chokudai's blog

By chokudai, history, 5 weeks ago, In English,

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!

 
 
 
 
  • Vote: I like it
  • +99
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

the timing is a little bit confusion.It collides with #655 div2 on codeforces right? Can anyone tell me the start time in india?

»
5 weeks ago, # |
Rev. 3   Vote: I like it +2 Vote: I do not like it

Strange registration time?

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Good luck!

»
5 weeks ago, # |
  Vote: I like it -158 Vote: I do not like it

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?

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you elaborate your approach.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        Hint
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you. That was a good approach!

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 2   Vote: I like it +3 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it +17 Vote: I do not like it

      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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you tell me where I went wrong ?

        Submission

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +46 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 3   Vote: I like it +32 Vote: I do not like it

        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)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I also reached here.. but how to evaluate further

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    I used Berlekamp Massey.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 4   Vote: I like it +28 Vote: I do not like it

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

I solve C by calculating all data on my laptop :|
Can I break longest code on atcoder ?
Here is my code .
Picture
:|

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

how to solve C

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why we are taking i=1 to 100, is it compulsory to take till 100?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    Spoiler
»
5 weeks ago, # |
  Vote: I like it -64 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

greedy in E.??

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

was that a rated contest?

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like 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/15177397

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like 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:

    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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +69 Vote: I do not like it

F answer in case anyone is wondering

F-ans

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    :O

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you came up with this solution?

    Can you please give some hints.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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+=1

l=[0]*n ll.sort() for i in ll: if i>n: break else: l[i-1]=d[i]

for i in l: print(i)

»
5 weeks ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

B Question wrong Answer.But I can not find it Wrong. Please help me

include

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;

}

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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);
    
»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What's the idea of solution for problem E?

»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

When will the English Editorial be published?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The test cases for the contest don't seem to be in the usual Dropbox folder. Is there a chance to get them somehow?