AMR12I - Saruman of Many Colours

no tags 

 

'"For I am Saruman the Wise, Saruman Ring-maker, Saruman of Many Colours!"
'I looked then and saw that his robes, which had seemed white, were not so, but were woven of all colours. And if he moved they shimmered and changed hue so that the eye was bewildered.' - Gandalf the Grey.
And so it was that Saruman decided to brand his Uruk-hai army with the many colours that he fancied. His method of branding his army was as follows.
He straps his army of N Uruk-hai onto chairs on a conveyor belt. This conveyor belt passes through his colouring-room, and can be moved forward or backward. The Uruk-hai are numbered 0 to N-1 according to the order in which they are seated. Saruman wishes that the i'th Uruk-hai be coloured with the colour c[i].
Further, his colouring-room has space for exactly K chairs. Once the chosen K consecutive Uruk-hai are put into the room, a colour jet sprays all K of them with any fixed colour. The conveyor belt is not circular (which means that the N-1'th and the 0'th Uruk-hai are not consecutive). Note that Uruk-hai can be recoloured in this process.
Saruman wants to find out what is the minimum number of times that the jet needs to be used in order to colour his army in the required fashion. If it is not possible to colour the army in the required fashion, output -1.
Input (STDIN):
The first line contains the number of test-cases T.
Each test case consists of 2 lines. The first line contains two space-separated integers, N and K.
This is followed by a single like containing a string of length N, describing the colours of the army. The i'th character of the string denotes the colour of the i'th Uruk-hai in the army.
Output (STDOUT):
Output T lines, one for each test case containing the answer for the corresponding test case. Remember if it is not possible to colour the army as required, output -1.
Constraints:
1 <= T <= 50
1 <= K <= N <= 20,000
The string c has length exactly N and contains only the characters 'a',...,'z'.
Sample Input:
2
3 2
rgg
3 3
rgg
Sample Output:
2
-1
Notes/Explanation of Sample Input:
In the first test case, soldiers 0 and 1 can first be painted with 'r', and then soldiers 1 and 2 can be painted with 'g'.
In the second test case, since N = K, all the soldiers will only have the same color.

 

'"For I am Saruman the Wise, Saruman Ring-maker, Saruman of Many Colours!"

'I looked then and saw that his robes, which had seemed white, were not so, but were woven of all colours. And if he moved they shimmered and changed hue so that the eye was bewildered.' - Gandalf the Grey.

And so it was that Saruman decided to brand his Uruk-hai army with the many colours that he fancied. His method of branding his army was as follows.

He straps his army of N Uruk-hai onto chairs on a conveyor belt. This conveyor belt passes through his colouring-room, and can be moved forward or backward. The Uruk-hai are numbered 0 to N-1 according to the order in which they are seated. Saruman wishes that the i'th Uruk-hai be coloured with the colour c[i].

Further, his colouring-room has space for exactly K chairs. Once the chosen K consecutive Uruk-hai are put into the room, a colour jet sprays all K of them with any fixed colour. The conveyor belt is not circular (which means that the N-1'th and the 0'th Uruk-hai are not consecutive). Note that Uruk-hai can be recoloured in this process.

 

Saruman wants to find out what is the minimum number of times that the jet needs to be used in order to colour his army in the required fashion. If it is not possible to colour the army in the required fashion, output -1.

 

Input (STDIN):

The first line contains the number of test-cases T.

Each test case consists of 2 lines. The first line contains two space-separated integers, N and K.

This is followed by a single like containing a string of length N, describing the colours of the army. The i'th character of the string denotes the colour of the i'th Uruk-hai in the army.

 

Output (STDOUT):

Output T lines, one for each test case containing the answer for the corresponding test case. Remember if it is not possible to colour the army as required, output -1.

 

Constraints:

1 <= T <= 50

1 <= K <= N <= 20,000

The string c has length exactly N and contains only the characters 'a',...,'z'.

 

Sample Input:

2

3 2

rgg

3 3

rgg

 

Sample Output:

2

-1

 

Notes/Explanation of Sample Input:

In the first test case, soldiers 0 and 1 can first be painted with 'r', and then soldiers 1 and 2 can be painted with 'g'.

In the second test case, since N = K, all the soldiers will only have the same color.

 

 


hide comments
rahul gautam: 2015-09-13 14:40:27

The rings were created by sauron :P

dark_lord1: 2015-08-18 18:43:33

@Aditya Bahuguna you saved me a lot of time..but I still feel that I did not get to clear my concept myself rather than took the help of comments.

[deleted]: 2013-12-07 23:42:54

@varun even without following a proper algorithm as required by the question,solution is getting accepted.please check the test cases

Ayush Vatsa: 2013-12-06 06:06:47

nice problem...had fun

Aditya Bahuguna: 2013-06-02 11:08:29

@those gettng WA:
5 rgggr
ans->3
u can put first 3 paint them left to right rrr then last three paint them rrr
at last pick 2nd 3rd and 4th paint them ggg thus 3 moves...

Last edit: 2013-06-02 11:09:12
Atul Kumar Verma: 2013-05-17 19:39:43

Plzz give some tricky cases i am getting wrong ans.

mehmetin: 2013-01-02 10:31:34

nice problem

Last edit: 2013-01-03 02:57:25
Shashank_Jain: 2012-12-29 19:48:39

@nightmare - thanks mate ! i thought we can only start from 1 .. well this wasn't given . thanks :)

foreverbell: 2012-12-29 09:57:20

@Flawless: paint it in the reverse order.

Shashank_Jain: 2012-12-29 08:56:30

@varun jalan- i think david is right.. u can't paint last one "g".. or can u ???

Last edit: 2012-12-29 08:56:48

Added by:Varun Jalan
Date:2012-12-22
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Varun Jalan - ICPC Asia regionals, Amritapuri 2012