I think YES because points are 100-200-300 as in Beginner contest

http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200711T2100&p1=248
Check this link contest starts at 5:30 pm in India

No it is fine. It is at usual 5:30 PM IST and CF round starts at 8:35 PM IST.

It doesn’t collide. This one ends about an hour and a half before the div2 starts.

See you on the scoreboard!

IT'S 3RD

You can suppose that all the camels isn't among the first ki .

Then just greedy to consider which one is among the first ki in different cases : l<r,l>r

how did you solve D? can you share your code please or article about concepts that you used.

You can use s2 = s1 + x(1) and so on....so you get: 2(s1+u1+n1+k1+e1)+x1+x2+x3+x4+x5 <= N, and we want sum x1*x2*x3*x4*x5, this can be calculated using coefficient of x^N in: (1+x^2+x^4.....)^5*(x+2*x^2+3x^3....)^5*(1+x+x^2....)

I used Berlekamp Massey.

You don't had to ig... Brute force would suffice..

the trick was to just precalculate those big numbers modulo the bitcount

After just one operation ,no matter what X is intially, X will become <200000. Now just precalculate answers for all y<200000. To find what X will become after first operation i.e after inverting a bit ,use modexp.

In the first step you have to calculate a large number modulo $$$x$$$, where $$$x$$$ is the number of set bits. Note that, the large number is a sum of some powers of two, so just add those powers of two modulo $$$x$$$, can be done in $$$O(n)$$$ or $$$O(nlogn)$$$. One simple observation on the problem is, once you toggle a bit $$$x$$$ increases or decreases by one. So first calculate two values, one is the large number modulo $$$x-1$$$ and the other being large number modulo $$$x+1$$$. After that for each of the toggled bit its easy to do the operation once. After that whatever number you get is going to be less than $$$n$$$. Then as you've mentioned proceed normally.

There are only two possible bitcounts (the original plus one and the original minus one).

You can determine the original value of S modulo both of these (2 numbers; each takes O(n) to compute). Then each bit flip means adding or subtracting a power of 2 to the original value of S (constant time). So all of the initial values can be computed in O(n) time.

The idea in D is that only the first mod operation is on huge number, all others are on numbers in int range, and not much operations at all.

So we find a way to calc the first mod operation. Note that there are only two possible number of bits we have to consider. This is the initial number +1 or -1.

Therefore we calculate the mod value of the original long string for those both mods. Then we go from left to right, and add the mod value of this single position to the sum (one of them, depending if current symbol is 1 or 0). The mod value of the current position can be calculated using power() function.

see for example code

Look after the first modulo operation x will be between 0 to cnt-1, cnt = number of 1. Then the binary representation will have 0-20 digits as log2(N) < 20. Then it's easy.

So we have to calculate the mod of first operation. Now the problem is X is huge. X can be written as X = sum of power of 2 from binary representation. And for every position in the binary string the number of 1 will be cnt+1 if S[i] = 0 or cnt-1 if S[i] = 1. So for this two we will calculate the module of X in O(n) operation.Let, after first operation X becomes a.

Now for pos 0 to n-1
if S[pos] = 0
   a = (X + pow(2, n-1-i))%(cnt+1)
else
   a = (X - pow(2, n-1-i))%(cnt-1)

This way we can handle the first operation. Another special case is cnt = 1, Then if S[pos] = 1, output will 0. Here is my Code

Thanks, everyone for helping! I had missed the fact that I could calculate the remainder by summing up the remainders from each bit (raising 2 to the power and then taking the remainder and then summing up). I feel silly.. lol!

Anyways, upsolved! code

Just brute force each variable from 1 to sqrt(i-2) -1. The constraints are small enough to allow brute force solution.

brute force over all possible values of x such that x <= sqrt(n)

Use a very simple brute force approach. Take numbers from 1 to 100 in 3 nested loops. And increase the count for n when the value, i.e. (x*x+y*y+z*z+x*y+y*z+z*x)=n. Then, in find the answer for each number in O(1).

Note, the limit on N = 10^4 , and since x,y,z are all positive, there maximum value can be sqrt(N) = 100 . Hence ,brute force for all x,y,z <= 100 ,making 10^6 iterations in total! Here's my submission https://atcoder.jp/contests/aising2020/submissions/15159448

Notice that if you take any value greater then 100 for x,y or z then resulting value of the given equation will be >10000. Thus we just have to brute force through all possible triplets consisting of values from 1 to 100, and store the count of each value which is generated.

vi f(1000000,0);
 
void pre()
{
    rep(i,1,101)
    {
        rep(j,1,101)
        {
            rep(k,1,101)
            {
                f[i*i+j*j+k*k+i*j+i*k+j*k]++;
            }
        }
    }
}

Careful when taking modulo: clip — 1, for example, could be 0, which generates an error.

