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

Points: 5 (partial)

Time limit: 1.0s

Memory limit: 512M

Author:

Problem type

You are given a row of slots numbered from $1$ ~1~ to $N$ ~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$ ~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$ ~N~ and $K$ ~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$ ~N~.

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

Marks Awarded	$N$ ~N~	$K$ ~K~
$6$ ~6~ marks	$2 \leq N \leq 10^3$ ~2 \leq N \leq 10^3~	$0 \leq K \leq 10^3$ ~0 \leq K \leq 10^3~
$9$ ~9~ marks	$2 \leq N \leq 10^6$ ~2 \leq N \leq 10^6~	$0 \leq K \leq 10^6$ ~0 \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
010111

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
100010000000001001001000001001

Sample Output 2

Comments

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. ← edited →

30 9

100010000000001001001000001001

(9 marbles remaining you have to add)

it is optimal to first use 2 marbles here

100010000000001001001000001001

Now: 100010000000001111001000001001 -- > 100010000000000001001000001001

(7 marbles remaining)

it is optimal to then use 2 marbles here

100010000000000001001000001001

Now: 100010000000000001001000001111 -- > 100010000000000001001000000001

(5 marbles remaining)

it is optimal to then use 2 marbles here

100010000000000001001000000001

Now: 100010000000000001111000000001 -- > 100010000000000000001000000001

(3 marbles remaining)

Finally, use 3 marbles here

100010000000000000001000000001

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!