### chokudai's blog

By chokudai, history, 5 weeks ago,

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!

• +75

 » 5 weeks ago, # |   +81 As a writer, I'm happy I finally could come here! Good luck and have a good centennial!
•  » » 5 weeks ago, # ^ |   +32 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, # |   +18 Shit, got AC for D a minute after contest ended
 » 5 weeks ago, # |   +71 AGC reminds me how stupid I am. ABC reminds me how bad I am at trivial implementations.
 » 5 weeks ago, # |   +25 Very decent problems. Enjoyed an ABC after a long time. Kudos to the author.
 » 5 weeks ago, # | ← Rev. 3 →   +17 Randomised Solution to D Randomly choose min(n, 20) elements from the array Generate all possible subset-sums Check if any subset-sum occurs more than once. If yes, we have found a valid answer. Pick any two such subsets. Repeat steps 1-3 an arbitrary number of times (for eg, 40) to ensure the probability of not finding a valid answer is extremely low.
•  » » 5 weeks ago, # ^ |   +30 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, # ^ |   0 Ah okay! Makes sense to me now.
•  » » » 5 weeks ago, # ^ |   +13 Yep, simple pigeonhole principle ($2^8 > 200$)
•  » » » 5 weeks ago, # ^ |   0 Sorry for noob question. Could you explain why take first min(n,8) elements work
•  » » » » 5 weeks ago, # ^ |   +6 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, # |   0 how to solve D using DP
•  » » 5 weeks ago, # ^ |   +1 You will need 3D DP , where DP[x][y][z] denotes that you have used considered first X indices , with one pack having sum Y and one pack having sum Z . Link to my solution https://atcoder.jp/contests/abc200/submissions/22429384
 » 5 weeks ago, # |   +8 Definition of an Overkill , Used 3-D DP in Problem D . :|
•  » » 5 weeks ago, # ^ |   0 One test case failed for D, can you check what was the error https://atcoder.jp/contests/abc200/submissions/22436353
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Can't help , My implementation is clearly different you can find it here if you want https://atcoder.jp/contests/abc200/submissions/22429384
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 same thing happened to me, probably a case like 2 200 200 or 2 200 50 For some reason, your code works for 2 200 40 but not 2 40 200
•  » » » » 5 weeks ago, # ^ |   0 No, mine solution producing correct ans for this test case! I got wrong on test_case #17, for which test case you got error??
•  » » » » 5 weeks ago, # ^ |   0 actually its working for 2 40 200 , ans is NO right
•  » » » » » 5 weeks ago, # ^ |   0 No, 40 = 40%200 = 4040, 200 = 240%200 = 40
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +14 pfft I wonder what you'd call my 6-D DP solution then.
 » 5 weeks ago, # |   0 Failing on two testcases for problem D-https://atcoder.jp/contests/abc200/submissions/22437132Any suggestions please?
•  » » 5 weeks ago, # ^ |   +5 In some test cases, you might be printing an empty array.
 » 5 weeks ago, # |   0 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, # |   0 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 →   0 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/22426134Later realised it was an overkill.
•  » » 5 weeks ago, # ^ |   +4 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, # |   0 I tried 2d DP for D, WA in 7 test cases. https://atcoder.jp/contests/abc200/submissions/22438484
 » 5 weeks ago, # |   0 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, # ^ |   +3 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, # |   0 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 →   0 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 submissionSee also this comment to understand more about inclusion-exclusion principle.Hope this helps
•  » » 3 weeks ago, # ^ |   0
•  » » » 2 days ago, # ^ | ← Rev. 2 →   0 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, # ^ |   0 Oh sorry!, ignore it, I just realised I didn't put upper bound condition.