Блог пользователя maroonrk

Автор maroonrk, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +227
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +131 Проголосовать: не нравится

aropan created the list. Thank you!

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +29 Проголосовать: не нравится

* 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 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится -59 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

    Not everything needs to be aimed at you.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -54 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +30 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится -69 Проголосовать: не нравится

          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 года назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

How to solve A? :'(

  • »
    »
    4 года назад, # ^ |
    Rev. 5   Проголосовать: нравится +14 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      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 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    tldr store stuff in row echelon form

»
4 года назад, # |
  Проголосовать: нравится +195 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

How to solve D?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It fails on this case

    3

    2 5 7

    010

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +62 Проголосовать: не нравится

Thanks for the participation!

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +58 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +34 Проголосовать: не нравится

      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 года назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +414 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -31 Проголосовать: не нравится

Deleted

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Why not to tourist?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?