maroonrk's blog

By maroonrk, history, 3 weeks ago, In English

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

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

We are looking forward to your participation!

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

»
3 weeks ago, # |
  Vote: I like it +98 Vote: I do not like it

An AGC! But wait ... A 600?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are right. But You can easily solve it.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

How to solve problem A?

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

    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:

    Matrix 1: Assign all odd cells to closest odd divisor and all even cells to closest even divisor.

    Matrix 2: Assign all odd cells to closest even divisor and all even cells to closest odd divisor.

    Then the minimum of cost of Matrix 1 and Matrix 2 is less than $$$(1/2)dn^2$$$

    Proof

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

    Submission

»
3 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

Tooo hard

»
3 weeks ago, # |
  Vote: I like it +270 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +71 Vote: I do not like it

    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.

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

    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.

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

      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?

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

        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.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
          Rev. 3   Vote: I like it +1 Vote: I do not like it

          Thanks!

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

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

        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.

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

          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? :)

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

      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.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it -35 Vote: I do not like it

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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -54 Vote: I do not like it

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

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

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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.

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

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?

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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$$$.
»
3 weeks ago, # |
Rev. 2   Vote: I like it +70 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

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

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

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

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

      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.

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

        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.

»
3 weeks ago, # |
  Vote: I like it +226 Vote: I do not like it

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.

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

    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

»
3 weeks ago, # |
  Vote: I like it +55 Vote: I do not like it

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

»
3 weeks ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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 answer

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

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.

»
3 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +167 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can we have your screencast?

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

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

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

    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.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 3   Vote: I like it +13 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it

wOw it was my first contest on Atcoder...

»
3 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

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?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    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.

»
3 weeks ago, # |
Rev. 2   Vote: I like it -99 Vote: I do not like it

Was this contest named AtCoder April Fools Day Contest 2024?

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

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

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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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