ATTIC - Editorial

ad-hoc
attic
cakewalk
cook35
editorial

#1

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* == '#')
			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

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


#3

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


#4

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


#5

thanxx @harshvk5 :stuck_out_tongue: !!


#6

include

using namespace std; int main() { long int t,i,c; char p[5000000]; cin>>t; while(t>0) { c=0; gets(p); for(i=0;p*!='\0';i++) { if(p*=='.') { c++; }
if(p*=='.'&& i!=0 && p[i-1]=='#')) { c++; }
} cout<<c<<endl; t--; } }

why is this showing wrong answer


#7

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


#8

@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

#9

http://ideone.com/9y6s24
why is it showing tle???


#10

why my soln giving WA ?
link text


#11

#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