zscoder's blog

Atcoder Grand Contest 022
By zscoder, history, 6 years ago, In English

Atcoder Grand Contest 022 will be held on Saturday (or Sunday depending on your timezone). However, the time of this contest will be three hours later than the usual time for Atcoder contests, i.e. 12am JST instead of 9pm JST. Thus, please check the contest time carefully here.

I (zscoder) am the writer of this contest and this contest counts for GP30 scores.

Contest Link

Contest Announcement

Duration : 150 minutes (2 hours and 30 minutes, 40 minutes longer than usual)

Scoring Distribution : 300-600-700-1600(1000)-1600-1600

I hope you will enjoy the problems. Although the date of the contest is 1 April 12am JST, it is assured that this contest is not an April Fool joke :)

Let's discuss problems after the contest.

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

»
6 years ago, # |
← Rev. 3   Vote: I like it -54 Vote: I do not like it

Does it intersect with CF April Fool's?

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

Codechef March Lunchtime clashes with it :(

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Contest starts in < 1 hour.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Duration: TBD.

Really?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    They probably forgot to update the blog. It's confirmed to be 150 minutes.

    → Reply
»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

When you make the mistake of picking Codechef LTIME over it and it gets cancelled...

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

    just curious, why didn't you just switch over?

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

      Bleh I just started thinking about the CC problems and felt too lazy to start a new contest.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://oeis.org/A214765 Is problem F this?

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

    No, the fifth term doesn't match.

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

    No, we oeised the sequence and it wasn't found.

    → Reply
»
6 years ago, # |
  Vote: I like it +50 Vote: I do not like it

Wow, I had never used Atcoder until today. It's an amazing platform! 10/10 loved it <3 really, try it out.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My idea for B was to select x elements which are multiples of 2(and not 3), where x is multiple of 3. Select y elements which are multiples of 3(and not 2), where y is multiple of 2. Other elements are multiple of 6. Then, for all elements which are divisible by 2, you get GCD as 2, and so on. But my solution is passing only half of the test cases. Can anyone please help me out? Here is my code: https://pastebin.com/PqdrRxD5. Is there any way of downloading the test cases?

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

    Testcases are published at https://atcoder.jp/post/21.

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

      Thanks a lot! My approach was completely wrong :(

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +10 Vote: I do not like it

        Your approach is almost fine. I used the same, but selecting x elements which are multiples of 2 and not 3, with x a multiple of 3, is not sufficient.

        For example you might pick (2, 4, 8). Their sum is 14, and not divisible by 3.

        To make your approach work all you have to do is make sure that you have x elements which are multiples of 2 and give 1 modulo 3 and also x elements which are multiples of 2 and give 2 modulo 3. That's how you ensure the sum is divisible by 3.

        I got AC with that.

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

    Here's a method for B that was easier to code:

        vector<int> nums;
    for(int j = 1; j <= 30000; j++){
        if(j % 2 == 0 || j % 3 == 0 || j % 5 == 0){
            nums.push_back(j);
        }
    }
    while(1){
        // try
        random_shuffle(nums.begin(), nums.end());
        int g = 0;
        int sum = 0;
        for(int j = 0; j < n; j++){
            g = __gcd(g, nums[j]);
            sum += nums[j];
        }
        if(sum % 30 != 0) continue;
        if(g != 1) continue;
        for(int j = 0; j < n; j++){
            cout << nums[j] << " ";
        }
        cout << endl;
        break;
    }
    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +82 Vote: I do not like it

Even though Japanese blood doesn't flow within zscoder, tasks were, as always on AtCoder, great.

→ Reply
»
6 years ago, # |
  Vote: I like it +46 Vote: I do not like it

It looks like problem D has weak testcases. I just took O(n2) DP (like in editorial) and bound the second parameter by .

Also was it intended in problem F that any polynomial solution is OK? I had O(n6) and it was OK to precalc (actually it works about 4s, so probably even with O(n7) solution you can do precalc).

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it +6 Vote: I do not like it

    Yes, I'm sorry for the weak testcases for D. I tried hard to fail some wrong greedy solutions but am not aware that bounding the parameter of the O(n2) dp passes.

    Also, it is intended for F that any polynomial solution that you can precalculate in time to pass. Initially, the constraints were set to N ≤ 100 but we decided to lower it to N ≤ 50.

    Anyway, congratulations on the win.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I found the second question on constructive algorithm quite random.Any insight on how to approach such problems.

→ Reply
»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I have one general question about problems like problem E: how to solve this type of problems? It can be easily seen that you need to find out correct pattern for good (or bad) strings. I do some pen-and-paper work trying to find useful properties of good strings or guess the pattern. Sometimes it works, but not always.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    Try out small cases and also find some observations (invariants, necessary conditions etc...). For example, for this problem, I noted that if the string has 4 or more consecutive ones, then it must be beautiful, and so we only need to consider strings with  ≤ 3 consecutive ones. It also helps if you wrote a brute force and print out all possible small cases to either analyze the pattern or verify your conjectures.

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

    For this particular question I observed a few greedy rules that help me reduce strings. For example it is always good move to replace 000 with 0. I analyzed problem a bit more and observed more such rules and then concluded that there is finitely many equivalence classes of prefixes and I can identify them with partially reduced strings. For example, if I'm dealing with prefix and I don't know my future, I know that if I see 001 I can reduce it to 0, but I can't reduce 100 to 0 because 0 may come next. Or when put in other words, this can be simulated by constructing an automaton and counting number of partial paths ending at every state. My automaton had 10 states, but I didn't built it explicitly, I just had map<string, int> dp and function string Reduce(string) that searches for patterns that can be greedily reduced.

    However I don't think this is a general way of dealing with such problems, I found my approach pretty unique. I did not try to find some general way of describing good strings (or, I tried but failed) and I don't think bruteforce would have helped me to observe any patterns.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The time was so unusual and I just noticed it.

→ Reply