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

×

SNAKEEAT - Editorial

2
3

PREREQUISITES - Sorting, Binary Searching, Sliding Window

QUICK EXPLANATION -

Sort the lengths array. For each query K, binary search for the largest element smaller than K and name it cur. Then binary search again on the prefix difference sum array (which will give the number of snakes to be fed to snakes in [prev+1, cur] to make their length at least K) in the region [1, cur] for finding the least index of snake to be killed and let it be prev. The answer is N-prev.

EXPLANATION -

Some key observations before we jump to the solution -

  1. The most optimal choice would be to feed the largest snakes shorter than K[i] on the smallest snakes and to not feed the snakes greater than K[i] in length in $i^{th}$ query.

  2. If we get some X smallest snakes killed for some query K[i], then, for all queries where K[j] > K[i] for some j, we get Y smallest snakes killed where the condition (Y $\geq$ X) will be satisfied.

There are many solutions to this problem some of which are discussed below -

ONLINE SOLUTION -

Let us sort the lengths array as the order doesn't matter for the answer.

Let us solve the problem for a query having its value as K. The most naive solution would be to keep iterating forward from 1 till we reach an element just smaller than K and name this index as cur. Let us keep one more pointer/variable prev which denotes the number of smallest snakes eaten, initially at 0. We will start feeding from $cur^{th}$ snake. Now, to make it of length K, we need to feed it on (K-l[i]) smallest snakes available, where i is initially cur. We increase the prev by (K - l[i]) and decrease i by 1 to reflect this change. We do this process of increasing prev and decreasing i while the condition (i > prev) remains satisfied. Then we print the answer to be simply N - i - 1.

Complexity - $O(Q*N)$

This solution is inefficient but can be passed in TL if we optimise the solution by binary searching the cur and prev as both functions are monotonic in nature.

Now, let us also make a prefix sum array defined as follows -

$$presum[x] = presum[x-1] + (10^9 - l[x]),\hspace{4mm} \forall \hspace{4mm}1 \leq x \leq N$$

For every query having value K, we first find the value of cur by binary searching on length array as it is in increasing order. Then, we also find the largest index prev which is going to get killed. In the naive solution also, we were taking the summation of (K - l[i]) from cur by iterating backwards and set the prev equal to that summation and it can be observed that the function (i > prev) is monotonic as i is decreasing and prev increasing. prev can be found simply by binary searching method on sample space [1, cur]. Binary searching method works because we are finding the smallest j for which the condition

$$presum[cur] - presum[j] - (cur-j)*(10^9 - K) \hspace{4mm} \leq \hspace{4mm} j$$

is satisfied and this function is monotonic with increasing j and then we set prev = j. We want the shortest j as this is the demand of the question to minimize the snakes being eaten OR maximize the snakes of length $ \geq K$ which is (N - j).

The need for the presum array is that it is the number of snakes required to be killed to make the length of snakes in [prev+1, cur] to be more than or equal to K and which is the demand of the question to maximize the number of snakes of length K.

After finding prev, answer is (N - prev) for the query having value K.

Complexity - $O((N+Q)*log(N))$

OFFLINE SOLUTION -

Let us again sort the length array in increasing order as the order doesn't matter. Also, let us sort the queries array along with their indices in increasing order of K values. Hence, a 2-pointer offline solution will be to maintain 3 variables - cur, prev, prefix - where cur means that $cur^{th}$ element is the largest element smaller than K value of current query which we are processing. prev refers to the largest index smaller than cur which is killed and can also be said that prev smallest snakes will be killed. Another thing to observe is that cur and prev can only increase if the queries are sorted according to K value of queries according to observation 2.

Let us assume that currently we are processing answer for $j^{th}$ query in sorted order. prefix refers to

$$ \sum \hspace{2mm} (K[j] - l[h]), \hspace{4mm} \forall \hspace{4mm} cur \geq h > prev $$

