ATTIC - Editorial

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

https://www.codechef.com/viewsolution/8601701 why its showing tle…!!

@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. :smiley:

thanxx @harshvk5 :stuck_out_tongue: !!

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

whats the problem with this one?
https://www.codechef.com/viewsolution/12867646

@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

#include<bits/stdc++.h>
using namespace std;
#define fi(S) for(int i=0;i<S;i++)
#define ll long long
int main()
{
int t;
cin>>t;
while(t–)
{
string s;
cin>>s;
ll c=0;
vector < ll>v1;
v1.push_back(1);
int j=0;
fi(s.size())
{
if(s[i]==’.’)
{
v1[j]++;
//c++;
}
else
{
j++;
v1.push_back(1);
}

	}
	v1.push_back(1);
	for(int i=1;i!=v1.size()-1;i++)
	{
		if(v1[i]<v1[i+1])
		c++;
	}
	cout<<c<<endl;
}
return 0;

}

what the error in this