We will hold AtCoder Regular Contest 177.
- Contest URL: https://atcoder.jp/contests/arc177
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240512T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: E869120, square1001
- Tester: maspy
- Rated range: — 2799
The point values will be 300-400-500-700-1000-1000.
We are looking forward to your participation!
May be this contest should be held on another day.
It's awful that having an "Earthquake" problem on exactly 12th May.
I feel sorry about it. I'm afraid didn't know the exact date of that earthquake...
For Earthquakes problem, I figured out that we need to solve it by considering connected components and that the ways to collapse could be only of the form LLL...RRR so I thought of calculating this using a stack. But, I am still confused how to merge the results for each components, can someone explain it?
Let $$$F(i, t)$$$ be the probability of the entire $$$i$$$-th connected component collapsing before or at time $$$t$$$. Of course, at each time $$$t$$$ from $$$1$$$ to $$$N$$$, at most one connected component's probability can change.
So, you can sweep over the time $$$t$$$ from $$$1$$$ to $$$N$$$, and maintain the product of $$$F(i, t)$$$ for all $$$i$$$. This can be done with a segment tree or just simply maintaining the product (to handle the case where there are zero values, just keep track of the number of zeros to avoid division by zero).
For problem E, we can use another type of sort to reduce the time complexity to $$$O(113TV+113N)$$$ where V is the max possible value of adding all the scores
Today's problems were really enjoyable! (The jump from C to D was higher than I expected, though.)
Unfortunately, I wasted almost an hour trying to solve a misread version of problem D (which turned out to be much harder than the actual problem).... 😅
I forgot to set my alarm, so I woke up after the contest ended, and lost 39 rating points :(
In problem E, if we let f[3]=2, f[4]=8, f[5]=113, what will the asymptotic behavior of f[n] be like?
The 8 candidates when there are 4 problems:
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 2
1 1 2 3
1 1 2 4
1 2 2 3
1 2 3 4
Because the number of possible combinations will be O(3^(n^2-n)/(2^(n-1)*(n-1)!)) (which will be impossible for brute force computation when n>10,), we need some other algorithm for computing larger f[n].
I have the result that there are $$$11219$$$ patterns to be considered for $$$6$$$ problems case. I ran the following C++ program for half an hour. In this case, the maximum point value was $$$30$$$.
Computing $$$f_7$$$ seems difficult. Did anyone try it?
Sad feelings about today's problem D. I failed to solve it because I didn't believe it's possible for probability of a certain group to be
0modulo998244353. Lack of math knowledge led to correct solution failed two test cases :( But liked first 4 problems in general.Me too, I was almost solved the problem D during contest but keep getting 2 WA on in19 and in20. If I solved this, it would be the first time I entered top 200 in ARC.
Is this (having 0 modulo 998244353) really likely to happen sometime or they handmade two testcases for this bug? Is the probability MOD/N?
I guess problem-setters intentionally made one small and one large tests with such values. I wouldn't say it was a bug. It was more like: my (non-existing) math knowledge tells me that probabilities will never be zero modulo large prime number, so I won't even bother handling that case. The statement was wrong, obviously. Funny, but it was about just a couple more if-statements to be added, but for some reason I didn't try it during the contest. Painful, but very important lesson.
Math knowledge tells us that products of non-zeros will be non-zero, not sums of non-zeros or products of anything. As I mention below, you shouldn't handle this just with a couple if-statements but with different representation.
Unfortunately, math knowledge doesn't tell me anything if it's simply not here :(
By a couple of if-statements I meant specifically handling zero-sums separately and not letting them to the product. Actually, the same idea is also suggested in the official AtCoder editorial. In my accepted code it literally looks like two-ish if-statements.
In this case, when the result is a product of $$$G$$$ sums, then assuming the data is sufficiently mixed that the sums are uniformly distributed, the probability that none are zero is $$$(1-1/MOD)^G \approx 1-G/MOD$$$, so it's not very likely to turn out zero by coincidence.
However, when the result is a product of sums, we should assume that it's possible. It doesn't even need extra special effort, the sums are 0 at the start! We can write code naturally to express the result as $$$0^k \cdot p$$$ with $$$p \neq 0$$$, and update $$$k$$$ and $$$p$$$ when a sum changes.
Most of the time, the result is a product of very few variables, so we tend to calculate results by multiplying new values of those variables instead of always calculating their modular inverses. In that case, it can still end up zero, it's just not visible as a source of bugs.
It doesn't even need extra special effort, the sums are 0 at the start!Unfortunelly, me (and I think) and other people who made this mistake printed 0 until all poles can actually fall, and then started calculating when we don't have any real 0 (the ones that are 0 without mod).
Now I can see why this was just a lazy way solving this corner case.
Well, actually the wrong assumption was that the sum of non-zero number of fractions $$$\frac{1}{2^{d_{i}}}$$$ modulo large prime number is never
0. This is why we handled zero number of addends separately. Not as lazy as it seems :)Us bro. It took me a lot of WA and RTE to figure out this case. Apparently people who directly bashed DS didn't had to handle to this case separately.
Why nobody is talking about question C? It was quite a jump from B to C
Maybe because it only require to observe independence? there is not much we can discuss about.
I guess you meant that problem B was easier than usual. Problem C wasn't difficult at all and required the only observation:
We can solve this problem for red and blue cells independently and sum up the answers after. It can be proven by the following logic:
For the red path we need only some of the blue cells to be colored purple.
For the blue path we need only some of the red cells to be colored purple.
Thus sets of cells colored purple for these phases will never intersect.
Implementation is quite straightforward and requires only graph theory basics:
For problem E, I saw another idea from submissions:
With 5 questions, there are
2^5different results if not considering penalties. Now consider the vectorrank[2^5]representing the rank distribution of the2^5result, whererank[mask] = the final rank (allowing tie) of mask result in all 2^5 different results. If we have all possible rank distributions, then we can just iterate through them on the input and find the minimum total squared error.Then let's brute force search for all possible rank distributions. I don't know if it's derived by trial and error, or by some math calculation, but it seems that you can get all possible rank distributions (
4672of them) when trying all possible score distributions where score of each question is <=30. This method passes the time limit.apiad's submission in the live game looks similar to the above method, but with 2 improvements:
Use randomization to get candidate rank distributions. Their randomization generates
4649unique rank distributions, which even though is not all (4672) but good enough, since we know from the editorial that only113of them are critical.Reduce the candidates rank distributions. The idea is that, for a rank distribution, if you can merge results of neighboring ranks into the same rank, you should do it, as it won't make the total squared error worse. If we use the terms from the official editorial, this is the process of reducing spaces (
# = 4672) divided by hyperplanes to intersections (# = 113) of hyperplanes.(I don't feel very confident in my interpretation. Let me know if I get any part of them wrong)