### chokudai's blog

By chokudai, history, 11 months ago,

We will hold AIsing Programming Contest 2020.

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

We are looking forward to your participation!

• +99

 » 11 months ago, # |   +14 Can we expect it's difficulty to be similar to normal ABC's?
•  » » 11 months ago, # ^ |   +8 I think YES because points are 100-200-300 as in Beginner contest
 » 11 months ago, # |   0 the timing is a little bit confusion.It collides with #655 div2 on codeforces right? Can anyone tell me the start time in india?
•  » » 11 months ago, # ^ | ← Rev. 2 →   +1 http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200711T2100&p1=248 Check this link contest starts at 5:30 pm in India
•  » » 11 months ago, # ^ |   +9 No it is fine. It is at usual 5:30 PM IST and CF round starts at 8:35 PM IST.
•  » » 11 months ago, # ^ |   +12 It doesn’t collide. This one ends about an hour and a half before the div2 starts.See you on the scoreboard!
•  » » » 11 months ago, # ^ |   +62 And then on youtube. :P
•  » » » » 11 months ago, # ^ |   +16 Waiting for Youtube to process :)
•  » » » » » 11 months ago, # ^ |   0 div 2 was not rated .
•  » » » 11 months ago, # ^ |   0 See you on YouTube :D
•  » » » 11 months ago, # ^ |   +26 Waiting for the screencast senpai UwU!
 » 11 months ago, # | ← Rev. 3 →   +2 Strange registration time?
 » 11 months ago, # |   +3 Good luck!
»
11 months ago, # |
-158

# 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?

•  » » 11 months ago, # ^ |   -60 IT'S 3RD
•  » » » 11 months ago, # ^ |   +4 ya sure! Just wait for remaining 7 minutes to end :)
•  » » » 11 months ago, # ^ |   +7 why are you commenting your code before the contest
•  » » » 11 months ago, # ^ |   +4 also please dont ask questions during contests.
 » 11 months ago, # |   +6 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?
•  » » 11 months ago, # ^ | ← Rev. 2 →   +6 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 : lr
•  » » » 11 months ago, # ^ |   +3
•  » » » 11 months ago, # ^ |   0 Can you elaborate your approach.
•  » » » » 11 months ago, # ^ |   +3 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]
•  » » » » » 11 months ago, # ^ |   0 Thank you. That was a good approach!
•  » » » » » 11 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » » » » » 11 months ago, # ^ |   0 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.
•  » » » » » » » 11 months ago, # ^ |   +5 I need more explanation to understand.
•  » » » » » 11 months ago, # ^ |   0 sort on what basis l-r or k for array v.
•  » » 11 months ago, # ^ |   0 how did you solve D? can you share your code please or article about concepts that you used.
•  » » » 11 months ago, # ^ | ← Rev. 3 →   +17 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
•  » » » » 11 months ago, # ^ |   0 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...
•  » » » » » 11 months ago, # ^ |   0 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.
•  » » » » 11 months ago, # ^ |   0 Can you tell me where I went wrong ? Submission
 » 11 months ago, # |   +8 How to solve F,I just came up with a solution of $O(5*n^2)$
•  » » 11 months ago, # ^ | ← Rev. 3 →   +46 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....)
•  » » » 11 months ago, # ^ |   0 how to find the coefficient of x^N in that product.I also arrived at this point.
•  » » » » 11 months ago, # ^ | ← Rev. 3 →   +32 Ok so we have: (1+x^2+x^4....) = 1/(1-x^2) (x+2*x+3*x^2...) = x/(1-x)^21+x+x^2... = 1/(1-x)so after some simplifications you have:coefficient of x^(N-5) in (1+x)^11/(1-x^2)^16Expand 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)
•  » » » » » 11 months ago, # ^ |   0 Ohhh nice ... Just got there but missed it .. Thanks a lot
•  » » » 11 months ago, # ^ |   0 thank you
•  » » » 11 months ago, # ^ |   +8 I also reached here.. but how to evaluate further
•  » » » 11 months ago, # ^ |   0 How did you get the above polynomial expression? Can someone please share an intuition behind it?
•  » » » » 11 months ago, # ^ |   0 Hmm.....you should practice some NTT/FFT/Generating Functions problem.....
•  » » » 11 months ago, # ^ |   0 how did you get the 2nd term (x+2*x^2+3*x^3+..)
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   +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.
•  » » » » » 11 months ago, # ^ |   0 ohh yeah, got it thanks
•  » » 11 months ago, # ^ |   +40 I used Berlekamp Massey.
•  » » » 11 months ago, # ^ | ← Rev. 4 →   +28
•  » » » 11 months ago, # ^ | ← Rev. 3 →   0 Could you explain, Berlekamp Massey is used for solving recursion right?? edit :: NVM got it by seeing your code. Awesome!!
 » 11 months ago, # | ← Rev. 2 →   +12 I solve C by calculating all data on my laptop :| Can I break longest code on atcoder ? Here is my code . Picture :|
