Mock CCC '24 Contest 1 J4/S1 - Magical Magnetic Marbles

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

You are given a row of slots numbered from 1 to N. Each slot can either be vacant (0) or contain a magnetic marble (1). The magnetic forces in these marbles prompt adjacent ones to merge into a single marble, settling in the slot of the rightmost merging marbles. Marbles merge immediately when adjacent, including in the starting configuration. Your task is to place exactly K marbles such that the resulting number of marbles is the minimum possible.

Input Specification

The input will consist of two lines. The first line will contain two integers N and K, representing the number of slots and number of marbles that you can add respectively.

The second line will contain a string of 0 and 1 of length N.

The following table shows how the available 15 marks are distributed.

Marks AwardedNK
6 marks2 \leq N \leq 10^30 \leq K \leq 10^3
9 marks2 \leq N \leq 10^60 \leq K \leq 10^6

Output Specification

The output will consist of a single integer indicating the minimum possible number of marbles in the slots after all marbles have been placed.

Sample Input 1

6 1

Sample Output 1


Explanation for Sample 1

In the given example, the row of slots can be represented as 010111 at the beginning. We can perform a merge immediately, and the configuration becomes 010001. We can place one marble at the first slot and result in the configuration 110001. Then, another merge can be performed, and our final configuration becomes 010001 which has the minimum possible number of marbles after all marbles are placed and merged.

Sample Input 2

30 9

Sample Output 2



  • 0
    thingthingthing1234  commented on Feb. 20, 2024, 2:48 a.m.

    Can someone take a look at my submission. I keep getting WA for the 3rd test case. Thanks

  • 0
    anjaneya  commented on Jan. 30, 2024, 3:44 a.m.

    can someone explain case sanple 2?

    • 4
      b_nary  commented on Jan. 30, 2024, 5:51 a.m.

      30 9


      (9 marbles remaining you have to add)

      it is optimal to first use 2 marbles here


      Now: 100010000000001111001000001001 -- > 100010000000000001001000001001

      (7 marbles remaining)

      it is optimal to then use 2 marbles here


      Now: 100010000000000001001000001111 -- > 100010000000000001001000000001

      (5 marbles remaining)

      it is optimal to then use 2 marbles here


      Now: 100010000000000001111000000001 -- > 100010000000000000001000000001

      (3 marbles remaining)

      Finally, use 3 marbles here


      Now: 111110000000000000001000000001 -- > 000010000000000000001000000001

      there are 3 marbles left in the slots at the end. the order of the operations could have been switched but hope this helps

      • 0
        Viv_CCGS  commented on Jan. 30, 2024, 12:37 p.m.

        It is a bit hard to understand the example when you haven't put in the merging of the marbles into the explanation. But thank you so much, helped a lot!