REVGAME - Editorial

editorial
, , , ,
1

PROBLEM LINK:
Practice

Author: Rupanjan Hari

Tester: Rupanjan Hari

DIFFICULTY
: Medium

PREREQUISITES
: Math

QUICK EXPLANATION

Basically, what you have to do is if you are given the number of terms in a series, you have to generate the skeleton series first i.e. if N=3 generate 0 1 2
Then, go for 0 1 2 → 2 1 0 → 2 0 1 → 2 0 1

What has been shown over here is

  1. Reverse the series from term t1 to tn
  2. Reverse the updated series from t2 to tn
  3. Continue this process until you reach tn as the starting term.

This way a series of numbers will be generated where you have to search for the index of a specific number (i.e. K in the given problem) to provide as the output.

EXPLANATION

This is hell of an optimization problem where at first it might look easy but when the input number touches 10^3 limit , the game changes. Each output takes more than 6 seconds to generate and this time can even shoot up to 15 seconds for each output. So, I have to find a different way to find the solution to the problem. The solution was to generate the series at one shot else than reversing it for (N-1) times thus decreasing the complexity to O(n) form O(n^3).

If you look at the final series clearly, you can notice that t0 is equal to (N-1), the term followed is equal to (N-1) - t0 and the term followed is equal to (N-2) - t1 and this process follows for alternate index places i.e. if Loop Variable is even t(n)=(N-2) - t(n-1) otherwise t(n)=(N-1) - t(n-1).

Then linearly search the series for the index of the K number.

To make the problem look easy, I have divided the program into functions of appropriate name.

Arrays:

N[] - This array stores the number of terms for each series
K[] - This array stores the number you have to find the index of

Functions:

void reverseBound(long a[],long n) - This function generates the final series at one shot.
void searchField(long a[],long n,long s) - This array searches the **K** field.

SOLUTION:
click here to see the solution