To calculate prefix, we keep on increasing cur and update prefix by adding (K[j] - l[cur]) to prefix till we get l[cur+1] to be greater than K[j]. Then, We keep on increasing prev and keep updating prefix by subtracting (K[j] - l[prev]) while (prefix > prev). Then we get the answer for that query to be simply (N - prev) as prev refers to the largest index of snake which will be killed. Before proceeding to the next query, we also update the prefix by adding
[(cur - prev) * (K[j+1] - K[j])]. The need for the prefix is that it is the number of snakes required to be killed to make the length of snakes in [prev+1, cur] to be exactly equal to K[j] and which is the demand of the question to maximize the number of snakes of length K[j].
Remember, that we sorted the query and length arrays both in increasing order.

Complexity - $O(N*log(N) + Q*log(Q))$

There also exists another solution which is to do the naive solution as explained above, but to not do computation again for some K previously encountered. This can be implemented easily by mapping K value of query to its answer and checking everytime before computing answer for a query, that if the answer for same K value has been computed before using a BST (map or set in C++). It can be proved easily that it is also efficient.

Offline solution implementation - here

This question is marked "community wiki".

asked 24 May, 14:35

vivek1_007's gravatar image

5★vivek1_007
7014
accept rate: 0%

edited 25 May, 14:17

@vivek1_007

In most naive solution is the condition i>prev correct? It won't work for the case.

N=9

x x x x x 6 6 6 8

k=8

The answer should ideally be 3, but as per the condition (i>prev) the answer would be 5 if we calculate it as N-i.

(25 May, 08:01) arpit7282★

@vivek1_007

What exactly we are trying to compute in presum array please explain in more detail. why 109- l[i]?

(25 May, 08:04) arpit7282★

@vivek1_007

please explain the condition (prefix > prev)in offline solution. What is its significance.

(25 May, 13:29) arpit7282★

@arpit728

I have followed 1-based indexing, so you will get 4 as the answer. But, the actual answer is N-i-1, because we are doing an extra iteration. So, you get the answer to be 3. Just updated it.

(25 May, 14:17) vivek1_0075★

@vivek1_007

Can you please refer this link, I have posted a question.

https://discuss.codechef.com/questions/98924/doubt-in-snakeeat-editorial-from-snackdown

I have some more doubts.

(25 May, 15:16) arpit7282★

I used merge sort and binary search in my code, still I was getting Time Limit Exceeded error My code

(26 May, 20:27) avinash802★
showing 5 of 6 show all

@jeetu86044 As mentioned in my comment Mo's algorithm almost always involve offline solutions.

Question -- DQUERY

Explanation for mo's algorithm and a bit of offline queries is given in this blog.

link

answered 24 May, 20:06

sdssudhu's gravatar image

5★sdssudhu
72429
accept rate: 13%

getting TLE using binary search and sorting,but i havent store the query result in array and check again for previous encountered query in array thats why i am getting tle?

link

answered 24 May, 17:33

vivek96's gravatar image

2★vivek96
51818
accept rate: 7%

What do you mean by online and offline solutions?

link

answered 24 May, 18:14

manjrekarom29's gravatar image

3★manjrekarom29
212
accept rate: 0%

1

Online solution is a solution in which you are answering a query simultaneously as you are accepting them as input OR you are answering each query before accepting next query as input.

Offline solution is a solution in which you are first accepting all the queries as input, then do something with that and then answer queries in one go.

(24 May, 18:25) vivek1_0075★

So that means I have always written online solutions. But it's specifically said "Online" or "Offline" sometimes like in GPD. Does it mean anything? Does it add additional constraints? I can't possibly see any difference in run time myself.

(24 May, 18:29) manjrekarom293★

Offline and Online solutions will usually involve completely different strategies. The GPD question mandated an online solution to make sure the only possible strategy followed is that of persistent data structures. :) And yes, if your code got the value of K and immediately printed its answer, before getting the next K value , it was an online solution! :)

(24 May, 19:11) akshayvenkat975★

Common examples of offline processing are questions involving mo's algorithm. On a side note GPD can be solved online without persistent data structures.

