We will hold AIsing Programming Contest 2020.

- Contest URL: https://atcoder.jp/contests/aising2020
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200711T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: camypaper
- Rated range: ~ 1999

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

Can we expect it's difficulty to be similar to normal ABC's?

I think

because points are 100-200-300 as in Beginner contestYESthe timing is a little bit confusion.It collides with #655 div2 on codeforces right? Can anyone tell me the start time in india?

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!

And then on youtube. :P

Waiting for Youtube to process :)

div 2 was not rated .

Waiting for the screencast senpai UwU!

Strange registration time?

Good luck!

## include

using namespace std;

int main() { int n; cin>>n;

int arr[n+1];

for(int i=0;i<n;i++) { arr[i]=0; }

int x=1,y=2,z=2;

while((6*x*x)<=n) { arr[(6*x*x)-1]=1; x++; }

while(((y+1)*(y+1)+2)<=n) { arr[((y+1)*(y+1)+1)]=3; y++; }

while(((z+1)*(z+1)+2*z*z)<=n) { arr[((z+1)*(z+1)+2*z*z-1)]=3; z++; }

for(int i=0;i<n;i++) { cout<<arr[i]<<endl; }

return 0;}

CAN ANYBODY TELL ME WHERE I'M GOING WRONG?

IT'S 3RD

ya sure! Just wait for remaining 7 minutes to end :)

why are you commenting your code before the contest

also please dont ask questions during contests.

How to solve E? Ternary search? We try placing all elements having

`l > r`

to left,`r > l`

to right and add`k`

for`l = r`

. The answer will first increase and then decrease based on how many elements we place having`l > r`

on left?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

code: https://atcoder.jp/contests/aising2020/submissions/15172079

Can you elaborate your approach.

let v[i] = l — r if l-r>0.let v'[i]=l — r if l-r<0.

you can see that if v[i] are added to the answer the answer will be better.

if v'[i] are added to the answer the answer will be worse.

So each v[i] want to be as front as possible,and v'[i] want to be as behind as possible.

Then try to solve it on your own.

HintTRY TO SORT v[i] and v'[i]

But this ignores the K[] values completly. It can be better to switch the first two camels, assume the first has k[i]=2, and the second has k[i]=1.

I think for any position we can check using binary search if it is possible to put that element with l-r>0 at that position. Correct me if i am wrong.

I need more explanation to understand.

sort on what basis l-r or k for array v.

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

Observe that converting 0 to 1 increase bits by 1 and 1 to 0 decrease bits by 1.

So we can find two values of string using above 2 values as mod. After this it means you have already applied one operation. Now you can observe the new values < 21 because we doing mod by set bits which can be atmost 21 ( 2 ^ 21 > 2 * 10 ^ 5 ). After that apply brute force.

Take care of special case when the count of 1 in string is 1. In that case our second mod is 0 which can give RE if apply above process.

Submission

When the mod value is odd, then each of the bits with $$$2^k > mod$$$ will give a non-zero reminder, which we should add to the number obtained from the first whatever bits right?

I was stuck here...

I was stuck here too, but then I saw that I forgot to update mod after operation. So there won't be any instance such that our mod will be greater than number which means we won't get stuck.

Can you tell me where I went wrong ?

Submission

How to solve F,I just came up with a solution of $$$O(5*n^2)$$$

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....)

how to find the coefficient of x^N in that product.I also arrived at this point.

Ok so we have: (1+x^2+x^4....) = 1/(1-x^2)

(x+2*x+3*x^2...) = x/(1-x)^2

1+x+x^2... = 1/(1-x)

so after some simplifications you have:

coefficient of x^(N-5) in (1+x)^11/(1-x^2)^16

Expand the denominator you'll get terms of form C(15+r, 15)*x^(2r)

From numerator you have C(11,j)*x^j , multiplying them we have:

C(15+r,15)*C(11, j)*x^(2r+j) , j <= 11, make a loop from j = 0 to 11, find suitable 'r' and add the coefficient: Complexity: O(15*11*T)

Ohhh nice ... Just got there but missed it .. Thanks a lot

thank you

I also reached here.. but how to evaluate further

How did you get the above polynomial expression? Can someone please share an intuition behind it?