I don't think anyone will read the code if you just copy-paste like this here. Just post a ideone link.

Anyways, I think you haven't considered the case where there is only one set bit. If that set bit is inverted then we have to perform 0 operations. If you are taking mod with 0 it will give RE

https://atcoder.jp/contests/aising2020/submissions/15181202 i know this community is pretty toxic they just downvote if ur rating is less than 2000 i guess. here is my code for D https://atcoder.jp/contests/aising2020/submissions/15181202 if anyone have some time for a fellow problem solver could u please help in debugging the above code.I am getting RE and had no clue for 20 min during contest and not now too. Any help will really be appreciated. like always pls downvote.

I think this is for D, so: In your case m2 = m1+1 or m2 = m1-1, so just calculate the remainders with (m1+1) and (m1-1) initially....now any bit flip adds or subtract 2^i modulo m2 which you can calculate in O(log(n))

store the ans for ans1=x%(popcount(x)-1) and ans2=x%(popcount(x)+1) precalculate value for 1<=i<=2*10^5 using dp {dp[i]=1+dp[i%(__builtin_popcount(i))])}

then answer queries as if(s[i]=='1') {if(popcount(x)==1) cout<< 0 ; else cout<<1+dp[(c-1+(ans1-pow(2,n-i-1))%(c-1)];} else cout<<1+dp[(ans2+pow(2,n-i-1))%(c+1)];

yes

store the ans for ans1=x%(popcount(x)-1) and ans2=x%(popcount(x)+1) precalculate value for 1<=i<=2*10^5 using dp {dp[i]=1+dp[i%(__builtin_popcount(i))])}

then answer queries as if(s[i]=='1') {if(popcount(x)==1) cout<< 0 ; else cout<<1+dp[(c-1+(ans1-pow(2,n-i-1))%(c-1)];} else cout<<1+dp[(ans2+pow(2,n-i-1))%(c+1)];

I tried the same idea! But it is wrong.

The problem is adding something can break a later prefix. Suppose you assign 3 camels to be in the first 3 positions. Then you try to add a camel to position 2. You will think this is OK (because you've only assigned 1 camel to the first 2 positions), but actually it breaks the length-3 prefix (there are now 4 camels in the first 3 positions).

I think l-r<0 is different from the case that l-r>0,so the need to be considered differently.

And I just use a set to store the unused position. https://atcoder.jp/contests/aising2020/submissions/15172079

Here's my solution. We process the camels whose l > r and whose l < r separately. Say for the camels whose l > r, we start assigning them from right. For some position i, you maintain the remaining camels whose k >= i in increasing order of l — r (using a set). Now, if there's any camel remaining, we assign the one with the maximum l — r value. Otherwise we don't assign any camel to position i. Similarly we do from left to right for l < r. Finally, we take the minimum of l and r for those whose positions are not assigned.

Complexity : O(N * LogN).

If I understand your solution correctly, than it will choose optimal solution from all placing camels such, that there are at most $$$k$$$ elements on first $$$k$$$ positions. If $$$L_i \geq R_i$$$ for all $$$i$$$ this would be fine, since any solution with some vacant position $$$i$$$ has some other position with $$$j > i$$$ with more than one camel in it and if we move one of them to spot $$$i$$$ the only thing which can change is that the camel we moved will get score $$$L_k$$$ instead of $$$R_k$$$ but since we assumed $$$L_k \geq R_k$$$ the solution after the swap can only be better, so there is an optimal solution for the generalized problem which is a permutation.

But if we don't have this assumption we can have for example:

2
1 1 2
1 1 2

Where your solution would try to put both camels on spot 2 which is not allowed.

However the idea is not so far from correct. You only need to notice, that if we have some camel $$$i$$$ with $$$L_i \geq R_i$$$ and some other $$$j$$$ with $$$L_j < R_j$$$ then there is an optimal solution where $$$i$$$-th camel goes before $$$j$$$-th, because if they don't we can just swap them and the score can't decrease. Now just put all camels with $$$L_i \geq R_i$$$ on the left, other on the right and use the solution you described for each of those parts independently

Try

3
001

and

3
000

I got AC after trying these.

:O

How did you came up with this solution?

Can you please give some hints.

You are trying to create an integer from 200k bits... that does not work. But is not nessecary, too. You can put the string into the constructor of bitset.

I assume the error comes from the fact that you do %bitset.count() later, which is sometimes 0, hence you get a division by 0.

However, if you fix this the code will still most likely TLE. The idea is to find a faster implementation than brute force. more explanation

        long long int x = stoi(temp,0,2);
        bitset< 200002 > bits(x);

Usually it will be translated into English soon. You can see the line 'Under construction' at the end of the editorial.

You can see video tutorials at the end of my screencast.