×

CAKEWALK

# 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

This question is marked "community wiki".

1067915
accept rate: 0%

19.8k350498541

 0 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 answered 08 Jul '15, 13:23 2★viv709 1 accept rate: 0%
 0 https://www.codechef.com/viewsolution/8601701 why its showing tle..!! answered 21 Oct '15, 21:42 11●1 accept rate: 0%
 0 @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. :D answered 22 Oct '15, 00:22 3★harshvk5 3●1●4 accept rate: 0%
 0 thanxx @harshvk5 :P !! answered 23 Oct '15, 15:57 11●1 accept rate: 0%

# include<bits stdc++.h="">

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[i]!='\0';i++) { if(p[i]=='.') { c++; }
if(p[i]=='.'&& i!=0 && p[i-1]=='#')) { c++; }
} cout<<c&lt;<endl; t--;="" }="" }="" <="" p="">

why is this showing wrong answer

1
accept rate: 0%

 0 whats the problem with this one? https://www.codechef.com/viewsolution/12867646 answered 16 Feb '17, 22:32 1 accept rate: 0%
 0 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  answered 16 Feb '17, 22:50 15.5k●1●20●66 accept rate: 18%
 0 http://ideone.com/9y6s24 .... why is it showing tle???????? answered 26 May '17, 00:24 1 accept rate: 0%
 0 why my soln giving WA ? link text answered 21 Aug '17, 20:54 93●3 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,688
×968
×8
×7

question asked: 24 Jun '13, 00:05

question was seen: 4,942 times

last updated: 21 Aug '17, 20:55