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

- Contest URL: https://atcoder.jp/contests/agc066
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240331T2100&p1=248
- Duration: 180 minutes
- Number of Tasks: 6
- Writer: maspy
- Tester: potato167, Nyaan
- Rated range: 1200 -

The point values will be 600-600-800-1100-1500-1600.

We are looking forward to your participation!

An AGC! But wait ... A 600?

You are right. But You can easily solve it.

Maybe not that easy. AGC065's A worth 500pts, and I spent 154 mins to solve it.

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

Yes ,it does. Refer to last line of this Link

Thank you sir, got it

How to solve problem A?

Call cells with odd $$$(i+j)$$$ as

`odd cells`

, and those with even $$$i+j$$$ as`even cells`

.For any integer $$$x$$$, call

`closest odd divisor`

as the number closest to $$$x$$$ and divisible by $$$d$$$ which when divided by $$$d$$$ is odd. Similarly, let's define`closest even divisor`

.Then one can easily prove the following lemma is true:

ProofTheir total cost is exactly $$$d*n^2$$$, so atleast one of them is $$$\leq$$$ half of that.

Of course, it is trivial to see that such matrices satisfy the adjacency conditions.

Submission

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.

I think that this comment may have caused some unfairness since there were a few new submissions on that problem tonight, though it's hard to find out who actually hadn't solved this problem before and just copied a solution to pass it.

But this is a common problem in all online programming contests that just can't be avoided even if there were no original problems. For example we can never know whether some participants worked together or shared solutions/ideas during the contest, though it is forbidden by the rules.

As for this contest, this problem was commonly used in Chinese trainings, and so far as I know, most of those who solved it during the contest did it beforehand, so keeping it rated would not be too unfair. Maybe a better way to avoid this situation is to have more testers since the probability that such a famous problem was known to none of the tester would be much lower.

I think a lot of people have seen it, because most Chinese should have used Luogu in this contest, and he has 400- fans in Luogu.

On the other hand, as far as I know, most of the people around me (Chinese) knew that this problem has appeared before during the competition.

Thanks for sharing the details!

Could you explain this sentence "most Chinese should have used Luogu in this contest" — what does it mean? Does Luogu provide some kind of frontend to AtCoder that people are using instead of AtCoder directly?

Luogu is running a remote judge of AtCoder for many years, but it always updates problems after the contest by 3~7 days. I don't think that there are many skilled participants who read/write shit posts in Luogu.

Thanks!

There was a follow-up question here, but it is no longer relevant since this was clarified below.

Sorry, what I meant was that I think there are a lot of Chinese using Luogu in this contest. For example, I know of a number of contestants who posted comments during the competition.

Thanks, it is clear now. You referred to using the social functions of Luogu during AGC 066, not the online judge functions.

Then it does sound unfortunate — why would one use social functions of any website during any round? :)

I asked some Chinese participants who passed E in contest if they saw this comment. Currently nobody admits that he saw this in contest. This problem should be famous because it is very interesting and the observation is really cool. I will not be surprised if some school pick this in a training plan/simulation contest.

At least 400 fans on luogu is just like nothing. I have ~3.5k fans but they rarely leave comments when I post some editorial. Since there are only ~50 participants passed this(about 30 are Chinese) I think noobs can not even find out the relation between two problems(some $$$n!$$$ and $$$\frac{1}{n!}$$$).

However I am so angry when I see this guy is even the administrator(actually the lowest manage group) of the online judge. AFAIK Luogu forbids users to discuss ongoing contests, I have reported that and hope this guy get punished.

It doesn't have a serious consequence. Forgive him. Don't punish him.

Can't understand your opinion. I don't think you are right.

Thank you for your comments. We decided to keep the contest rated.

I'm already tired of all the cheater telegram group shits in CF, but ok, at least they aren't too good. But the fact that people do the same thing in AGC just makes me hate this community.

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:

B:

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.

That can't be right... You can get a rating increase with last place?

Actually right, the perf. of 0pt is 1384, and yes some 0pt lightblues got $$$+ \Delta$$$.

Even if you are in last place, you still have performance rating 1384. If your rating is under this score, you still earn rating.

This is because all problems are too difficult and only 25% of the participants solved at least one. Even some grandmasters get zero score.

I strongly suggest future AGC put at least one problem below 500 to prevent this happen.

I don't think it matters... like at all. Rating is just a number. Rating below 3000 is certainly just a number. AGC happen 4-5 times a year nowadays. This is funny, but it is hardly a serious vulnerability.

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.

If even you — who has solved tens of thousands of problems on multiple online judges — is saying this, I don't think anyone else has much of a chance lol

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.

My python code to generate the answerSeems like 11753 bytes fit under the submission limits, so I was just able to copy-paste the number I received as in here

I have the same solution, to check that $$$s(2^{k-1}x)>s(2^{k}x)$$$ you use that $$$s(5^{99-k})>s(2^{k}) $$$ $$$(k \leq 50)$$$ that seems true because left number is much longer than right.

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.

Can we have your screencast?

Well if YouTube will not block it because of music... I'm uploading yesterday's CF and this contest now.

Thank you! I'll do my best to create another enjoyable contest!

I think today's "contest" isn't very good, unfortunately. But I would be happy if you enjoy my problem.

A and B are both great problems. Unfortunately i wasnt able to try the harder ones

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?Thank you for solving my problem!

It's easy to bound the number of operations with a suitable constant, but to prove that it's an "upper limit of 1", I think a little tedious (but not difficult) case-by-case discussion is needed.

The discussion on operations regarding the suffix is simpler. Adding "-++ +--" can be replaced by inserting +++ and — twice, so it's reasonable to consider only one type of addition. Even if you add "-++ -++ -++", the length of the leading A+-+-... increases by at most 2 (inferior to inserting +++, — three times), so it's acceptable to add no more than twice.

Furthermore, increasing the length of the A+-+-... part by adding these is only possible when the string is exactly in the form of A+-+- up to the end at the time of addition. By verifying that in such cases, the pattern of performing two insertions is not optimal, we can prove it.

The discussion regarding the prefix is similar.

My published code significantly reduces the number of patterns generated for comparison, but when solving problems in contests, I had assumed generating and solving a few more patterns for safety.

Nice problem <3

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.

it is standard for problems to not allow leading zeroes when printing integers.

Polygon single huge integer checker indeed checks for leading zeroes. Guess you learn something everyday