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

×

Problem in November Challenge 2018,i.e, Appy Loves One.

What is the best algorithm or any short way to solve this problem Appy Loves One ,Please explain.?? I got only 30 pts,for brute force solution??

asked 25 Nov '18, 11:32

siva140191's gravatar image

3★siva140191
1335
accept rate: 12%


The editorial for this problem is here (link), which gives a few possibilities.

My own approach was:
- deal with the cases where there are no ones, one one or all ones
- find the runs of ones, if necessary with wraparound
- sort to find the longest such run and its position, plus the next longest, if any
- track the rotation described in the question as a mark moving through the array (representing the break)
- assess the mark position when a readout is required, to see if it's in the largest run of ones.
- if so, calculate the longest intact run (otherwise the longest run is the answer)

link

answered 25 Nov '18, 12:01

joffan's gravatar image

5★joffan
9488
accept rate: 13%

I think this problem and its editorial definitely will help you.

link

answered 25 Nov '18, 11:35

starboy_jb's gravatar image

5★starboy_jb
111
accept rate: 0%

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:

×2,363
×1,657
×1,389
×847
×135
×67
×4

question asked: 25 Nov '18, 11:32

question was seen: 172 times

last updated: 25 Nov '18, 12:01