An AGC! But wait ... A 600?

If i participate in the contest as unrated, still it count for GP30 scores?

How to solve problem A?

Tooo hard

Thank you for participating in the contest, and I'm very sorry that the problem E was exactly the same as some USACO problem.

During the contest many people asked us if the contest would be rated, so I'll describe our policy.

If the problem was not theft and it's just a coincidence, we don't make the round unrated. Those who know the problem can earn points easily and that looks unfair. However, we can say that it's a kind of reward for those who practiced. I understand that this reward is extreme it's not fun for other participants. Nevertheless, I don't think that's enough to declare the contest unrated. Therefore we currently plan to make the round rated.

However, some people expressed their concern about posing the solution on the internet. We did some search and found this comment. P6277 is the problem ID of the subject USACO problem. Of cource we will remove this participant from today's standings, but I'm not sure how much impact does it have.

I'd like to hear your opinion (especially from Chinese participants) about the situation. Did the comment above spread in the Chinese community, did other people also share the solution, or did nobody notice this?

I believe most of the participants (especially top participants) remembered the USACO problem by themselves and the leak didn't affect the standings much. If that's the case we will keep the round rated.

Last but not least, I am very sorry for the bad contest experience. I hope you find other problems interesting and enjoyed them.

Problem E is USACO 2020 Open Problem 3.

I copied code from the editorial for that problem into my submission -- that should be allowed under the rules right, since it was published before the contest?

Solutions (maybe unintended?) to A and B:

A:

• Color the grid with a checkerboard pattern.
• For a fixed $$$k$$$ in $$$[0, 2d-1]$$$, put an integer which is $$$\equiv k \text{ (mod } 2d)$$$ in even cells, and $$$\equiv k+d \text{ (mod } 2d)$$$ in odd cells.
• The expected cost is exactly $$$dn^2/2$$$, so at least one choice of $$$k$$$ works.

B:

• Note that $$$f(k) = 10^{100}(2^k - 1)$$$ behaves quite well, since the number of nonzero digits increases by $$$1-\log_2(10)$$$ on average every time you divide it by $$$2$$$.
• Then, you can try to let $$$2^n \cdot x$$$ be a number consisting of many copies of $$$f(k)$$$ with different $$$k$$$, but it does not work because the digits on the right are the same for all $$$k$$$, so the divisions by $$$2$$$ have similar effects on all $$$k$$$. You actually need random $$$f(k, l) = 10^{100}(2^k-1)(2^{-l})$$$.
• This still does not work if $$$l > k$$$, because there can be a lot of digits $$$9$$$ on the left that are deleted when you divide by $$$2$$$. In practice, you can choose $$$k \approx 125$$$ and $$$l \approx 25$$$.

The way to increase your rating easily:

Step 1: Participate beginners and reach 1200.

Step 2: Register an rated AGC that begin with 600 points problem,

Step 3: Go to sleep

Congratulations, you rating increased.

Hello, I'm the writer of AGC 066.

I apologize for the fact that AGC 066 E was an exact match with a problem from a past contest. This significantly diminished the satisfaction of the contest.

I want to solve more problems to improve my ability to identify matches with past contest problems.

Problem A and B's construction are SOOO hard for me, I spent about >60 minutes on each problem.

I solved them by guessing and trying many methods....

My approach to B:

I made the following observation: multiplying $$$2$$$ is effectively like dividing by $$$5$$$ (and then multiplying by $$$10$$$ which doesn't change the digit sum)

And if you have a power of $$$5$$$, the digit sum (on average, but not always!) will decrease when you divide by $$$5$$$.

Thus, you can concatentate a bunch of blocks of length $$$100$$$ with powers of $$$5$$$ in each block, and in every iteration, you should expect the average digit sum among the blocks to decrease.

n_pows = 99
five_pow = 50
digits_per_block = 100

A = 0
for i in range(n_pows):
    A += pow(5,five_pow) * pow(10,i * digits_per_block)
    five_pow += 1


print(str(A))

Seems like 11753 bytes fit under the submission limits, so I was just able to copy-paste the number I received as in here

Unlike the solution from the editorial, my solution for problem B does not utilize the fact that 2 (the number we multiply by many times) is not coprime with 10 (the base of the numeral system), and therefore I believe it is more general (it also has some failing assertions that should not fail, so maybe the below is false):

Consider the following number: $$$10^k-x$$$. What happens when we multiply it by $$$2^n$$$? We get $$$2^n\cdot 10^k-2^n\cdot x=(2^n\cdot 10^k-1)-(2^n\cdot x-1)$$$. Now $$$(2^n\cdot 10^k-1)$$$ is a number that starts with $$$2^n-1$$$ followed by $$$k$$$ 9s. Now if $$$k$$$ is bigger than the length of the number $$$(2^n\cdot x-1)$$$, the subtraction happens in the area of 9s, so $$$f((2^n\cdot 10^k-1)-(2^n\cdot x-1))=f(2^n-1)+9\cdot k-f(2^n\cdot x-1))$$$.

Note that the part containing $$$x$$$ has a negative sign, so instead of decreasing $$$f()$$$ we now need an increasing $$$f()$$$! The rest is like in the editorial: we take many random $$$x$$$ (I did 50, each up to 255), and concatenate the decimal representations of $$$10^k-x$$$. It is not hard to see that the above computations happen almost independently for them, as long as $$$k$$$ is high enough. We do have a growing component in $$$f(2^n-1)$$$, but when we concatenate many $$$10^k-x$$$ we get only one term of the form $$$f(2^n-1)$$$ but many terms of the form $$$-f(2^n\cdot x-1))$$$, so the latter dominate.

When I saw B — Decreasing Digit Sums, I even thought I was looking at the problem of Project Euler :P

To maspy and maroonrk: I enjoyed the problems very much, don't be sad :) This kind of thing happens sometimes, it's not the end of the world.

wOw it was my first contest on Atcoder...

Is there proof for problem F that operations turn X into Y++- and append +-- to the string have an upper limit of $$$1$$$ in an optimal construction?

Was this contest named AtCoder April Fools Day Contest 2024?

Can someone explain to me which checker was used in problem B? During the contest I got 1 extra submission for outputing leading zeroes. May be my question is dumb but do checkers always prohibit such behaviour? It's first time something like this has happened to me so I am wondering whenever I should be careful with this in the future. Also if this is not such a commonly occurring thing may be stating that in output format would be helpful.