### chokudai's blog

By chokudai, history, 11 months ago,

We will hold AtCoder Beginner Contest 297.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

• +49

 » 11 months ago, # |   0 How do you solve problem E?
•  » » 11 months ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » » 11 months ago, # ^ |   +1 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.
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » 11 months ago, # ^ |   +1 Yes.
•  » » » 8 months ago, # ^ |   0 How does one come up with this solution
 » 11 months ago, # |   +2 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?
•  » » 11 months ago, # ^ |   0 Maybe similar with Leetcode2386: Find the K-Sum of an Array.PS: Solve G instead of E...
•  » » » 11 months ago, # ^ |   0 How to prove grundy number of a pile will be ${(a_i \space \% \space (L + R)) / L}$ ??
•  » » » » 11 months ago, # ^ |   0 I do not prove it. Just print a table using dfs.
•  » » » » » 11 months ago, # ^ |   0 table of what?
•  » » » » » » 11 months ago, # ^ |   0 Sprague-Grundy function.
•  » » » » 11 months ago, # ^ |   +4 Mathematical induction may help.
•  » » 11 months ago, # ^ |   0 Were you able to prove D ?
•  » » » 11 months ago, # ^ |   0 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
 » 11 months ago, # |   0 How to solve problem F
•  » » 11 months ago, # ^ |   0 iterate over all possible heights and widths of the rectangle we can choose.
 » 11 months ago, # |   0 How to solve problem Ex
•  » » 11 months ago, # ^ | ← Rev. 2 →   +23 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.
 » 11 months ago, # |   0 When editorial?? Waiting patiently
 » 11 months ago, # |   0 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?
•  » » 11 months ago, # ^ |   0 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.
•  » » » 11 months ago, # ^ |   0 ooooooooo, didn't realise this was graph, also hadn't seen dijkstra used like this before, very nice, thank you for your explanation.