We will hold KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200）.
- Contest URL: https://atcoder.jp/contests/abc200
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210508T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: physics0523
- Rated range: ~ 1999
The point values will be 100,200,300,400,500,600.
We are looking forward to your participation!
As a writer, I'm happy I finally could come here! Good luck and have a good centennial!
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
Shit, got AC for D a minute after contest ended
AGC reminds me how stupid I am.
ABC reminds me how bad I am at trivial implementations.
Very decent problems. Enjoyed an ABC after a long time. Kudos to the author.
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.
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
Ah okay! Makes sense to me now.
Yep, simple pigeonhole principle ($$$2^8 \gt 200$$$)
Sorry for noob question. Could you explain why take first min(n,8) elements work
There are $$$2^8 - 1 = 255$$$ nonempty subsequences, but only $$$200$$$ possible remainders modulo $$$200$$$, hence two sequences will give the same remainder.
how to solve D using DP
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
Definition of an Overkill , Used 3-D DP in Problem D . :|
One test case failed for D, can you check what was the error https://atcoder.jp/contests/abc200/submissions/22436353
Can't help , My implementation is clearly different you can find it here if you want https://atcoder.jp/contests/abc200/submissions/22429384
same thing happened to me, probably a case like
or
For some reason, your code works for 2 200 40 but not 2 40 200
actually its working for 2 40 200 , ans is NO right
No,
40 = 40%200 = 40
40, 200 = 240%200 = 40
pfft I wonder what you'd call my 6-D DP solution then.
Failing on two testcases for problem D-
https://atcoder.jp/contests/abc200/submissions/22437132
Any suggestions please?
In some test cases, you might be printing an empty array.
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
falling one 1 test case on D, any suggestion about the case where I am missing. https://atcoder.jp/contests/abc200/submissions/22438206
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.
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
wow! learned a lot from ur code !!!
I tried 2d DP for D, WA in 7 test cases. https://atcoder.jp/contests/abc200/submissions/22438484
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?
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