Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

maroonrk's blog

By maroonrk, history, 4 weeks ago, In English,

We will hold AtCoder Grand Contest 045. This contest counts for GP30 scores.

The point values will be 400-800-800-1200-1200-1800.

We are looking forward to your participation!

P.S. The AtCoder Race Ranking can be found here. I don't know who created this list, but I'd like to say thank you to them.

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

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

aropan created the list. Thank you!

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

* Rated range: 1200 ~

The site says it is rated for all. So which one is true?

UPD: Just refreshed the site and it says rated range 1200 ~

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

Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).

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

It's the first ever contest on AtCoder, having a lower-bound on the Rated Range.

Nice.

Though, it will be unrated for me, I am excited to try out the problems.

Thanks!

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

Please decrease rated bound to 690+ , it is much better . And more people will participate

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

    Not everything needs to be aimed at you.

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

      So , i am the only person with that rating , i am sure there are others too. :-<>

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

        What I meant was "not everything needs to be aimed at you beginners" (as a group).

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

          What do you mean by a beginner , i started Programming , 11 months ago .

          You can't categorize me as a beginner . I am experienced , just not being able to solve some problem (Other's Idea ) doesn't mean my ideas are weak .Some day, i will improve.

          Btw ,i got what you want to say , unofficial participation will also be great for us to improve. Thx

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

            Yeah, "beginner" is politically correct for "not good".

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

Why atcoder doesn't include a problemset set section with problem tags for practice?

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

What is the equivalent rating of 1200 Atcoder rating in Codeforces and also what are the rating of problems in terms of A,B,C,D in AGC?

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

