how to solve this question of IOPC 2017?

please explain proper approach with recursion and simple approach if any…

Problem link-https://www.codechef.com/IOPC2017/problems/IOPC17A

my solution-
link text

1 Like

Just brute force it. It will work.

Here is my solution - https://www.codechef.com/viewsolution/13366961

So what I did was that I made a function solve(string s, int l, inr r, int n, int cnt)

cnt is the number of times we have divided the string till now.
l and r define that we have sub-string from [l,r] of the original string.
n - length of the string
s - string

So now I check if the whole sub-string is same. If yes then return cnt.
Else divide.

Hope that was helpful.

1 Like

@mathecodician can u please explain ur approach, as iam not familar with python.

@mathecodician Will you please tell me what’s wrong with my approach? I have explained it in the comment section.

Using priority queue and BFS you can solve this problem

My solution: https://www.codechef.com/viewsolution/13368629

We maintain a priority queue that holds structure that contains string and length of string,the priority queue is maintained based on the length of the string.
In each step we pop the first element and check whether the string holds only one character if yes we calculate the number of steps (at each step the length becomes half of the original length knowing the input string length we can do this)
if no we check whether the length of the sting is even or not, if it is even we split the string into two and push both new string and their length, if it is not even we just ignore it.
if we cannot find a sub string that contains only one character we display -1 (A flag is maintained for this purpose)
Hope this helps

1 Like

Where can u tell?

1 Like

I didn’t use recursion.I first checked whether the given string is the type of string chef likes.If it’s of that type print 0. I then checked parity of the length of the given string if it’s odd print -1. Then even length strings comes into consideration.Here we have 2 cases.If given string is power of 2. If it is then I started with temp= n checked whether it can be the answer or not.Then temp=n/2,n/4…Down to 2. Final ans if log2(n) - log2(temp). If it’s not power of 2 then here we have only one case.If after tearing the middle part(we get two strings),just checked if any of them is ans.

Link: https://www.codechef.com/viewsolution/13367789

My approach uses recursion:

1 - Read the numbers, store them in some array.

2 - Linearly compute for each position how many numbers starting on it are equals (and consecutive), not matter if you do that to the right or to the left.

3 - Use a recursive solution for cutting the original string and so on, and keeping always with the minimum amount needed. As was stated by @mathecodician a Brute Force approach also work… I thinks this is just another way to implement it.

//For that, you must initialize some integer variable “best” with a huge number. Note that “last” is an array and it store for each position, the position of last element to the right which is equal to it; they form a consecutive row of equal values…

Call a Recursive Function: RECURSIVE_DIVIDE(1,large_of_original_string,0)

void COMPUTE(int ini, int fin, int cuts) {

if(cuts >= best) return;

if(last[ini] >= fin) best = cuts;

if(0 == (fin - ini + 1) % 2) //Even length…

{

RECURSIVE_DIVIDE(ini + (fin - ini + 1)/2, fin, cuts + 1);

RECURSIVE_DIVIDE(ini, fin - (fin - ini + 1)/2, cuts + 1);

}

}

recursion will be :-

rec(str,low,high)
{

if(str.size() is odd && check(str))

   return 0;

else if(str.size() is odd && !check(str))

     return a big number

else if(str.size() is even )
{

 if(check(str))
     return 0;

else

 return 1+min(rec(str,low,mid),rec(str,mid+1,high));

}
}

here check() checks whether the string is required type of string or not.
for code , refer - http://ideone.com/RU5UUM

3 Likes

please explain ur approach if u can

Easy
try recursion

2 Likes

is the question uploaded in the practice section yet ?

Yes it´s… there is the link to problem in practice section: https://www.codechef.com/problems/IOPC17A

Yes this question can be solved using bfs as well .