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

should I be giving AGC?

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

No Div1 round within 10 days on CF :(

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.

I think the problems will be super awesome!

Looking forward to an amazing problemset again :)

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

Also me: Solves AB

How to solve D?

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?

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

How to solve A?

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

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

Editorial is out!

Auto comment: topic has been updated by dario2994 (previous revision, new revision, compare).

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 ;

}

I think second place is actually jqdai0815.

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.

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.

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

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.

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

In problem D why replacing

cout << "! " << rec(0, m - 1) << endl;

to

string ans = rec(0, m - 1);
cout << "! " << ans << endl;

change something?

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.

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.

I have a confusion... Is there any difference between the two output ways?
string ans=solve(0,61); cout<<"! "<<ans<<endl;
cout<<"! "<<solve(0,61)<<endl;

In problem D, the first way gets AC, but the second one gets WA.