For most div 2 participant, AGC isnt even rated, so that works out.

Thank you for the notice. Somehow I though the AtCoder round is the usual 2h long. We've moved the round to avoid the clash.

wishing luck

Some people like me might say that Codeforces isn’t for you. But don’t lose hope—keep pushing forward and keep grinding.

E might be easy since it's score is just 2000, we have to aim for AK (or if F is too hard then speed will matter). Good Luck!

UPD : Well you are too close. Solving till E will probably suffice (rather we should talk about rank, so top 200).

UPD 2 : My predictions actually worked, but this is still generally not correct.

Score distribution only says how difficult are the problems relative to each other, not how difficult they are relative to other problems on the platform, so you can't really make a prediction like this.

in such strange time?

precisely my thought, haha!

id say binary strings arent too rare, if youre interested in the topic i can link you some problems with them i solved

Maybe you can take a nap from 22:00 to 23:00 (UTC+8)

You are Chinese so I used UTC+8

Thanks for being a tester for the round.

ask your mumma(mom) to buy one!!

More laughing faces

as it's clashing with atcoder

and div1 problem

Yeah I was a bit surprised a straightforward DP works (at least passed pretest). Thought it may need some optimizations.

C, D, E < B for me during contest lol

B took ~25 mins to solve while C, D and E took 20, 10 and 20 respectively.

since i knew that every perfect square is having odd divisors, i could do B easily, but C took me much of time for implementation and trying to figure out all cases

also i have seen the exact B question but only difference is the question had asked to find how many bulbs would be off at end

C is not easy to prove. B is pretty obvious.

You don't need to know $$$(x \oplus x = 0)$$$ for E to code the knapsack? You just need to know xor of two numbers $$$< 2^i$$$ is $$$< 2^i$$$. Also, E isn't code heavy at all.

Is B actually binary search? Had to code a quick program to show me the pattern there.

how to solve D? is it related to gcd?

I agree, I felt I knew close to the full solution as soon as I opened each of the problems for A-E.

Fyi E has an even simpler (and more braindead implementation) approach than yours.

1. Just realize $$$x \oplus x = 0$$$, so the value $$$x$$$ only contributes if it occurs an odd number of times.

2. Knapsack to find these "odd" probabilities in $$$O(n)$$$.

3. $$$a_i \leq 1024$$$, so just do Knapsack to find the probability of each $$$f(S)$$$ (worst case $$$~2 \cdot 10^7 ops$$$).

For E you can also dp for the probability of each resulting xor value and just calculate directly.

I agree completely, also something to note on E : it is even more classic than you put it as, because you can just code the trivial n * 1024 dp which comfortably passes without optimizations.

I am sad that this is the impression indian rounds leave for people....

binary search

I just wrote a bruteforcer, it is a stupid problem.

it's binary search, notice that only perfect squares are turned off in a range.

If you naively used a DSU, you would have to merge at worst O(n) elements for one operation. Since you have m Operations, you can have up to O(n*m) Merges, which is way too slow.

There are a lot of approaches to solve the problem, but the main observation is that $$$d_i \leq 10$$$. Based off that you could store for each element the last element to update and the merges that you would still need with a specific value of d. Thus, you only need to store how long the updates have to go back for each d, which means that for all elements, you have at most 10 merges backwards. For a merge just use the dsu to merge with the other element and update the amount of updates for the prior element if neccessary.

To speed up you can use 10 dsu (for each d).283663343

To be honest, this is not a big deal since the observation was easy enough to make anyway. And if you didn't make it, you could just write a brute force to print the numbers that don't have an even number of divisors and you would realize instantly that they are the square numbers.

I got WA on pretest 8 twice. Then I replaced sqrt by sqrtl and got AC

should be like this

mid — n>=mid/(mid-n) + (mid%(mid-n)==0?0:1)

Try binary search to find sqrt(n) otherwise after getting n through binary search as you have done manually check by incrementing n when is n-sqrt(n)>=k

$$$sqrt(n)$$$ is not accurate enough for $$$10^{18}$$$, you will pass pretests (and hopefully systests) if you use $$$sqrtl(n)$$$.

The safest approach is to binary search on the value of $$$y = \lfloor \sqrt{x} \rfloor$$$ as $$$y \cdot y \leq x$$$. I was too lazy to do that in contest, lets see if the risk pays off :).

Submission: 283590674

while(n >= k){
    ans++;
    n = operate(n, k);
}
ans += n;

Possibly you missed the case when k==1, and directly output n, as there might be issues with division with 0 which would give TLE/Runtime Error. Also its kind of like writing n in the base k, and finding the set bits of it

Told you not to trust Varga

for C, iterate over bits and check if its possible to make the difference of the 2 bits of the first expression equal to the second expression. there are a few cases, and theyre pretty simple to figure out. for B, binary search, and also try to find out for a certain range how many bulbs will be turned on

Well for what it's worth, I did solve it without guesswork. Bulb $$$x$$$ is on if it's flipped even number of times. Every factor of $$$x$$$ flips it. So "good" bulbs are those with even number of factors.

Represent $$$x$$$ as its prime factorization, $$$p_1^{n_1}\cdot p_2^{n_2} \cdots p_m^{n_m}$$$. Number of factors of $$$x$$$ is $$$(n_1 + 1) \cdot (n_2 + 1) \cdots (n_m + 1)$$$ (we have $$$n_i + 1$$$ choices for which power of $$$p_i$$$ to include in each factor)

It's easier to find bad bulbs — they have odd number of factors, so $$$n_i + 1$$$ must be odd $$$\forall i \in [1, m]$$$. So $$$n_i$$$ must be even $$$\forall i \in [1, m]$$$. Which is a roundabout way of defining a square number. So bulbs with square indices are bad.

I agree that it's guessable, but also liked arriving at the solution, which probably will cost me some rating. Anyway, I'm sure someone with better maths can solve it much faster.

Generate more samples either by hand or with brute force program and find pattern, that's how I did this problem and that's how I solve most of problems that are not obvious.

no, that won't fix probably. Changing language/compiler might fix .

I hope all O(N x 1024) solutions will be eliminated :( :(

$$$2 * 10^8$$$ operations for 4 seconds is fine lol

Considering that it is trivial to cut this approach, I'm guessing that is true.

nope, it was just maths knowledge test contest

each bit is independent in this equation

a=b^d

So do i, man. It really encourages me to learn more about number theory.