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

### maroonrk's blog

By maroonrk, history, 4 weeks ago, ,

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 weeks ago, # |   +131 aropan created the list. Thank you!
 » 4 weeks ago, # | ← 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 weeks ago, # |   +25 Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).
 » 4 weeks ago, # |   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 weeks ago, # ^ | ← Rev. 2 →   +3 Well, I tried them out, too ;)
 » 4 weeks ago, # |   -59 Please decrease rated bound to 690+ , it is much better . And more people will participate
•  » » 4 weeks ago, # ^ |   +37 Not everything needs to be aimed at you.
•  » » » 4 weeks ago, # ^ |   -54 So , i am the only person with that rating , i am sure there are others too. :-<>
•  » » » » 4 weeks ago, # ^ |   +30 What I meant was "not everything needs to be aimed at you beginners" (as a group).
•  » » » » » 4 weeks ago, # ^ |   -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 weeks ago, # ^ |   +16 Yeah, "beginner" is politically correct for "not good".
 » 4 weeks ago, # |   -14 Why atcoder doesn't include a problemset set section with problem tags for practice?
 » 4 weeks ago, # | ← Rev. 2 →   0 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, # |   +42 How to solve A? :'(
•  » » 4 weeks ago, # ^ | ← 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 weeks ago, # ^ |   +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 weeks ago, # ^ |   +3 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, # |   +195 Problems seem amazing as usual, but I think this contest was just too hard. Even by AtCoder standards...
 » 4 weeks ago, # |   +4 How to solve D?
 » 4 weeks ago, # |   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 weeks ago, # ^ |   0 It fails on this case32 5 7010
•  » » 4 weeks ago, # ^ |   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 basisIf 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, # |   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 weeks ago, # ^ |   +3 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, # |   +62 Thanks for the participation!I recommend reading the editorial of B, for a beautiful solution without caseworks.
•  » » 4 weeks ago, # ^ |   +58 I have no idea how to even do the naive binary search solution :(
•  » » » 4 weeks ago, # ^ |   +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.
•  » » 3 weeks ago, # ^ |   +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 weeks ago, # |   +414 Nontrivial Gauss elimination problem as problem A. Just AtCoder things.
 » 4 weeks ago, # | ← Rev. 2 →   -31 Deleted
•  » » 4 weeks ago, # ^ |   0 How did you taste the problems if you had idea of none?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Deleted
 » 4 weeks ago, # |   +15 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, # ^ |   0 Why not to tourist?
•  » » » 4 weeks ago, # ^ |   +26 I consider MiFaFaOvO as a specialist in number theory/combinatorics and techniques connected with them.
•  » » » » 4 weeks ago, # ^ |   +123 Just Joking. You can ask me i am specialist too :) Codeforces rated specialist.
•  » » » » 3 weeks ago, # ^ |   -21 I think turis is the best in that too.
•  » » 4 weeks ago, # ^ |   +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 weeks ago, # ^ |   +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 weeks ago, # ^ |   +22 I only know the same solution as Um_nik described.
•  » » » » » 4 weeks ago, # ^ |   -102 From now onwards always use #define int long long. really sorry for you