Even more weirder, if we use binary representation for every cf round number, all bases $$$i$$$ $$$(i \gt 1)$$$ seems to be happy :|

PS: Came up with a problem based on this

*last binary contest of the century

(assuming 1 to 2 contests per week on avg)

last binary contest :|

a few hours/mins after system test completes

If you made at least one submission (even if it's wrong), then you'll be rated

However, you need to submit at least one accepted solution in 5 different live contests to be a trusted participant of Div. 3

note that "trusted participant" refers to the participants who are included in the official standings of the contest

I don't think there's an application process for it. ig it's invite only. So, maybe try forcing one of ur friends to author a round :-)

better than getting hacked/failing sys test :-)

The authors of the problems are referred to as the problem setters

The problem testers are the ones who try solving the problems and provide feedback for any required improvements. This is done across multiple user ratings to get an idea of what a participant will experience when solving the problem...

by using a debugger

by putting a bunch of print statements and dry running the code to catch the place where it doesn't behave as intended

C is a great problem :-)

lol

I Hope to regain my lost ratings in this contest :-)

Since the graph is bidirectional, it will have atleast 1 loop (assuming $$$n \ge 2$$$)

So, if we define a tree with root 1, it's contradictory (as loops not allowed in tree)

EDIT: nvm, just realised that "bidirectional paths" is part of storyline and has nothing to do with the problem itself...

I understand that from the picture but since the graph is bidirectional, we have no sense of direction

So, when we build a subtree with h=1;v=2 how can we include 3 but exclude 1?

In problem C,

"The houses in the village are connected by bidirectional paths"

So, if the graph is 1---2---3 then houses 1 and 3 forms a guild, right? (v=2;h=1)

I hope to solve A to C (and maybe D)

Nice problemset

I overthinked B and wasted a lot of time :(

B involves more thinking. But, A is a straight forward question (the formal definition describes the exact implementation to do)

The O(n) solution is well known. So, the $$$O(n^2)$$$ solution feels too easy for a Div 1+2 (usually easy implementation problems are given only in Div. 4 or Div. 3)

For problem A, an O(n) solution exists. But since $$$1 \le n \le 100$$$ an $$$O(n^2)$$$ solution would also pass

This makes the problem too easy for a Div. 1+2

$$$B \gt C \approx A$$$

Problem A constrain on n is too small

For second problem,

(I assume $$$1 \le a[i] \le 60$$$)

The prime numbers between 1 and 60 are 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59

let x be an integer in the inclusive range of 1 and 60.

The prime factorization of x can contain $$$2^5$$$ (when x is 32) but it can never contain $$$2^6$$$ (for that $$$x \ge 64$$$, which is not allowed)

The prime factorization of x can contain $$$3^3$$$ (when x is 27 or 54) but it can never contain $$$3^4$$$ (for that $$$x \ge 81$$$, which is not allowed)

Let P(m,n): The prime factorization of x can contain $$$m^n$$$, $$$m^{n-1}$$$, ..., $$$m^{0}$$$ but it can never contain $$$m^{n+1}$$$

It can be shown that the following are true: P(2,5) P(3,3) P(5,2) P(7,2) P(13,1) P(17,1) P(19,1) P(23,1) P(29,1) P(31,1) P(37,1) P(41,1) P(43,1) P(47,1) P(53,1) P(59,1)

So, total number of possible LCMs= 6*4*3*3*2*2*2*2*2*2*2*2*2*2*2*2*2 = 1769472

However, we can verify programmatically that the number of LCMs less than or equal $$$10^9$$$ is 206181 using the code below

from itertools import product
from math import prod
c=0
for [p2,p3,p5,p7,p11,p13,p17,p19,p23,
     p29,p31,p37,p41,p43,p47,p53,p59] in product(
         range(6),range(4),range(3),range(3),
         *([*range(2)] for _ in range(13))):
    l=prod([2**p2,3**p3,5**p5,7**p7,11**p11,13**p13,
            17**p17,19**p19,23**p23,29**p29,31**p31,
            37**p37,41**p41,43**p43,47**p47,53**p53,
            59**p59])
    if l<=10**9:
        c+=1
print(c)

We can count the frequency of each element in a. This frequency array is guaranteed to have atmost 60 elements. Let this frequency array be b

Now, we iterate over every allowed LCM value and calculate the number of permitted elements from array a that can be choosen in the subset. Let's call this computed value as m. The max value of m over all iterations will be the answer

no. of operations = 60*206181 which is approx. in the order of $$$10^7$$$

Code:

from itertools import product
from math import prod
n,t=map(int,input().split())
a=[int(x) for x in input().split()]
from collections import Counter
b=Counter(a)
ans=0
for [p2,p3,p5,p7,p11,p13,p17,p19,p23,
     p29,p31,p37,p41,p43,p47,p53,p59] in product(
         range(6),range(4),range(3),range(3),
         *([*range(2)] for _ in range(13))):
    l=prod([2**p2,3**p3,5**p5,7**p7,11**p11,13**p13,
            17**p17,19**p19,23**p23,29**p29,31**p31,
            37**p37,41**p41,43**p43,47**p47,53**p53,
            59**p59])
    if l<=t:
        m=0
        for k,v in b.items():
            if l%k==0:m+=v
        if m>ans:
            ans=m
print(ans)

EDIT: fixed code taking too much horizontal space

EDIT: fixed a mistake (I used variable x to describe 2 different things but now i replaced one of them with m)

looking at the score distribution, ig i can do 3 to 4 problems fs

I hope to become specialist again :)

Auto comment: topic has been updated by jothin (previous revision, new revision, compare).

Auto comment: topic has been updated by jothin (previous revision, new revision, compare).

Auto comment: topic has been updated by jothin (previous revision, new revision, compare).

Auto comment: topic has been updated by jothin (previous revision, new revision, compare).

Auto comment: topic has been updated by jothin (previous revision, new revision, compare).

Auto comment: topic has been updated by jothin (previous revision, new revision, compare).

Auto comment: topic has been updated by jothin (previous revision, new revision, compare).

Auto comment: topic has been updated by jothin (previous revision, new revision, compare).

Auto comment: topic has been updated by jothin (previous revision, new revision, compare).

https://codeforces.com/blog/entry/142192

Auto comment: topic has been updated by jothin (previous revision, new revision, compare).