(24 May, 19:37) sdssudhu5★

can you provide some examples of offline solution ?

link

answered 24 May, 19:51

jeetu86044's gravatar image

4★jeetu86044
91
accept rate: 0%

why TLE in my code,please somebody explain https://www.codechef.com/viewsolution/13773134

link

answered 24 May, 19:57

vdrago's gravatar image

0★vdrago
1
accept rate: 0%

You are sorting the array repetitively unnecessarily every time after each query, thus TLE.

(25 May, 04:21) vivek1_0075★

Hi, I tried similar approach. Tried some test cases all passed. Can you give me some test case for which my solution is failing? https://www.codechef.com/viewsolution/13767521

link

answered 24 May, 19:59

grajesh's gravatar image

3★grajesh
1
accept rate: 0%

@grajesh you sorting the array repetively for each test in loop for(p=0;p<q;p++).Instead sort the array outside the loop only one time .Hence your solution has time complexity O(q*(nlogn+n))

link

answered 24 May, 20:32

sonu_628's gravatar image

4★sonu_628
1928
accept rate: 9%

edited 24 May, 20:35

Answer is hidden as author is suspended. Click here to view.

answered 24 May, 22:08

raj79's gravatar image

4★raj79
(suspended)
accept rate: 11%

"The most naive solution would be to keep iterating forward from 1 till we reach an element just smaller than K and name this index as cur."

"For every query having value K, we first find the value of cur by binary searching on length array as it is in increasing order."

According to the definition of cur mentioned in the editorial, for array [11,13,13,13,14], cur would be $4^{th}$ element.

(25 May, 04:26) vivek1_0075★
Answer is hidden as author is suspended. Click here to view.

answered 24 May, 22:12

raj79's gravatar image

4★raj79
(suspended)
accept rate: 11%

It means that the sample space of binary search is [1, cur] and the difference sum array will give the number of snakes to be fed to snakes in [prev+1, cur] to make their length at least K where prev refers to the largest index smaller than cur which is killed and can also be said that prev smallest snakes will be killed. For more clarity, please read the explanation part.

(25 May, 04:30) vivek1_0075★

What's wrong with my python code...Any kind of a help is most welcomed https://www.codechef.com/viewsolution/13774246

link

answered 25 May, 08:05

sharmarahul's gravatar image

0★sharmarahul
1
accept rate: 0%

@vivek1_007 According to your third solution, which uses some sort of a BST, can you please provide the proof why the solution will fit in TL supposing all the values of $K$ are distinct ?

link

answered 25 May, 11:46

nikhil_chandak's gravatar image

4★nikhil_chandak
3712
accept rate: 23%

edited 25 May, 11:48

why is the code showing TLE..plz explain..link to code --> https://www.codechef.com/viewsolution/13750899

link

answered 25 May, 13:17

abhihacker02's gravatar image

4★abhihacker02
11
accept rate: 0%

Can anyone tell me any test case for which my code is failing. I have used sorting and binary search and I tried all combinations of test cases I could think of and all are passing. I got a WA for this code - https://www.codechef.com/viewsolution/13767521 . Any help is welcome. Thanks

link

answered 25 May, 14:08

grajesh's gravatar image

3★grajesh
1
accept rate: 0%

@grajesh

Input:
1
10 1
1 2 3 4 4 5 5 5 5 7
7

Your code answers 3. The right answer is 4.

(25 May, 19:31) tony_hager5★

@tony_hager thanks a lot for this.

(26 May, 18:31) grajesh3★

Can anyone please explain why am i getting TLE in my code. https://www.codechef.com/viewsolution/13706936

link

answered 26 May, 00:41

daaku_97's gravatar image

3★daaku_97
1
accept rate: 0%

I have used suffix sum instead of prefix.I have tried running many test cases but have not been able to spot the problem. I am getting a WA. https://www.codechef.com/viewsolution/13765159 Can anyone please point out what's the problem in my solution?

link

answered 26 May, 15:08

