We will hold AtCoder Beginner Contest 297.
- Contest URL: https://atcoder.jp/contests/abc297
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230409T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: PCTprobability, nok0, evima, Nyaan, kyopro_friends, sugarrr
- Tester: Nyaan, physics0523
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!
How do you solve problem E?
maintain a set and take the smallest element at each step and add all elements that can be made from this element by adding the elements of the array and put them in the set , repeat this process k times. Note the set size should not exceed memory limit , to do that you can check and add the element only if set.size()<= some number , for me 1e6 worked , there may be a tighter bound. here is my solution.
Why does taking the smallest element work?
I mean, I think I did not understand your solution, why wouldn't we add different elements at every step if we start from the same element (smallest) and add the same elements (of a static array)?
UPD: oh I see you remove the smallest at every step
i think those different elements that could be made by adding new elements from the set can also be made by adding the elements from the static array.
are we removing the smallest element and adding them to rest of elements in set to create new numbers which we insert into the set?
Yes.
How does one come up with this solution
I wasn't able to solve E :(
Seems like something very standard but I wasn't able to find it... And optimized bruteforces took a couple of minutes.
Any hints?
Maybe similar with Leetcode2386: Find the K-Sum of an Array.
PS: Solve G instead of E...
How to prove grundy number of a pile will be $$${(a_i \space \% \space (L + R)) / L}$$$ ??
I do not prove it. Just print a table using dfs.
table of what?
Sprague-Grundy function.
Mathematical induction may help.
Were you able to prove D ?
You can print out the values a, b and the difference and a pattern becomes visible. For example this test case is interesting. 1000000 1000000000000
How to solve problem F
iterate over all possible heights and widths of the rectangle we can choose.
How to solve problem Ex
Use inclusion-exclusion, polynomial inversion to get the number of splendid array whose sum is k for 1<=k<=n.
And we can use this information to calculate the answer by counting if we put a number $$$k$$$ on the array and the sum before the number is $$$x$$$ and after the number is $$$y$$$ and $$$k+x+y=n$$$, how many number of this array. If can be do by inclusion-exclusion and FFT if we get the first part answer.
hi, can someone who solved E during contest share the thought process leading to their solution? Like what chain of thoughts led to spotting the idea. Is it similar to some other idea that is well-known?
You can see the process as running a shortest path algorithm on a hidden graph and your goal is to calculate the node with k-th distance to node 1. So you can easily solved this problem with a heap-optimistic dijkstra.
ooooooooo, didn't realise this was graph, also hadn't seen dijkstra used like this before, very nice, thank you for your explanation.