You are not logged in. Please login at www.codechef.com to post your questions!

×

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

This question is marked "community wiki".

asked 24 Jun '13, 00:05

prad_adm's gravatar image

0★prad_adm
1067915
accept rate: 0%

edited 24 Jun '13, 00:27

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 08 Jul '15, 13:23

viv709's gravatar image

2★viv709
1
accept rate: 0%

link

answered 21 Oct '15, 21:42

vishalrox's gravatar image

2★vishalrox
111
accept rate: 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

link

answered 22 Oct '15, 00:22

harshvk5's gravatar image

3★harshvk5
314
accept rate: 0%

thanxx @harshvk5 :P !!

link

answered 23 Oct '15, 15:57

vishalrox's gravatar image

2★vishalrox
111
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

link

answered 09 Jul '16, 11:48

yasheel_10's gravatar image

2★yasheel_10
1
accept rate: 0%

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

link

answered 16 Feb '17, 22:32

ashishgulati21's gravatar image

0★ashishgulati21
1
accept rate: 0%

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

answered 16 Feb '17, 22:50

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 16 Feb '17, 22:54

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

link

answered 26 May '17, 00:24

shubham_2797's gravatar image

1★shubham_2797
1
accept rate: 0%

why my soln giving WA ? link text

link

answered 21 Aug '17, 20:54

deepak_097's gravatar image

4★deepak_097
933
accept rate: 0%

edited 21 Aug '17, 20:55

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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