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 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.
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 .