chokudai's blog

By chokudai, history, 21 month(s) 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

| Write comment?
»
21 month(s) 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!

  • »
    »
    21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it +18 Vote: I do not like it

Shit, got AC for D a minute after contest ended

»
21 month(s) 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.

»
21 month(s) 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.

»
21 month(s) ago, # |
Rev. 3   Vote: I like it +17 Vote: I do not like it
Randomised Solution to D
  • »
    »
    21 month(s) 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

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah okay! Makes sense to me now.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

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

    • »
      »
      »
      21 month(s) 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

      • »
        »
        »
        »
        21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D using DP

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
21 month(s) 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?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

»
21 month(s) 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

»
21 month(s) 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

»
21 month(s) 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.

  • »
    »
    21 month(s) 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

»
21 month(s) 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

»
21 month(s) 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?

  • »
    »
    21 month(s) 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