zenith_dj's gravatar image

3★zenith_dj
1
accept rate: 0%

Are there any special test cases we need to consider for the online solution? We use the same approach in our submission (for Java); we also test with our own test cases and it's seemed ok. But the submission is still WA. Here is our code: link text. Thank you in advance.

link

answered 26 May, 17:38

victor_arsenal's gravatar image

0★victor_arsenal
1
accept rate: 0%

@victor_arsenal, I have run your program against my test files and it gives exactly the same output as my own program, which got AC.

(26 May, 20:50) tony_hager5★

wow, strange. When I submitedt it in the contest, it returned WA. Anyway, thank you very much.

(26 May, 21:05) victor_arsenal0★

why TLE in my code pls help me https://www.codechef.com/viewsolution/13686479

link

answered 26 May, 19:06

akshaycs's gravatar image

4★akshaycs
11
accept rate: 0%

I think observation 2 is incorrect. Consider the following case:
Snake lengths: [1,2,3,6,7,9,10,21]
Queries: [10,21]

In the case of query one, K=10, 4 snakes are killed.
In the case of query two, K=21, none of the snakes is killed.

link

answered 26 May, 19:19

mahipjain's gravatar image

4★mahipjain
11
accept rate: 0%

edited 26 May, 19:23

@sharmarahul liscut and lisrem dont get updated in 3rd case since k1>snakelist[i] for every i hope it helps

link

answered 26 May, 21:39

vdrago's gravatar image

0★vdrago
1
accept rate: 0%

@vivek1_007 In Online Solution, could you please explain why you defined prefix sum as
presum[x]=presum[x−1]+(109−l[x])
instead of
presum[x]=presum[x−1]+l[x]

link

answered 26 May, 23:18

ksmukta's gravatar image

3★ksmukta
111
accept rate: 0%

In case of offline solution how to find largest element smaller than K value of current query which we are processing?

link

answered 30 May, 14:19

amanawasthi96's gravatar image

2★amanawasthi96
151
accept rate: 0%

As requested, here is a video editorial on this:

Snackdown: SNAKEEAT - Video Editorial

We use the binary search approach here to solve the problem.

Cheers! :-)

link

answered 31 May, 23:22

gkcs's gravatar image

5★gkcs
2.4k11025
accept rate: 9%

Thank you for your videos. I think it will be great if you do some hard problems or problems based on some rare topic :) Keep up the good work!

(01 Jun, 00:14) ista2000 ♦5★
1

Hi @ista2000, Thanks for the feedback! There are some hard and rare problems picked up on the channel: Mo's Algorithm with Updates, Fourier Transform, Persistent Segment Trees etc... You could have a look at them.

(01 Jun, 03:33) gkcs5★

I haven taken a different approach to solve the problem, the idea: for each number of eaten snakes compute the length of the smallest remaining snake and store it in an array. All what needs to be done for a query k is to binary search that array for the fist entry >= k and return n-index.

When submitting the solution I encountered the following strange behaviour:

I get a TLE for the original solution (see my solution).

I produced a WA "on purpose" by not considering the last query in the last testcase (see without last query). BUT I get the WA at a time of 0.23 seconds - hence pretty fast. I came to the last solution but optimizing my first one through many steps and the time when I got the WA on purpose constantly decreased (started with 3 seconds and went through 0.99, 0.3 til 0.23).

Can anyone explain this behavior to me? I can't imagine a single query causing the time difference from 0.23 to TLE. Am I missing something? Or are the times for WA not representative? But somehow they are, because times decreased as I optimized my solution.

Would be glad for any ideas which give some insight on this!

link

answered 02 Jun, 19:19

tutux's gravatar image

3★tutux
111
accept rate: 0%

What is presum[0]?

link

answered 17 Jun, 18:00

cabaza's gravatar image

2★cabaza
1
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:

×11,590
×2,610
×594
×535
×40
×22

question asked: 24 May, 14:35

question was seen: 4,320 times

last updated: 17 Jun, 18:00