chokudai's blog

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

We will hold AtCoder Beginner Contest 136.

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

We are looking forward to your participation!

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

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

How to solve E? ._.

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

    Notice that any number X which divides all the elements of the array also divides the sum of the array. Moreover, the sum is constant after any number of operations.

    Therefore, we iterate over all the divisors of the original array, and find the highest divisor which can be the answer.

    For checking if X is valid, I found A[i] % X for all A[i], pushed them into an array, sorted them, and then tried to reduce the left ones and increase the ones on the right to minimise the number of operations required.

    Code: https://atcoder.jp/contests/abc136/submissions/6699490

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    new to this site but have anyone tried binary search? i mean given a dividend we can use greedy method to judge whether it's possible and Nlog(K+max(array)) isn't too bad. although noticing the invariant is elegant, it's like kasiski's method.

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

Can someone explain E and F??

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

    They are explained in detail on my blog, but the gist is that for E, we should check whether each factor of the sum of the values in the array is achievable. We can use a greedy strategy to compute the minimum number of moves necessary to make all of our numbers divisible by one of these factors. For F, we use the Principle of Inclusion/Exclusion, along with a segment tree to track some important values. (Full details are on the blog.)

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

My solutions are up at https://codeforces.com/blog/entry/68900, for anyone interested.

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

    Thanks for the editorial @geothermal

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

    Thanks for quick and well-explained editorial after each Atcoder contest!

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

    Can you help me understand how idea of parity worked in problem D's solution?

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

      Whenever a child moves, the parity of its position changes, as any odd position is adjacent to two even positions, while any even position is adjacent to two odd positions. Hence, after $$$10^{100}$$$ moves, the parity of its resulting position will be the same as the parity of its original position, since the parity will have switched an even number of times. Once we've found two adjacent positions each child could end up in, therefore, we can pick the one with the same parity as the child's original position.

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

        It will have same parity because 10^100 is even ?

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

    hey! Geothermal please give approach for B-uneven numbers that you mentioned in your editorial for complexity O(log(n)).

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

How to Solve D ???

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

    You can maintain the prefix and suffix sums of L and R in each grid, while resetting them to $$$0$$$ when the letter in the grid is not the same as the one you want to maintain.

    This seems a little bit hard to understand, so code is here:

    int prel[MAXN], prer[MAXN], sufl[MAXN], sufr[MAXN], ans[MAXN];
    for (int i = 0; i < s.length(); i++) {
    	if (s[i] == 'L'){
    		prel[i] = prel[i - 1] + 1;
    		prer[i] = 0;
    	}
    	else {
    		prer[i] = prer[i - 1] + 1;
    		prel[i] = 0;
    	}
    }
    for (int i = s.length() - 1; i >= 0; i--) {
    	if (s[i] == 'L') {
    		sufl[i] = sufl[i + 1] + 1;
    		sufr[i] = 0;
    	}
    	else {
    		sufr[i] = sufr[i + 1] + 1;
    		sufl[i] = 0;
    	}
    }
    

    where the $$$prel,prer,sufl,sufr$$$ arrays denote the prefix and suffix sums.

    Then, you can see that if a child wanders to RL, he would always be wandering between these two grids. So a child would go one direction (as the one written in his grid) until he arrives to RL, since $$$10^{100}$$$ is a huge even number, you can assume that the movements fall into a 2-loop, count the prefix and suffix sums and you will know the answer.

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

      To understand the parity, you can write down the direction a child takes, and you'll find it's either RRRRRRR...RRRLRLRLRLRLRLRLRLRLRLRLRLRL... or LLLLLL....LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRL..., and you can find that it repeats after some time.

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

    Well find the closest opposing character in proper direction (for R, the closest L to right // for L, the closest R to left).

    It is easy to see that the child will step there "once".

    It is also easy to see that the child will "rotate" there + on its neighbor (before it) ..co in some "RL" substring :)

    To see where it will end, simply check the parity of distance.

    Good Luck & Wish you a nice day!

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

E and F were written by me. Thank you for participating!

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

Can anyone help me find out what is the problem of my code of F?Thx https://atcoder.jp/contests/abc136/submissions/6720126,it wrong 2 of the testdatas.

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

How to Solve F ??? help me thanks

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

What is the difficulty level/rating of ABC's problems E & F as compared to codeforces's problems ?

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

Can anyone give a solution for question D??

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

Hey, I tried to solve C, but get a wrong answer. Can someone help me to find why my way is wrong?

I just check whether there is difference more than 1 or there is continuous difference of 1 just like 9 8 7 ,so ,what's wrong?I can not solve it. Please.\ That's my code. int a[100000+50]; int main() { int T=1; while(T--){ int n=read(); rep(i,1,n) a[i]=read(); int flag=1; //int num=0; rep(i,1,n-1) { if(a[i]-a[i+1]>1) {flag=0;break;} if(a[i]-a[i+1]==1) { if(i<n-1) { if(a[i+1]-a[i+2]==1) {flag=0;break;} } } } if(flag) puts("Yes"); else puts("No"); } }

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

    Check if you pass:

    4
    9 8 8 7
    

    As far as I can tell your code misses the differences offset by equal values.

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

My solution for F using inclusion/exclusion and AVL tree for order statistic Code : https://atcoder.jp/contests/abc136/submissions/6742192

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

Can someone please check my code for $$$E$$$ and point out the mistake. It's failing 10 out of 84 test cases : Solution