chokudai's blog

By chokudai, history, 5 weeks 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

»
5 weeks 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!

  • »
    »
    5 weeks 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

»
5 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Shit, got AC for D a minute after contest ended

»
5 weeks 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.

»
5 weeks 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.

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

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

      Ah okay! Makes sense to me now.

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

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

    • »
      »
      »
      5 weeks 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

      • »
        »
        »
        »
        5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D using DP

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
5 weeks 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?

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

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

»
5 weeks 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

»
5 weeks 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

»
5 weeks 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.

  • »
    »
    5 weeks 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

»
5 weeks 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

»
5 weeks 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?

  • »
    »
    5 weeks 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

»
5 weeks 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?

»
3 weeks 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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      2 days 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!

      • »
        »
        »
        »
        2 days 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.