### dario2994's blog

By dario2994, history, 5 months ago,

We will hold AtCoder Grand Contest 044. This contest counts for GP30 scores.

The point values will be 400-700-1000-1100-1300-2400.

We are looking forward to your participation!

Edit: Thank you very much for your participation, I hope that you liked the problems!

First of all, congratulations to the winners:

Then, I want to say thank you to the testers dacin21, rafbill, reew2n, tempura0224 and obviously to the coordinator rng_58 who let me organize my first online contest!

Here is the editorial.

• +471

 » 5 months ago, # |   +238
•  » » 5 months ago, # ^ |   +86 I am surprised by my memory, but I am quite sure dario2994 was one of my two randomly assigned Italian roommates at Romanian Master of Mathematics 2011 xd
•  » » » 5 months ago, # ^ |   +173 Surprised by your memory? When you are given some math problem, you immediately say "yeah, it was in Mszana/Zwardon camp, year 2010, day 6 or 7... wait, I wore a black t-shirt that day so for sure day 6".Is there something you don't remember?
•  » » » » 5 months ago, # ^ |   +162 Unfortunately such scenario couldn't happen cause day 6 on Zwardon 2010 was the one I was absent on XD. I needed to come back to Warsaw cause on weekend there was an important puzzle competition for me. I do remember tasks from that day a bit, though... xD Can't quote them exactly, but I think I would recognize some of them once shown to me. First one was an easy geometry with some external angle bisector, second one was some inequality with absolute values, third one was something of type if (n+a)(n+b) is square then blah blah (they may have been swapped though), fourth one was about some balls in space xD
•  » » » 5 months ago, # ^ |   +79 I am surprised by your memory too! It's always nice to find that out that the world is not that big after all! Honestly, I could not even remember who was the other Italian in the room. But I have investigated, and it seems that Julian Demeio was the other italian in the room and he actually remembers that we were sharing the room with "someone from another team". Said that, it seems that RMM11 is a black hole of information... I could not find a single photo of that year (but I am pretty sure I took many).
 » 5 months ago, # |   0 I m able to solve only 4 problems in ABC's.should I be giving AGC?
•  » » 5 months ago, # ^ |   +5 It does not cost much to try. I can solve A sometimes, and once I solved a B.
•  » » » 5 months ago, # ^ |   +1 Can you guess the difficulty rating of Atcoder AGC A and B problems if these were CF problems(approx.)? Its my first time so I was wondering.
•  » » » » 5 months ago, # ^ |   0 All the previous agc contests are only one click away, just take a look. Link to AtCoder
•  » » » » 5 months ago, # ^ |   +6 A depends but last time when A was for 400 points the difficulty was around 1600 by codeforces standards i guess. B was 2000+ on atcoder itself so by codeforces standards i guess 2200? LOL just guesses.
•  » » » » » 5 months ago, # ^ |   0 Ok so AGC is too tough.I attended the last contest and couldnt solve one although in recent CF contests I have solved 1800-1900s easily.Its literally Div 0.5
•  » » » » » » 5 months ago, # ^ |   +34 This was a one off where even the first problem was too difficult. Usually it is quite a bit easier.
 » 5 months ago, # |   0 What are the difficulty level of the problems in AGC relative to Codeforces?
•  » » 5 months ago, # ^ |   +72 According to this comment, AGCs are equivalent to CF Div. 0.8.
•  » » 5 months ago, # ^ |   +39 About the same as the last div1 round, maybe a bit easier.
 » 5 months ago, # |   +47 No Div1 round within 10 days on CF :(
•  » » 5 months ago, # ^ |   +448
•  » » » 5 months ago, # ^ |   +1
 » 5 months ago, # | ← Rev. 2 →   +31 Awesome! I was looking forward to an AtCoder contest for ~2 months.
 » 5 months ago, # |   +174 Sad to choose between AGC and new ProjectEuler problem that is revealed an hour into the AGC.
•  » » 5 months ago, # ^ |   +627 Come on, I organized a whole AGC in order to get the "Gold Medal" award on ProjectEuler! Don't ruin my plan!
•  » » » 5 months ago, # ^ |   +225 Well played, sir, well played.
•  » » 5 months ago, # ^ |   0 What does it mean?
 » 5 months ago, # |   +31
 » 5 months ago, # |   +6 Looking forward to an amazing problemset again :)
 » 5 months ago, # |   -26 Amazing Contest !
 » 5 months ago, # |   +201 Me looking at the score distribution: "It looks like ABCDE should be doable."Also me: Solves AB