Hmm.....you should practice some NTT/FFT/Generating Functions problem.....

how did you get the 2nd term (x+2*x^2+3*x^3+..)

If you need number of solutions of that equation you take (x+x^2+x^3....) but notice that you need the sum (x1*x2*x3*x4*x5) i.e. you need the values of the solution....For now assume that there was only one term i.e. x1 and you need the sum of values of x1 over all solutions....this can be done if you take the polynomial (x+2x^2+3x^3...) since when you multiply this polynomial with some other polynomial you'll get the contribution of x1....if you are not able to understand it then try some hand-made examples, you'll understand it.

I used Berlekamp Massey.

Could you explain, Berlekamp Massey is used for solving recursion right??

edit :: NVM got it by seeing your code. Awesome!!

I solve C by calculating all data on my laptop :|

Can I break longest code on atcoder ?

Here is my code .

Picture

:|

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

Can anyone help with question D? I mean, was there a pattern or something, that I missed? I understood this that after the first modulo operation, a simple approach would do, but how was I to find the remainder of such a large number with the count of it's set bits?

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

Could you elaborate a bit?

Observe that if original number has 'n' number of set bits then after inverting the number of set bits will be n+1 or n-1. Also since the binary number is sum of powers of two you can first calculate its mod by these two numbers. Also see modular exponentiation.. https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/

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.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

Hey I'm unable to understand this, what happens if N=2e5 and the string has all 1 set.

In that case it would be having 2e5 as popcount. I'm unable to wrap this fact,can you clarify more. Thanks!

If the string size 2e5 having all 1 in the string, then

`cnt =2e5`

. So after first mod operation X must become 0 to 2e5-2, X = the number of whose binary string is given. Let, it becomes X = 2e5-2 after first operation.Now for the second operation`cnt must be less than 20 as log2(2e5-2)<20.`

Then we can check untill X becomes 0 as it will be a very few moves. And the first operation I tried to explain in my first comment....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

how to solve C

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).why we are taking i=1 to 100, is it compulsory to take till 100?

if x = 1,y = 1,z = 100.formula's value will be > 10000. while maximum N can be 10000. so you can go till only 100.

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.

Spoilerimport java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(reader.readLine()); char[] list = reader.readLine().toCharArray(); int clip = 0; for(int i = 0;i<n;i++){ if(list[i]=='1') clip++; } int[][] rems = new int[2][n+1]; ArrayList l = new ArrayList<>(); l.add(-1); l.add(1); for(int i=0;i<2;i++){ int temp = clip + l.get(i); for(int j = 0;j<=n;j++){ if(temp==0){ rems[i][j] = 0; continue; } if(j==0) rems[i][j] = 1%temp; else rems[i][j] = (rems[i][j-1]*2)%temp; } } int[] remlist = new int[2]; for(int i = 0;i<2;i++){ int temp = clip + l.get(i); for(int j = 0;j<n;j++){ if(list[j]=='1'){ remlist[i] = (remlist[i]+rems[i][n-j-1])%temp; } } } for(int i = 0;i<n;i++){ if(list[i]=='1'){ if(clip==1){ writer.write(1+"\n"); continue; } int lp = ((remlist[0] — rems[0][n-i-1]) + (clip-1))%(clip-1); writer.write((1+solve(lp))+"\n"); } else{ int lp = (remlist[1] + rems[1][n-i-1])%(clip+1); writer.write((1+solve(lp))+"\n"); } } writer.flush(); } public static int solve(int p){ if(p==0) return 0; int temp = p; int cnt = 0; while(p>0){ if(p%2==1) cnt++; p=p>>1; } if(cnt==0) return 1; return 1 + solve(temp%cnt); } } here is my code for D don't know why ia am getting RE in 5 cases else all are AC

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.

Take care of modulo 0. It can cause RE.

Try your code on the test cases

3 010

3 000

these should be enough to test the special-casing

https://atcoder.jp/contests/aising2020/submissions/15183714 The problem is when clip==1. I handled that case separately.

If I have a value x which is n % m1.

Is there a way to get value n % m2 using x, m1 and m2 ?

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))

I feel so dumb right now, Thanks for the answer :)

All our queries will be solved when secondthread puts out his screencast.....meanwhile happy upsolving....

greedy in E.??