•  » » 11 months ago, # ^ |   +2 You don't had to ig... Brute force would suffice..
•  » » 11 months ago, # ^ |   0 https://atcoder.jp/contests/aising2020/submissions/15162450^^ this might help
•  » » 11 months ago, # ^ |   0 Just brute force each variable from 1 to sqrt(i-2) -1. The constraints are small enough to allow brute force solution.
 » 11 months ago, # |   +12 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?
•  » » 11 months ago, # ^ |   0 the trick was to just precalculate those big numbers modulo the bitcount
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 Thats what I did, Whats wrong? : https://atcoder.jp/contests/aising2020/submissions/15181474Why am I getting RE ?
•  » » » 11 months ago, # ^ |   +4 Could you elaborate a bit?
•  » » » » 11 months ago, # ^ |   +6 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/
•  » » 11 months ago, # ^ |   0 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.
•  » » 11 months ago, # ^ |   +8 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.
•  » » 11 months ago, # ^ |   +6 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.
•  » » 11 months ago, # ^ |   +3 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
•  » » 11 months ago, # ^ | ← Rev. 2 →   +6 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
•  » » » 11 months ago, # ^ |   0 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!
•  » » » » 11 months ago, # ^ | ← Rev. 3 →   0 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....
•  » » 11 months ago, # ^ |   0 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
 » 11 months ago, # |   +3 how to solve C
•  » » 11 months ago, # ^ |   +3 Just brute force each variable from 1 to sqrt(i-2) -1. The constraints are small enough to allow brute force solution.
•  » » 11 months ago, # ^ |   0 brute force over all possible values of x such that x <= sqrt(n)
•  » » 11 months ago, # ^ |   +1 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).
•  » » » 11 months ago, # ^ |   0 why we are taking i=1 to 100, is it compulsory to take till 100?
•  » » » » 11 months ago, # ^ |   0 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.
•  » » » » » 11 months ago, # ^ |   0 yes got it, thank you
•  » » 11 months ago, # ^ |   0 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
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 jsdhjshdjskhdjkshdjshd
•  » » 11 months ago, # ^ |   0 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. Spoilervi 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]++; } } } } 
 » 11 months ago, # |   -64 import 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(); 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;j0){ 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
•  » » 11 months ago, # ^ | ← Rev. 2 →   +8 Careful when taking modulo: clip — 1, for example, could be 0, which generates an error.
•  » » 11 months ago, # ^ |   0 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
•  » » » 11 months ago, # ^ |   0 really appreciate u had a look in my code. i have taken care of case when clip==1 i am returning 1 when clip==1
•  » » 11 months ago, # ^ |   -7 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.
•  » » » 11 months ago, # ^ |   0 Take care of modulo 0. It can cause RE.
•  » » » » 11 months ago, # ^ |   0 I think i have. really appreciate for ur time, thanks mate
•  » » » 11 months ago, # ^ |   0 Try your code on the test cases3 0103 000these should be enough to test the special-casing
•  » » » » 11 months ago, # ^ |   0 thanks i got my mistake. really thanks
•  » » » 11 months ago, # ^ |   0 https://atcoder.jp/contests/aising2020/submissions/15183714 The problem is when clip==1. I handled that case separately.
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   0 thanks mate , i got my mistake , really appreciate ur debugging skills.
•  » » » » 11 months ago, # ^ |   0 really smart work around line 25 26
 » 11 months ago, # |   0 If I have a value x which is n % m1.Is there a way to get value n % m2 using x, m1 and m2 ?
•  » » 11 months ago, # ^ |   0 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))
•  » » » 11 months ago, # ^ |   0 I feel so dumb right now, Thanks for the answer :)
 » 11 months ago, # |   0 All our queries will be solved when secondthread puts out his screencast.....meanwhile happy upsolving....
 » 11 months ago, # |   0 greedy in E.??
 » 11 months ago, # |   0 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.
•  » » 11 months ago, # ^ |   0 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)];
 » 11 months ago, # |   0 was that a rated contest?
•  » » 11 months ago, # ^ |   0 yes
•  » » 11 months ago, # ^ |   0 Rated for less than 1999 rating.
 » 11 months ago, # |   +3 really love questions specially problem D. here is my submission. submitted after 10 wrong attempts.
 » 11 months ago, # |   0 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