•  » » 5 months ago, # ^ |   +82 Mfw I can only solve C and spent 1 hour trying to get any ideas for AB to no avail (and get lower score than A+B T_T) :PepeHands:
 » 5 months ago, # |   +11 How to solve D?
•  » » 5 months ago, # ^ |   +5 Perform a query of $c*L$ for each character $c$ to find the number of its occurrences in the password (hence the password length) For each position, perform a query $BB...BAB...B$ to determine the location of all $A$. Do binsearch on the empty positions, using $A$ as filler.
•  » » » 5 months ago, # ^ |   +35 Instructions unclear, d*ck stuck in the compiler
•  » » 5 months ago, # ^ |   +38 You can find number of each characters in the string in $62$ queries. After that you have $62$ subsequences, you can merge 2 of them in sum of their length operations. Do divide and conquer. It will work in $n \log(62) = 6n$.
 » 5 months ago, # |   +271 4 years ago: "Problem with 2x points on AtCoder should be at the same level difficulty as problem with x points on TopCoder"Nowadays 500pts TopCoder: "You are given A and B, return A+B"Nowadays 1000pts AtCoder: "Determine whether P=NP"
 » 5 months ago, # |   +143 A looks like an observation problem, can anyone explain what we were supposed to observe?
•  » » 5 months ago, # ^ |   -32 Nothing. At least something like $O(\log^3n)$ dp solution does not require much thinking.
 » 5 months ago, # | ← Rev. 2 →   +49 I hope you have liked the problems! During the contest, thanks to a participant with a very good memory, we discovered that D was given in a USACO stage (but it is not online) and E (in a simpler version) was USACO 2018, Platinum, December. We are sorry for that, hopefully not too many participants had seen them (and for problem E, hopefully it was not trivial to deduce the solution for the current version).
•  » » 5 months ago, # ^ | ← Rev. 2 →   +68 On my planet the search for solution of A continues...
•  » » » 5 months ago, # ^ |   0 YA AGCs are too awesome even I was also pondering of how to solve A. And also I think now that I am over-rated!
•  » » » » 5 months ago, # ^ |   0 I have the same feelings with you.
•  » » 5 months ago, # ^ |   +13 I gave a problem very similar to D in my Petrozavodsk contest in 2015. Liked all the problems, especially C!
•  » » 5 months ago, # ^ |   +3 IMO E is infinitely harder than that USACO problem and it's just unrelated (I'd like to be proven wrong though)
•  » » » 5 months ago, # ^ |   +28 I strongly disagree with "it's just unrelated", but yes E is harder than that USACO problem and it might be that knowing the solution to the USACO was less than "half the problem". If you take a look at the editorial, you will see that the key-idea is fundamentally the same: it's a well-hidden convex-hull (here well-hidden, in the USACO problem not so well-hidden).In the continuous version (as described in the editorial), the similarity is more clear. Both problems are "obstacle problems" but in the USACO problem the obstacle was given in input, in problem E you have to compute the obstacle.
•  » » 5 months ago, # ^ |   0 https://codeforces.com/problemset/problem/1282/Dsimpler version of D is also given here
•  » » » 5 months ago, # ^ |   0 This did not help.
•  » » 5 months ago, # ^ |   +44 It's a pity that some people were familiar with a problem or two, but the contest was still amazing!
•  » » » 5 months ago, # ^ |   +14 I also said that the contest is amazing hereThen why i got too many downvotes ? where as for the same comment, you got upvotes.
•  » » » » 5 months ago, # ^ |   +15 It's called ratism!
•  » » » » 5 months ago, # ^ |   +61 Maybe because your rating doesn't really match participating in AGC so people thought you didn't even participate. Idk.
 » 5 months ago, # |   +4 How to solve A?
