Problem Link:
Practice
Contest
Difficulty:
CAKEWALK
Pre-requisites:
ad-hoc
Problem:
You are given a string of “#” and “.” representing a passage. A “#” means the presence of a floorboard, while a “.” is the absence of it. Digory and Polly decide to cross the passage (from left to right). At each time, they can only tell where the next “#” position is. They start being able to jump a distance of 1, and whenever they are unable to jump a particular distance L, they take one day to learn how to jump L (and any distance <= L). In how many days will they be able to cross the passage?
Quick Explanation:
Just keep track of the current length of jump you need to perform. If it crosses your threshold at the next “#”, update your threshold and add one to your answer. Pseudocode follows:
int f (string passage)
int L = 1, ans = 0, cur = 0
for(int i = 0; i < passage.length(); i++)
cur++;
if(passage[i] == '#')
if(cur > L)
L = cur
ans++
cur = 0
return ans
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here
2 Likes
it can be solved using divide and conquer using offline query
the logic is to first scan the largest jump in the array,then anything after largest jump doesn’t increment days
so a array “#.#…#…##…#.#” can be divided as “#.#…#” with days incremented by 1
second iteration we consider “#.#…#” and again get array “#.#” with days incremented by 1
third iteration gives “#” with days incremented by 1
and stop on 4th iteration
@vishalrox That’s because you are using strlen() in each iteration, which is O(n) in complexity. So this effectively makes your code O(n^2), where n is the string length.
https://www.codechef.com/viewsolution/8605526
I just modified the same, to get AC with the same code. 
include
using namespace std;
int main()
{
long int t,i,c;
char p[5000000];
cin>>t;
while(t>0)
{
c=0;
gets§;
for(i=0;p[i]!=’\0’;i++)
{
if(p[i]==’.’)
{
c++;
}
if(p[i]=='.'&& i!=0 && p[i-1]=='#'))
{
c++;
}
}
cout<<c<<endl;
t--;
}
}
why is this showing wrong answer
@ashish
You don’t have to store the previous jump. You need to store the MAXIMUM jump encountered so far.
In your code, suppose they leanred jumping 3 units in a day, and then encounter a ‘…’ and ‘…’ in way, so they don’t need additional practice/days to cross it. But your code makes it that after crossing 1 ‘…’ , it stores this in previous and then makes them require 1 more day to re-learn ‘…’
Meaning, you need to store maximum element encountered so far, not the previous.
Also, add return 0; in last line of int main.
Test case-
1
###...##..###..###...##
Your Output
2
Expected output-
1
http://ideone.com/9y6s24 …
why is it showing tle???
why my soln giving WA ?
link text
!!