We will hold AtCoder Grand Contest 045. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc045
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200607T2100&p1=248
- Duration: 150 minutes.
- Number of Tasks: 6
- Writer: maroonrk
Rated range: 1200 ~
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.
aropan created the list. Thank you!
The site says it is rated for all. So which one is true?
UPD: Just refreshed the site and it says rated range 1200 ~
Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).
It's the first ever contest on AtCoder, having a
lower-bound
on theRated Range
.Nice.
Though, it will be unrated for me, I am excited to try out the problems.
Thanks!
Well, I tried them out, too ;)
Please decrease rated bound to 690+ , it is much better . And more people will participate
Not everything needs to be aimed at you.
So , i am the only person with that rating , i am sure there are others too. :-<>
What I meant was "not everything needs to be aimed at you beginners" (as a group).
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
Yeah, "beginner" is politically correct for "not good".
How to solve A? :'(
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:
Then we can easily check for membership in $$$DP_i$$$ by the following algorithm:
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$$$.
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!
There's a good tutorial on xor basis in https://codeforces.me/blog/entry/68953 and https://codeforces.me/blog/entry/60003.
tldr store stuff in row echelon form
Problems seem amazing as usual, but I think this contest was just too hard. Even by AtCoder standards...
How to solve D?
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
It fails on this case
3
2 5 7
010
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
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 forB
now if any possible subset ofA
is not inB
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 basisB
, here's my updated solution.Thanks adhvana!
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?
If the last number belongs to player 1, he wins regardless. You need to build the list iteratively starting from the end.
Thanks for the participation!
I recommend reading the editorial of B, for a beautiful solution without caseworks.
I have no idea how to even do the naive binary search solution :(
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.
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).
Nontrivial Gauss elimination problem as problem A. Just AtCoder things.
Deleted
How did you taste the problems if you had idea of none?
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?
Why not to tourist?
I consider jqdai0815 as a specialist in number theory/combinatorics and techniques connected with them.
Just Joking. You can ask me i am specialist too :) Codeforces rated specialist.
I don't know about "as easy" (I don't understand your solution tbh), but yes, this problem is solvable.
It is not exactly what you wanted, but we can continue the search (with smaller right bound) after we have found minimal $$$k$$$.
I've meant something like this:
I like it because it's easy to understand. Anyway thanks, I'll parse yours.
I only know the same solution as Um_nik described.
Can someone explain the solution to Problem F ? More specifically, I don't understand this part of the editorial
Why should we do this ?