•  » » 5 months ago, # ^ |   +3
•  » » » 5 months ago, # ^ |   -10 care to use more words please!
•  » » » 5 months ago, # ^ |   +42 How to analyze the time complexity tho?
•  » » » » 5 months ago, # ^ |   +16 editorial has explained this clearly!
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +54 Claimthe number will always be one of the following form1.floor(n/(2^a*3^b*5^c)) 2.ceil(n/(2^a*3^b*5^c)) Proofthese are 2 well known identities 1.floor(floor(x/a)/b)=floor(x/ab) 2.ceil(ceil(x/a)/b)=ceil((x/ab)floor(x/ab)=floor(floor(x/a)/b)<=floor(ceil(x/a)/b)<=ceil(ceil(x/a)/b)=ceil(x/ab) note the difference between the leftmost and rightmost term is at most one hence floor(ceil(x/a)/b) is always either equal to floor(x/ab) or ceil(x/ab) similarily ceil(floor(x/a)/b) is always either equal to floor(x/ab) or ceil(x/ab)now the proof can be completed by induction
•  » » 5 months ago, # ^ |   0
 » 5 months ago, # | ← Rev. 4 →   0 So I used a graph approach to try to solve B. Basically the graph is a interconnection of points that are adjacent to each other AND are also empty.So for each element in the array p: I mark p[i] as empty. I check if any of the adjacent sides of p[i] is empty, if yes i make an edge. I mark dist=INF and call dfs at p[i]. In dfs I have a statement dist = min(dist,close[v]). close[v] is the closest v is to any square side. Finally i do answer+=dist Am i missing something here? Because I keep getting WA for some of the test cases
 » 5 months ago, # |   +233
 » 5 months ago, # |   0 Can someone explain in detail how to solve A and B?
•  » » 5 months ago, # ^ |   0 Check the editorials.
 » 5 months ago, # |   0 Can any help me know where my approach fails? Or provide me the last test cases? problem B-jokerhttps://atcoder.jp/contests/agc044/submissions/13547183
 » 5 months ago, # |   0 Editorial is out!
 » 5 months ago, # |   0 Auto comment: topic has been updated by dario2994 (previous revision, new revision, compare).
 » 5 months ago, # |   0 How can we see submissions of others in AtCoder?
•  » » 5 months ago, # ^ |   0 Click on details.
 » 5 months ago, # | ← Rev. 5 →   0 Can somebody please point out what's wrong with my solution for A? It is passing every test case except 007.txt.hm is a map for storing dp values Link for Solution long recur(long n,long a,long b,long c,long d){ if(n==0) return 0L ; if(hm.containsKey(n)) return hm.get(n); long ans = Long.MAX_VALUE ; ans = Math.min(recur(n/2,a,b,c,d)+a+(n%2)*d,ans); ans = Math.min(recur(n/3,a,b,c,d)+b+(n%3)*d,ans); ans = Math.min(recur(n/3 +1 ,a,b,c,d)+b+(3-n%3)*d,ans); ans = Math.min(recur(n/5,a,b,c,d)+c+(n%5)*d,ans); ans = Math.min(recur(n/5 +1 ,a,b,c,d)+c+(5-n%5)*d,and); if( n*d > 0){ // This is for Overflow check of long ans = Math.min(ans,n*d); } hm.put(n,ans); return ans ; } 
•  » » 5 months ago, # ^ |   +19 I believe you should also be able to divide by 2 and round up? If N=31, A=1, B=C=D=100, the result should be 205.
•  » » » 5 months ago, # ^ | ← Rev. 3 →   0 Yes I noticed my mistake in the contest. Problem with that is when I call for (n/2 + 1) and when n is 2 it will again call 2/2 +1 = 2, So the problem wasn't reduced into smaller problem. That's why then I tried to solve n==2 using every possible option of a,b,c,d using this code long ansFor2 = Math.min(a,2*d); ansFor2= Math.min(ans2,b+d); ansFor2= Math.min(ans2,c+3*d); hm.put(2L,d+ansFor2); But then I don't know even what's the best answer for n=3 and n=5 which eventually depends on n=2 too. So I am now confused. Then I tried sorting a,b,c, and claimed that smallest among a,b,c. won't depend on other options except for d.Edit: I added the above code and then submitted but then it passed for 007.txt but failed for 001.txt
•  » » » » 5 months ago, # ^ |   +1 Math.min(a, d);Or in the recurrence, if N=2, you may simply ignore the option (N/2+1) as it doesn't help you at all.
•  » » » » » 5 months ago, # ^ |   +5 I am stupid, Thanks It Worked! AC! Struggled whole contest!
 » 5 months ago, # |   +21 I think second place is actually MiFaFaOvO.
•  » » 5 months ago, # ^ |   0 Thanks, fixed.
•  » » 5 months ago, # ^ |   +56 That guy is so confusing.
 » 5 months ago, # | ← Rev. 3 →   -98 Just curious: why make a separate website? It could have been great to integrate UI and community features of Codeforces with problem quality of AtCoder. See: everyone has to discuss the problems on Codeforces, since AtCoder doesn't have community tools.
•  » » 5 months ago, # ^ | ← Rev. 4 →   -10 Your world is too simple!
•  » » 5 months ago, # ^ |   +2 I don't think problem quality of Codeforces is much worse than AtCoder's!
•  » » 5 months ago, # ^ |   +42 They have separate employees, rules and sponsors.
 » 5 months ago, # | ← Rev. 2 →   +27 Did anyone solve C in $O(3^{N/2} |T|)$ and was it intended ? I used a meet in the middle strategy : using bruteforce to calculate the first N/2 digits, and changing the last N/2 digits lazily.Here is the implementation : https://atcoder.jp/contests/agc044/submissions/13545845EDIT : fixed a typo in the complexity.
•  » » 5 months ago, # ^ |   0 I also used meet-in-the-middle with my solution (though I did something more sophisticated but did not end up computing stuff lazily).
•  » » » 5 months ago, # ^ |   +16 For those that are curious, here is the idea :I will calculate for each danser, the value of it's first $N/2$ digits in base 3, and the last $N/2$ digits (the prefix, and the suffix). To update the prefixes, it can be done in $O(3^{N/2})$ at each step by bruteforce easily. To take care of the suffixes, I keep track of $\text{current_suffix}_i$ for all $0\le i< 3^N$. Initially, $\text{current_suffix}_i = E(i/3^{N/2})$. When doing a salsa, remember lazily that a salsa has to be done by maintaining the parity of the number of salsas done so far for each danser, and the parity of the salsas seen before. When doing a rumba, one can notice that exactly one of the $3^{N/2}$ prefixes will overflow and need to modify the suffixes of the dansers with that prefix. So you just need to update the $3^{N/2}$ corresponding suffixes.
 » 5 months ago, # | ← Rev. 2 →   +31 Here's my strange solution for E (I got AC after the contest).If we know the set of stopping positions, for every two consecutive of them, say $L$ and $R$, we need to add something to the answer (contribution from interval from $[L, R]$). If you play with EV equations, it turns out we need this sum: $f(L, R) = \sum_{i=L+1}^{R-1} (i - L) \cdot (R - i) \cdot cost_i \cdot constant$This can be computed in $O(1)$ after we compute prefix sums of $cost_i$ and $i \cdot cost_i$ and $i^2 \cdot cost_i$, a quite standard trick.Now, since there is some solution with convex hull (source: editorial says so), a stack will work as well here, even if I don't figure out the points for convex hull. If three last indices on the stack are currently $A, B, C$, we pop $B$ only if $f(A,B) + f(B,C) < f(A, C)$.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +41 After a discussion with tourist, I came to the following understanding that explains why this and many other solutions should work:Suppose answer is $e_i$, and obviously $e_i \ge a_i$. Let's start with declaring all positions to be stopping, and then while there is a position that we can flip to non-stopping and improve the answer, do it. When all remaining stopping positions are "locally optimal", we have our answer. We can do it using the stack you describe, but we can really repeatedly take any non-optimal stopping position and making non-stopping.The reason this works is: Since $e_i \ge a_i$, if the position is non-optimal to be stopping now, it will be even more non-optimal to be stopping if we make some other stopping positions non-stopping. So we can always make any flips that are locally optimal. When there are no more locally optimal flips remaining, then the argument works in the other direction: if the answer corresponding to the current state is $f_i$, then we can prove by induction that no matter what further flips we're going to make, the answer for each vertex will always stay as $\le f_i$. (this is a bit shaky and informal)
 » 5 months ago, # | ← Rev. 3 →   +72 My solution to C:Split each number $i \in [0, 3^n - 1]$ into two parts: the least significant digit ($d_i$) and everything else ($h_i$).We see that: any operation of type S changes $d_i=1$ into $d_i=2$ and vice versa, and applies S to $h_i$; any operation of type T changes $d_i$ into $(d_i+1)\mod3$; if $d_i=2$, we also apply T to $h_i$. Also, we can assume that a sequence of operations $t$ never contains a substring SS (otherwise we can erase it without changing the result).Moreover, we can deduce the $k$ least significant digits of the number after all the transformations from $k$ least significant digits of the initial number.We write a recursive function $Rec(d_0, d_1, \dots, d_{k-1}, e_0, e_1, \dots, e_{k-1}, t)$ that solves the problem for each number with $k$ fixed least significant digits $d_0$ till $d_{k-1}$ (which were transformed by the operations into $e_0$ till $e_{k-1}$), and a sequence of operations $t$ that we have to apply to the remaining most significant digits. If $k=n$, we're done; otherwise, for each least significant digit $d_k \in {0, 1, 2}$, we compute the resulting least significant digit $e_k \in {0, 1, 2}$ and a sequence of operations $t_{d_k}$ that we have to apply to the most significant digits (as above). Then we call $Rec(d_0, d_1, \dots, d_k, e_0, e_1, \dots, e_k, t_{d_k})$.Why is it fast enough? Each T within any $t$ received in a recursive call is then moved to exactly one of $t_0, t_1, t_2$. Therefore, for each $k$, total number of T's throughout all recursive calls is at most $n$. Furthermore, if any sequence $t$ contains $x$ T's and no substring of form SS, it has at most $2x + 1$ elements. Hence, all sequences of operations in all recursive calls are short in total.My code: here.
 » 5 months ago, # |   +15 My screencast, fast A and B, then mainly trying to solve E and adding some heuristics at the end https://www.youtube.com/watch?v=GWJo17kmZGc
•  » » 5 months ago, # ^ |   0 I tried to do a dijkstra like search for problem A, but i did not know how to escape from overflow. After i saw your approach i tried to use it with my solution, but i'm not able to make my solution pass the test:1 29384293847243 454353412 332423423 934923490 1Correct answer: 3821859835My answer: 3821859837After hours trying to make it, i came here asking for help. Here is my submission: https://atcoder.jp/contests/agc044/submissions/13553853
•  » » » 5 months ago, # ^ |   +1
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   0 Thank you very much. I was so angry with problem B that i could not find my wrong usage of % operator.
 » 5 months ago, # |   +2 In problem D why replacing thiscout << "! " << rec(0, m - 1) << endl; to thisstring ans = rec(0, m - 1); cout << "! " << ans << endl; change something?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +18 In function rec you ask some questions that contains stdin/stdout stuffs. This lead to wrong format
 » 5 months ago, # |   +21
 » 5 months ago, # |   +8 Is the "naively" in solution C serious? It's too dangerous :)
 » 5 months ago, # |   0 Hi! Is AtCoder working for anyone? It hasn't been working for me since the past 2 days.
•  » » 5 months ago, # ^ |   0 why the hell you even asked this question after seeing this blog? Means it's pretty clear at least this many people gave contest implies obv. atcoder is working for them
•  » » » 5 months ago, # ^ |   +3 Ok, i thought that since the blog post was from 44 hrs ago, it might've been working then and not now. Seems I'm the only one.
 » 5 months ago, # |   +70 Thank you for your great contest, dario2994. The problems are very interesting (and harder than usual), and your editorial is easy to understand. I'd like you to know that a lot of people praised the contest also in Japanese SNS communities. Thanks!
 » 5 months ago, # |   0 Thanks very much for the illuminating problems, and the organization for such a big contest.There is one thing I am concerning about, however. The problem D is an interactive problem, which requires the interaction between the participant's program and a standard program(for example, read the queries, calculate the edit distance and return). To work on this problem, if we want to debug such a program, we can first run on a small alphabet and small length, first setting a password and responding to every query by calculating by hand. However, it will cost much time and cannot be applied for larger data sets.I am wondering if an interactive program should be provided for problems like D. Maybe it can just be run by an argument for an executable file compiled from the participant's code, and another argument for a password(or a file including the password) as input. Or just a program with two executable files and one password file as arguments, while both the guessing and responding executable file written by participants. By run such an assistant program one can easily debug their own programs.I admit that we can prepare this kind of interactive program(at least for the second kind) before the contest, which can be considered as a part of ability, but I am not sure whether such preparation should be considered in such a contest. Also, for the people to take these problems as an exercise after the contest, this kind of program will also be very helpful.
 » 5 months ago, # |   +10 I don't understand the complexity analysis of problem B-Joker. I get the idea that the sum of all initial minimal distance is bounded above by N^3. However, I still cannot understand why the total number of visited nodes in bfs is bounded by N^3. Someone please help me. Sorry for my bad English.
•  » » 5 months ago, # ^ |   +18 Your english is not bad!When the bfs visits a node, the distance from that node to the outside of the cinema decreases by 1. Hence, if the initial distance of a node is $D$, you can visit that node only $D$ times (because each time its distance to the outside decreases by 1 and it cannot become negative). Therefore, the total number of visited nodes is not more than the sum of the initial distances -> $O(N^3)$.
•  » » » 5 months ago, # ^ |   0 Oh I see. Thanks for fast reply.
 » 3 months ago, # |   0 I have a confusion... Is there any difference between the two output ways? `string ans=solve(0,61); cout<<"! "<