maroonrk's blog

By maroonrk, history, 4 years 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

| Write comment?
»
4 years ago, # |
  Vote: I like it +131 Vote: I do not like it

aropan created the list. Thank you!

»
4 years 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 years 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 years 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 years 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 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    Not everything needs to be aimed at you.

    • »
      »
      »
      4 years 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 years 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 years 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 years ago, # ^ |
              Vote: I like it +16 Vote: I do not like it

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

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

How to solve A? :'(

  • »
    »
    4 years 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 years 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 years 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 years 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 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve D?

»
4 years 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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It fails on this case

    3

    2 5 7

    010

  • »
    »
    4 years 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 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Hi! I tried to solve with the same approach as yours and got AC.

      However, my first attempt was also similar: Iterate from the end and have 2 basis, one for A and for B now if any possible subset of A is not in B then ans is 1 else 0.

      Though I feel this is the same as yours I am not sure if where's my logic wrong. I'd be grateful if you help me with this. Here's my code.
      Thanks!

      UPD: Solved! I misinterpreted checking of basis A as a subset of basis B , here's my updated solution.
      Thanks adhvana!

»
4 years 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 years 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 years 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 years 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 years 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.

  • »
    »
    4 years 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 years ago, # |
  Vote: I like it +414 Vote: I do not like it

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

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

Deleted

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

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

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why not to tourist?

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

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

      • »
        »
        »
        »
        4 years 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.

  • »
    »
    4 years 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 years 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.

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

Can someone explain the solution to Problem F ? More specifically, I don't understand this part of the editorial

Eventually, we have to enumerate all i such that (D × j mod C) < (D × i mod C) for all
j < i.

Why should we do this ?