•  » » 11 months ago, # ^ |   0 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)];
•  » » » 11 months ago, # ^ |   0 Here c=popcount(x)???
•  » » » » 11 months ago, # ^ |   0 yes
•  » » » » » 11 months ago, # ^ |   0 https://ideone.com/Tl2PvZ This gives runtime error again But what's the problem now??
•  » » » » » » 11 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » » » 11 months ago, # ^ |   +1 AC.Got it
 » 11 months ago, # |   0 This time difficulty of D is more than usual AtCoder(abc)-D btw Loved Problem-D so much :)
 » 11 months ago, # |   +5 Hello, 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
•  » » 11 months ago, # ^ |   +8 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).
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +3 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.
 » 11 months ago, # |   0 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?
•  » » 11 months ago, # ^ |   0 I think l-r<0 is different from the case that l-r>0,so the need to be considered differently.
•  » » 11 months ago, # ^ |   +18 And I just use a set to store the unused position. https://atcoder.jp/contests/aising2020/submissions/15172079
•  » » 11 months ago, # ^ |   +31 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).
•  » » » 11 months ago, # ^ |   +3 g1[k[i] + 1].pb(i); why k[i]+1 ?
•  » » » » 11 months ago, # ^ |   0 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.
•  » » » » » 11 months ago, # ^ |   +3 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.
•  » » » » » » 11 months ago, # ^ |   +3 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.
•  » » » » » » » 11 months ago, # ^ |   0 Thanx got it
•  » » 11 months ago, # ^ |   +8 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
•  » » » 11 months ago, # ^ |   +1 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
 » 11 months ago, # |   0 I am getting runtime error for problem D. https://atcoder.jp/contests/aising2020/submissions/15184028 Please suggest some test cases.
•  » » 11 months ago, # ^ |   0 Try 3 001 and 3 000 I got AC after trying these.
•  » » » 11 months ago, # ^ |   0 Thanks.
•  » » » 11 months ago, # ^ |   0 Mine works with those TCs, but still RE: https://atcoder.jp/contests/aising2020/submissions/15181474
 » 11 months ago, # |   +69 F answer in case anyone is wondering
•  » » 11 months ago, # ^ |   +10 :O
•  » » 11 months ago, # ^ |   0 How did you came up with this solution? Can you please give some hints.
•  » » » 11 months ago, # ^ |   0 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 )
 » 11 months ago, # |   0 Hey can anybody help me with Problem C. why did i get WA for a test case?Here is my Python code....n=int(input()) d={} sm=3 a=1 brk=0 ll=[]while 1: we=sm-a for i in range(1,we): c=we-i b=i temp=pow((a+b+c),2)-(a*b+a*c+b*c) if temp not in d: d[temp]=1 ll.append(temp) else: d[temp]+=1 brk=max(brk,temp) if temp>n and a>=sm-2: break if we==2: sm+=1 a=1 else: a+=1l=[0]*n ll.sort() for i in ll: if i>n: break else: l[i-1]=d[i]for i in l: print(i)
 » 11 months ago, # | ← Rev. 6 →   0 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)$?
»
11 months ago, # |
-21

# include<bits/stdc++.h>

using namespace std; int main() { long long n,i,c=0; cin>>n; long long A[n]; for(i=1;i<=n;i++) cin>>A[i]; for(i=1;i<=n;i+=2) { if(A[i]%2==1) c++; } cout<<c<<endl; return 0;

}

 » 11 months ago, # | ← Rev. 2 →   0 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.
•  » » 11 months ago, # ^ |   +3 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); 
 » 11 months ago, # | ← Rev. 2 →   0 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
 » 11 months ago, # |   0 Hi there, I am new at Atcoder can anyone help me where can I find tutorial in English.
•  » » 11 months ago, # ^ |   0 Usually it will be translated into English soon. You can see the line 'Under construction' at the end of the editorial.
•  » » 11 months ago, # ^ |   +10 You can see video tutorials at the end of my screencast.
•  » » » 11 months ago, # ^ |   0 thank you it helped me a lot :)
 » 11 months ago, # | ← Rev. 2 →   0 What's the idea of solution for problem E?
 » 11 months ago, # |   +17 When will the English Editorial be published?
 » 11 months ago, # |   0 If anyone is having difficulty with D , Here is a detail explanation(not a video tutorial) of D Here
 » 11 months ago, # |   0 Will there be an AB(G?)C this Sunday?
 » 11 months ago, # |   0 The test cases for the contest don't seem to be in the usual Dropbox folder. Is there a chance to get them somehow?