dario2994's blog

By dario2994, history, 4 years ago, In English

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:

  1. tourist
  2. jqdai0815
  3. mnbvmar
  4. FizzyDavid
  5. taeyeon_ss

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.

  • Vote: I like it
  • +471
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +238 Vote: I do not like it

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +86 Vote: I do not like it

    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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +173 Vote: I do not like it

      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?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +162 Vote: I do not like it

        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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +79 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

should I be giving AGC?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +34 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +47 Vote: I do not like it

No Div1 round within 10 days on CF :(

»
4 years ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +174 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Looking forward to an amazing problemset again :)

»
4 years ago, # |
  Vote: I like it +201 Vote: I do not like it

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

Also me: Solves AB

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +82 Vote: I do not like it

    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:

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve D?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    • 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.
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +35 Vote: I do not like it

      Instructions unclear, d*ck stuck in the compiler

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    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, # |
  Vote: I like it +271 Vote: I do not like it

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"

»
4 years ago, # |
  Vote: I like it +143 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -32 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it +49 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +68 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I have the same feelings with you.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    simpler version of D is also given here

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        It's called ratism!

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +61 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve A?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      care to use more words please!

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +42 Vote: I do not like it

      How to analyze the time complexity tho?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        editorial has explained this clearly!

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +54 Vote: I do not like it
        Claim
        Proof
»
4 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +233 Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial is out!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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 ;

}
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I think second place is actually jqdai0815.

»
4 years ago, # |
Rev. 3   Vote: I like it -98 Vote: I do not like it

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.

»
4 years ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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.

»
4 years ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +41 Vote: I do not like it

    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:

    1. 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.
    2. 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)
»
4 years ago, # |
Rev. 3   Vote: I like it +72 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

In problem D why replacing

this

to

this

change something?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +18 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

»
4 years ago, # |
  Vote: I like it +70 Vote: I do not like it

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!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh I see. Thanks for fast reply.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.