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.

Randomised Solution to DRandomly 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 > 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

No, mine solution producing correct ans for this test case! I got wrong on test_case #17, for which test case you got error??

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

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

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?

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

1-indexed solution

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,

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

Can you help? Thanks!

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