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

×

CHEFSUBA:- Later Part Clarification

Hi,

Here my solution for the problem CHEFSUBA. I can not understand the later part of the problem when k<n. How should we approach it, if k=3 and n=5, should we iterate in this frame for 3(5-3+1) times or take it once, for n, collectively? I have used repetition to avoid the rotation, If any hint/explanation can be provided, It will be great as I desperately want an AC for this problem. :)

asked 23 May, 22:29

abhiroj786's gravatar image

2★abhiroj786
8110
accept rate: 22%


Instead of Segment Tree we can use a Linked List of size of number of frames i.e n-k+1 .Then we calculate maximum from the Linked List.When we perform rotatation we delete the back of linked list and (increment/decrement/no change) to front of the Linked List.We also keep an index for which we have our maximum.If we maximum frame element was at back of Linked List then that would have been deleted in each rotation that means we search linearly along the frames once more.Other case is that back element was not maximum then all we have do it compare with front element which might incremented and hence become the new maximum. Here is code link text

link

answered 24 May, 02:40

sonu_628's gravatar image

4★sonu_628
1928
accept rate: 9%

edited 24 May, 08:00

After using the rotation trick...Create the sum array with the given pseudo code in the editorial.. an element in the sum[i] indicates the number of 1 in the range b[i-k] to b[i] .... create segment tree with the sum array ...ask a range maximum query using the above explanation of "Sum[i]".... Here's my Solution..... https://www.codechef.com/viewsolution/14939652 Feel free to ask anything about this code.. :-)
Hope this help..

link

answered 12 Aug, 23:55

amanharitsh's gravatar image

3★amanharitsh
134
accept rate: 0%

edited 12 Aug, 23:58

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:

×909
×164
×16

question asked: 23 May, 22:29

question was seen: 357 times

last updated: 12 Aug, 23:58