CHEFCK - Editorial

editorial
, , , , ,
4

@abhra73 thanks…:slight_smile:

5

Hi, i am stuck at a little awkward problem in this problem, i, after frustration, decided to brute force the problem, and to my surprise i found that whenever i used an array of 1-based indexing my solution were showing Accepted result, but the same code for 0 based indexing isn’t working(but why?), i am still surprised where the problem is please look at the solution, it is in python so it wouldn’t take too long to understand what i did there :slight_smile:
1 Based Indexing CodeChef: Practical coding for everyone
0 Based indexing CodeChef: Practical coding for everyone

6

@lwmarsh06 The generator defined is for generating a 1-based indexed array. Since the index is part of the generator, if you want to generate the same array with 0-based indexing, you were required to modify the generator accordingly which you didn’t.

7

@abhra73 The arrays coming out are almost the same(just in 1 indexing the 0th element is irrelevant),
i tried some test cases, some of my own too, and i found the arrays coming out to be the same, i shifted the variable x from 2 to 1 and x<=n to x<n. Can you please point out the correction and by any chance a test case for which my 0 indexing solution is failing so that i can figure out the difficulty.
I am getting identical answers for both solution on the test cases which i can think of :slight_smile:

8

How much efficient is the sparse table algorithm … can it be used for this case ?

9

I solved the problem during the contest but TLE in the third subtask,Solution which part of the solution need improvement? can someone help me with that?

10

@Sabari You can optimise your solution by using just using the following things::

  1. While generating the array A[] don’t use power() function. since every time t is taken to the power of x which is also equal to the iteration of loop, so simply make a variable and in every iteration of loop multiply it by t.
  2. Use % (modulo) only if a number becomes greater or equal to modulo … ie. if(A[x] >= m ) then take modulo.
    Rest is all fine…I was also doing same mistake…and i’ve done about 60 submissions
    For referance you can see my submission here link text
    link text
11

@madhur123Thanks a lot!!! cleared all sub-tasks. I never knew load posed by mod operation.

12

I used Sparse Table Algorithm and i am not getting why it gives SIGSEGV for subtask 3 (after running for 2 secs). Please help and guide me. Here is my solution : CodeChef: Practical coding for everyone

13

I used Sparse Table Algorithm and i am not getting why it gives SIGSEGV for subtask 3 (after running for 2 secs). Please help and guide me. Here is my solution : CodeChef: Practical coding for everyone

14

I used Sparse Table to solve this problem. Can someone please tell me why I am getting TLE in last test case of third subtask.Here is my solution : CodeChef: Practical coding for everyone

15

I am applying second method still getting TLE for one test case out of 6 solution link rkAgT2 - Online C++ Compiler & Debugging Tool - Ideone.com please help

16

http://www.codechef.com/viewsolution/6980436
could you explain, why isn’t my solution right?

17

@nil96 remove modulo while you are generating array use only once when number exceeds m.i was doing same mistake after 4 days i got this…:stuck_out_tongue:

18

Why my code become accepted instead of TLE/WA ? I just change the portion

A[x]=(a*pm(A[x-1],m) + b*(A[x-1]%m)+c)%m;

/// where pm is a function which make the operation : { b=A[x-1]%m; return (b*b)%m; }

TO

A[x]=(a*A[x-1]*A[x-1] + b*A[x-1]+c)%m;

I think the second one should get WA instead of ACC .
Because (10^9*10^9 *10^9 +10^9*10^9+10^9)% 10^9 will overflow the long long integer’s range.
Am I wrong?
http://www.codechef.com/viewsolution/6980480

19

The last two comments in the code
// Remove the first element of the window,
// and from the list P as well, if it belongs there.
Somebody Please explain that part to me?

20

How am I supposed to solve the problem if I cannot even generate array A and Q queries in the given time for python? http://www.codechef.com/viewsolution/6989977

21

Time Limit was too strict. My solution with correct approach gave TLE in just 1 Task because of using too many mod operations. Wasted 4 days and lost 70 pts :frowning:

22

Another possible way to solve this problem is by using queue with O(1) min. query for sliding window - implementing it with two stacks is a well-known trick: https://www.codechef.com/viewsolution/7645078.

23

I did not understand the question as to how is range min query applicable in this.

Could someone please explain