How to solve A? :'(

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

    First refer to the editorial, but note that the DP sets could be exponential in size if stored explicitly. It doesn't give much details as to how to solve this subproblem except for a mention of "maintaining the basis".

    It refers to the concept in linear algebra. In other words, we want to somehow maintain a small-enough subset $$$B \subseteq DP_i$$$ such that we can easily check that $$$x \in DP_i$$$ by xor-summing a subset of $$$B$$$.

    This is possible, because if $$$a \in DP_i$$$ and $$$b \in DP_i$$$, then $$$a \oplus b \in DP_i$$$.

    What if we stored $$$B$$$ as an array of $$$60 = \lfloor \log_2 \max A_i \rfloor + 1$$$ integers with the following rule:

    • If there exists a number in $$$DP_i$$$ such that its $$$j$$$-th least significant bit is $$$1$$$ and all bits lower than the $$$j$$$-th are $$$0$$$, $$$B[j]$$$ should be set to one of those numbers, otherwise $$$B[j] = 0$$$.

    Then we can easily check for membership in $$$DP_i$$$ by the following algorithm:

    • If $$$x = 0$$$, $$$x \in DP_i$$$. (cause $$$0$$$ is always in $$$DP_i$$$ as long as we're "alive")
    • Otherwise let $$$j$$$ be the index of $$$x$$$'s least-significant $$$1$$$-bit.
    • If $$$B[j] = 0$$$, $$$x \notin DP_i$$$, because we cannot flip the $$$j$$$-th bit without affecting lower bits.
    • Otherwise $$$x \in DP_i \iff x \oplus B[j] \in DP_i$$$, so do $$$x := x \oplus B[j]$$$. The algorithm is guaranteed to terminate because the new $$$x$$$ is either $$$0$$$ or has a greater number of trailing zeros.

    Now the final step is to figure out what to do if $$$x \notin DP_i$$$. If $$$S_i = 1$$$, we report a player $$$1$$$ win. Otherwise we want to expand the set for $$$DP_{i-1}$$$; it suffices simply to set $$$B[j]$$$ to the final value of $$$x$$$.

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

      Thanks a lot, man! Though I somehow managed to solve the question in contest by copy-pasting code from the blog, your explanation gave me a wonderful conceptual clarity!

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

    There's a good tutorial on xor basis in https://codeforces.com/blog/entry/68953 and https://codeforces.com/blog/entry/60003.

    tldr store stuff in row echelon form

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

Problems seem amazing as usual, but I think this contest was just too hard. Even by AtCoder standards...

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

How to solve D?

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

How to solve A? I had following idea — Find basis of both list and check if for each element of 2nd basis there exist a subset with xor sum equal to that element using 1st basis? Sadly, I cannot find any test or flaw in this solution

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

    It fails on this case

    3

    2 5 7

    010

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

    Answer is 0 only if somehow player 0 can construct every number player 1 can construct.

    It is enough if player 0 can construct every number player 1 has after player 1 plays it.

    So for every number belonging to player 1 (say $$$x$$$), find basis of all numbers by player 0 occurring after this position and check if $$$x$$$ belongs to the span of this basis

    If you iterate in reverse, you can maintain the basis of numbers of player 0 and check this in $$$\mathcal{O}(N\log A)$$$ total.

    I referred this blog for basis calculation

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

Why can't A be solved using Gaussian Elimination? Find the basis vector of both player 0 and player 1, and then find if basis of player 1 is a subset of bases player 0?

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

    If the last number belongs to player 1, he wins regardless. You need to build the list iteratively starting from the end.

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

Thanks for the participation!

I recommend reading the editorial of B, for a beautiful solution without caseworks.

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

    I have no idea how to even do the naive binary search solution :(

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

      Let's say we want to check if $$$Answer \leq V$$$ for some $$$V$$$.

      An $$$O(VN)$$$ solution is like: $$$dp[i][j]=$$$ is it possible to have the prefix sum of first $$$i$$$ numbers = $$$j$$$? We let $$$dp[0][j]=$$$ true for all $$$0 \leq j \leq V$$$, so that we need to consider only $$$0 \leq j \leq V$$$ for all $$$i$$$.

      If we fix the parity of $$$j$$$, we can see that $$$j$$$s such that $$$dp[i][j]=true$$$ for some $$$i$$$ form a range. This allows us to speed up the above DP to $$$O(N)$$$ time.

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

    I think conceptually my solution is even simpler. The basic idea is to find a good lowerbound. Two obvious lower bounds are the maximum subarray sum (when we consider zeros and question marks as $$$-1$$$) and the absolute value of the minimum subarray sum (when we consider zeros as $$$-1$$$ and question marks as $$$+1$$$). It turns out that the highest of these lower bounds is nearly always attainable, except in the case when there are two places with different parity that provide the same lower bound (it is easy to see that this lower bound is not attainable in this case); in that case our answer will be exactly one higher.

    So the final solution is just to run Kadane's algorithm twice, keep track of the lower bounds for each parity, and return the answer as described above (with a single if).

    During the contest, my proof of the claim above was a bit shaky, so I also wrote a quick stress test to verify it, but the 'real code' is pretty short (only the solve method).

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

Nontrivial Gauss elimination problem as problem A. Just AtCoder things.

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

Deleted

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

Just upsolved F and I have a question to experienced guys like MiFaFaOvO.

Let's consider this problem: Given $$$R, A, P$$$ (let's assume that $$$P$$$ is prime, but whatever) find a minimum value of $$$(A \cdot x) \mod P$$$ for $$$x \in [1, R]$$$. This one is easy, we start with $$$min=1$$$ and $$$max=1$$$, then consider $$$x=min+max$$$ and check whether for this $$$x$$$ the value of $$$(A \cdot x) \mod P$$$ is a new minimum or a new maximum. Then do transitions like $$$min+=max$$$ or $$$max+=min$$$ and we do a small speed up to skip arithmetic sequences where nothing overflows (bad explanation but you probably know what I'm talking about).

What about minimizing $$$(B + A \cdot x) \mod P$$$? Or alternatively, $$$x \in [L, R]$$$ (the same problem). Is there any solution that is as easy as the one mentioned?

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

    Why not to tourist?

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

      I consider MiFaFaOvO as a specialist in number theory/combinatorics and techniques connected with them.

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

        Just Joking. You can ask me i am specialist too :) Codeforces rated specialist.

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

        I think turis is the best in that too.

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

    I don't know about "as easy" (I don't understand your solution tbh), but yes, this problem is solvable.

    //	finds min k s.t. L <= (k * A) % M <= R (or -1 if it does not exist
    ll solve4(ll A, ll M, ll L, ll R) {
    	if (L == 0) return 0;
    	A %= M;
    	ll ans = 0;
    	ll s1 = 1, s2 = 0;
    	while(A > 0) {
    		if (2 * A > M) {
    			A = M - A;
    			L = M - L;
    			R = M - R;
    			swap(L, R);
    			ans += s2;
    			s1 -= s2;
    			s2 *= -1;
    		}
    		ll ff = (L + A - 1) / A;
    		if (A * ff <= R) return ans + ff * s1;
    		ans += (ff - 1) * s1;
    		ff = (ff - 1) * A;
    		L -= ff;
    		R -= ff;
    		ll z = (M + A - 1) / A;
    		s2 = s1 * z - s2;
    		swap(s1, s2);
    		M = z * A - M;
    		swap(A, M);
    	}
    	return -1;
    }
    

    It is not exactly what you wanted, but we can continue the search (with smaller right bound) after we have found minimal $$$k$$$.

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

      I've meant something like this:

      ll solve(ll A, ll M, ll R) {
      	ll low = 1;
      	ll high = 1;
      	ll val_low = A;
      	ll val_high = A;
      	while(low + high <= R && val_low) {
      		if (val_low + val_high < M) {
      			ll count = min((M - val_high - 1) / val_low, (R - high) / low);
      			val_high = (val_high + val_low * count) % M;
      			high += low * count;
      		} else {
      			ll count = min(val_low / (M - val_high), (R - low) / high);
      			val_low = (val_low + val_high * count) % M;
      			low += high * count;
      		}
      	}
      	return val_low;
      }
      

      I like it because it's easy to understand. Anyway thanks, I'll parse yours.