chokudai's blog

AtCoder Beginner Contest 297 Announcement
By chokudai, history, 21 month(s) ago, In English

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!

  • Vote: I like it
  • +49
  • Vote: I do not like it

Comments Comments (23)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you solve problem E?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How does one come up with this solution

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

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?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe similar with Leetcode2386: Find the K-Sum of an Array.

    PS: Solve G instead of E...

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to prove grundy number of a pile will be $$${(a_i \space \% \space (L + R)) / L}$$$ ??

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Were you able to prove D ?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem F

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    iterate over all possible heights and widths of the rectangle we can choose.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem Ex

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +23 Vote: I do not like it

    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.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ooooooooo, didn't realise this was graph, also hadn't seen dijkstra used like this before, very nice, thank you for your explanation.

      → Reply