chokudai's blog

KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200） Announcement
By chokudai, history, 4 years ago, In English

We will hold KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200）.

The point values will be 100,200,300,400,500,600.

We are looking forward to your participation!

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

Comments Comments (30)
| Write comment?
»
4 years ago, # |
  Vote: I like it +81 Vote: I do not like it

As a writer, I'm happy I finally could come here! Good luck and have a good centennial!

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

    Good problems, I liked E and F, although they are somewhat heavy on the implementation side.

    By the way, /* shameless plug */ I recorded a screencast with explanations today, maybe it will help someone understand the solutions better: link

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

Shit, got AC for D a minute after contest ended

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

AGC reminds me how stupid I am.
ABC reminds me how bad I am at trivial implementations.

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

Very decent problems. Enjoyed an ABC after a long time. Kudos to the author.

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it
Randomised Solution to D
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    It's deterministic actually, and you don't you have to select 20 random elements multiple times, Taking first min(n,8) elements will work

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

      Ah okay! Makes sense to me now.

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

      Yep, simple pigeonhole principle ($$$2^8 > 200$$$)

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

      Sorry for noob question. Could you explain why take first min(n,8) elements work

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

        There are $$$2^8 - 1 = 255$$$ nonempty subsequences, but only $$$200$$$ possible remainders modulo $$$200$$$, hence two sequences will give the same remainder.

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

how to solve D using DP

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

Definition of an Overkill , Used 3-D DP in Problem D . :|

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

Failing on two testcases for problem D-

https://atcoder.jp/contests/abc200/submissions/22437132

Any suggestions please?

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

    In some test cases, you might be printing an empty array.

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

Using FFT on E caused TLE I don't know why? I tried changing long double to double but that caused precision errors. It would be so nice if somebody can help.

submission : Link

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

falling one 1 test case on D, any suggestion about the case where I am missing. https://atcoder.jp/contests/abc200/submissions/22438206

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

Prob D: Here is my 2D knapsack solution. Then I retrieve 2 solutions from the dp States I calculated. Here is the link: https://atcoder.jp/contests/abc200/submissions/22426134

Later realised it was an overkill.

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

    Maybe a long code, but you could have avoided that by using a bitmask that has the $$$i$$$-th bit on if the $$$i$$$-th set is valid (has at least one element), and that way it would be easier to recover the sequences.

    I did that here

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

I tried 2d DP for D, WA in 7 test cases. https://atcoder.jp/contests/abc200/submissions/22438484

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

D — I still didn't get where the 8 came from?? I mean we can still choose some more than 8 numbers to get both the sums % 200 same.

Can someone please help me with this?

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

    for any sequence(not empty), we can map sequence to 0...199 by their sum mod 200. so if there are more than 200 distinct sequences, there must be 2 sequences whose sum are equal. with 8 elements, therr are 255 sequences, which is more than 200 and 8 is the first number with more than 200 sequences. 7 has 127

    → Reply