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

- Contest URL: https://atcoder.jp/contests/agc044
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200523T2100&p1=248
- Duration: 150 minutes
- Number of Tasks: 6
- Writer: dario2994
- Rated range: All

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.

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

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?

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

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).

I m able to solve only 4 problems in ABC's.

should I be giving AGC?

It does not cost much to try. I can solve A sometimes, and once I solved a B.

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.

All the previous agc contests are only one click away, just take a look. Link to AtCoder

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.

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

This was a one off where even the first problem was too difficult. Usually it is quite a bit easier.

What are the difficulty level of the problems in AGC relative to Codeforces?

According to this comment, AGCs are equivalent to CF Div. 0.8.

About the same as the last div1 round, maybe a bit easier.

No Div1 round within 10 days on CF :(

Unfortunately there wont be any D1 contest in next 7 days . . .

Awesome! I was looking forward to an AtCoder contest for ~2 months.

Sad to choose between AGC and new ProjectEuler problem that is revealed an hour into the AGC.

Come on, I organized a whole AGC in order to get the "Gold Medal" award on ProjectEuler! Don't ruin my plan!

Well played, sir, well played.

What does it mean?

I think the problems will be super awesome!

Looking forward to an amazing problemset again :)

Amazing Contest !

Me looking at the score distribution: "It looks like ABCDE should be doable."

Also me: Solves AB

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:

How to solve D?

Instructions unclear, d*ck stuck in the compiler

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$$$.

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"

A looks like an observation problem, can anyone explain what we were supposed to observe?

Nothing. At least something like $$$O(\log^3n)$$$ dp solution does not require much thinking.

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).

On my planet the search for solution of A continues...

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!

I have the same feelings with you.

I gave a problem very similar to D in my Petrozavodsk contest in 2015. Liked all the problems, especially C!

IMO E is infinitely harder than that USACO problem and it's just unrelated (I'd like to be proven wrong though)

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.

https://codeforces.com/problemset/problem/1282/D

simpler version of D is also given here

This did not help.

It's a pity that some people were familiar with a problem or two, but the contest was still amazing!

I also said that the contest is amazing here

Then why i got too many downvotes ? where as for the same comment, you got upvotes.

It's called ratism!

Maybe because your rating doesn't really match participating in AGC so people thought you didn't even participate. Idk.

How to solve A?

dp+greedy. https://atcoder.jp/contests/agc044/submissions/13539933

care to use more words please!

How to analyze the time complexity tho?

editorial has explained this clearly!

Claimthe number will always be one of the following form

1.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

https://atcoder.jp/contests/agc044/submissions/13548393

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:

Am i missing something here? Because I keep getting WA for some of the test cases

Can someone explain in detail how to solve A and B?

Check the editorials.

Can any help me know where my approach fails? Or provide me the last test cases? problem B-joker

https://atcoder.jp/contests/agc044/submissions/13547183

Editorial is out!

Auto comment: topic has been updated by dario2994 (previous revision, new revision, compare).How can we see submissions of others in AtCoder?

Click on details.

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

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.

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

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

`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.

I am stupid, Thanks It Worked! AC! Struggled whole contest!

I think second place is actually MiFaFaOvO.

Thanks, fixed.

That guy is so confusing.

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.

Your world is too simple!

I don't think problem quality of Codeforces is much worse than AtCoder's!

They have separate employees, rules and sponsors.

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/13545845

EDIT : fixed a typo in the complexity.

I also used meet-in-the-middle with my solution (though I did something more sophisticated but did not end up computing stuff lazily).

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.

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:

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)$$$.

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

anynon-optimal stopping position and making non-stopping.The reason this works is:

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:

`S`

changes $$$d_i=1$$$ into $$$d_i=2$$$ and vice versa, and applies`S`

to $$$h_i$$$;`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.

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

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 1

Correct answer: 3821859835

My answer: 3821859837

After hours trying to make it, i came here asking for help. Here is my submission: https://atcoder.jp/contests/agc044/submissions/13553853

https://atcoder.jp/contests/agc044/submissions/13554127

Thank you very much. I was so angry with problem B that i could not find my wrong usage of % operator.

In problem D why replacing

thisto

thischange something?

In function rec you ask some questions that contains stdin/stdout stuffs. This lead to wrong format

https://clist.by/standings/atcoder-race-ranking-2020-19846514/ may be helpful.

Is the "naively" in solution C serious? It's too dangerous :)

Hi! Is AtCoder working for anyone? It hasn't been working for me since the past 2 days.

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

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.

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!

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.

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.

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)$$$.

Oh I see. Thanks for fast reply.