chokudai's blog

By chokudai, history, 12 months 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

»
12 months 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!

  • »
    »
    12 months 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

»
12 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Shit, got AC for D a minute after contest ended

»
12 months 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.

»
12 months 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.

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

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah okay! Makes sense to me now.

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

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

    • »
      »
      »
      12 months 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

      • »
        »
        »
        »
        12 months 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.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D using DP

»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
12 months 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?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

»
12 months 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

»
12 months 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

»
12 months 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.

  • »
    »
    12 months 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

»
12 months 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

»
12 months 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?

  • »
    »
    12 months 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

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I also know about dynamic planning problem like knap sack or lcs, but when reading articles like post D I can't figure out if it's a dp problem, how can this be improved?

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

For those who are weak in combinatorics and don't know how to solve E with it (like me), here is my submission with detailed comments. Main idea was from thescrasse's submission

See also this comment to understand more about inclusion-exclusion principle.

Hope this helps

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Hey,I had a similar approach,but for finding the sum I used binary search and star bars, idk why but it's giving wrong answer,

      $$$x+y+z+dummy=n$$$
      $$$x=a+1, y=b+1, z=c+1$$$
      $$$a+b+c+dummy=n-3$$$
      $$$ {n-3+4-1}\choose{4-1}$$$ = $$${n}\choose{3}$$$

      This give elements with sum less than equal to n, I don't know why is it giving wrong sum value,

          ll l = 3, r = 3 * n + 1;
          auto f = [&](ll x) {
              return (1ll*x * (x - 1) * (x - 2)) / 6;
          };
          
          ll ans = -1;
          
          while (l < r) {
              ll md = (l + r) / 2;
              if (f(md) < k) {
                  l = md + 1;
              }
              else {
                  r = md;
              }
          }
      

      Can you help? Thanks!

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh sorry!, ignore it, I just realised I didn't put upper bound condition.