How to solve D? I have wasted lots of time on C just for finding the pattern then I realised I can pre calculate the values.

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)];

was that a rated contest?

yes

really love questions specially problem D. here is my submission. submitted after 10 wrong attempts.

https://atcoder.jp/contests/aising2020/submissions/15180168 good contest!

Can any one explain me the approach of D no problem ? I was just implementing what has been told in question but it gives me RE.Thanks in advance

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)];

Here c=popcount(x)???

yes

https://ideone.com/Tl2PvZ This gives runtime error again But what's the problem now??

I couldn't find the error as such but if it is showing RTE for 5 cases then it is for the cases when c=1 You can see my code for finding the exact mistake My Submission

AC.Got it

This time difficulty of D is more than usual AtCoder(abc)-D btw Loved Problem-D so much :)If need help -https://atcoder.jp/contests/aising2020/submissions/15177397Hello, I'd appreciate any help knowing why the following logic for E is wrong (I've spent over 1.5+ hours cross-checking it with brute force generators+checkers, and finally found a failing case of n = 85k. However, somehow it fails all testcases on atcoder).

First, I sort all those with l>r in decreasing order, and consider them one by one. I update the fenwick tree at point K, if sum(0,K) <= K+1 for the current query (which implies I have not filled my quota for this prefix). Thus, you could say I am greedily assigning them.

Similarly, for those with l<r, I try to assign them to the point K+1 greedily (the next available point). Is there an easy failing testcase for the above?

Code can be found here

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).

Ahh, I see. Thanks! So I just have to iterate by sorting K and storing a multiset, and removing values when I can I guess.

What is the solution to E?

I tried greedy. Sort by |L-R|, and then try to add camels one-by-one taking the higher value. How do you tell if you can put a camel in the first K? (or last K). Let P[k] be the number of camels that have been placed in the first k spots. Then we must have \sum_{i=0}^j P[i] <= j+1 for each j. Keep track of these partials sums in a segtree. Adding a single camel means subtracting 1 from a range in the segtree. If the global min becomes negative, adding the camel is not allowed.

Is the idea above right?

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).

Your code: https://atcoder.jp/contests/aising2020/submissions/15167753

g1[k[i] + 1].pb(i); why k[i]+1 ?

Yeah, so when I go from left to right, the camel should be added at (k[i] + 1)th position since strictly after k[i], we'll be taking r instead of l.

But what will happen when camels of type-1(L > R) overlaps with camels of type-2(R > L). i.e., they are fighting for same position.

Say we fill the camels whose l > r at some positions. We can shift all of them to the left. Similarly for those whose r > l, we can shift them to the right. The remaining positions can be filled with the remaining camels. So in short even on overlapping, we can do some shifting to get the same value.

Thanx got it

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:

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

Sorry, I didn't describe my solution fully. I have two segtrees, one for L>R and one for R<=L (and it does correctly give 3 for your case). I think that's the same as your observation. https://atcoder.jp/contests/aising2020/submissions/15181711

I am getting runtime error for problem D. https://atcoder.jp/contests/aising2020/submissions/15184028 Please suggest some test cases.

Try

and

I got AC after trying these.

F answer in case anyone is wondering

:O

How did you came up with this solution?

Can you please give some hints.

Express what you're looking for with bunch of summation notations, then find out whether mathematica can reduce it for you like this. ( In[41] is the desired answer )

I reduced $$$F$$$ to finding $$$\displaystyle\sum_{i=0}^{\left\lceil \frac{n}{2}\right\rceil -3}\binom{i+4}{4}\binom{n+5-2i}{10}$$$. Any ideas on how to simplify this to run in $$$O(1)$$$?

Can anyone help me, please? Getting Runtime Error in Problem D. Here is my code: https://atcoder.jp/contests/aising2020/submissions/15178586 Thanks for your time.

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

Could someone help me with my WA code on problem D. I use the same idea as many people here but get WA on 4 test cases. I cannot find out the mistake. Thanks in advance. My submission

Hi there, I am new at Atcoder can anyone help me where can I find tutorial in English.

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.

When will the English Editorial be published?

If anyone is having difficulty with D , Here is a detail explanation(not a video tutorial) of D Here

Will there be an AB(G?)C this Sunday?