chokudai's blog

AtCoder Beginner Contest 297 Announcement
By chokudai, history, 19 months 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?
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you solve problem E?

→ Reply
  • »
    »
    19 months 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
    • »
      »
      »
      19 months 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
      • »
        »
        »
        »
        19 months 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
    • »
      »
      »
      19 months 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
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How does one come up with this solution

      → Reply
»
19 months 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
  • »
    »
    19 months 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
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Were you able to prove D ?

    → Reply
    • »
      »
      »
      19 months 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
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem F

→ Reply
  • »
    »
    19 months 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
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem Ex

→ Reply
  • »
    »
    19 months 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
»
19 months 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
  • »
    »
    19 months 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
    • »
      »
      »
      19 months 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