"DETAILED" EDITORIAL to MAXEP Problem - December Long 2018

It is seen that minimum number of coins are used up when the gaps we choose are the square root of N, as @vijju123 mentioned.

The constraints were very beautiful in this question, isn’t it??
1,50,000(n) = 150© * 1000(coins)

All i did was divide N in the range of 1000.
Like let us say n=100005.
So, ranges are= 1-1000, 10001-2000, 2001-3000,…upto 99001-100000, 100001 - N.

We check on the upper limit of each range. the first time we get a 1, we don’t check afterwards as our answer is between this upper limit and the upper limit of the previous range.

In this range finding process, we will use atmost (150 x 1 + 1 x c) coins, i.e atmost 300 coins.
Now, we have a range of 1000 numbers (just like N=1000 ) from which we have to find our answer.

Then we apply binary search 2 times in this range to decrease our range of values to 250.
coins used=300(previous)+300(current)=600.

So,600 coins have been used up and we have a range of 250 numbers. Here we apply linear search in that range.

So, max coins uded=600(previous)+249(linear search)+150(when the output is 1)=999 coins.

THUS BY USING MAX 999 COINS, WE HAVE FOUND OUT THE ANSWER.

I solved the problem by doing ternary search (1:3 ratio) till I have left with n elements in search range and n <= c. Then I did linear search with c coins in my hand.

You can find the accurate range by DP :). That’s what I did, finding out that for the max test case you need a minimal of 693 coins to solve.

We can also just do binary search with ratio 1:7

To the earlier comment by @shoom:

I don’t think 450 coins constraint is feasible. According to my calculations, it’s 457 coins. For such constraint, you can do the following:

  • Check the circuit on 2500, 5000, 7500, …, 147500 voltages. That’s 59 points to check, or 59 coins. You may break it once, and that’s extra 150 coins to shell out. You check with such interval only up to the breakage.
  • Now the interval to check is 2500 units. Split it in blocks of 50, so if you break the circuit at 7500, then you need to check at 5050, 5100, 5150, …, 7450. That’s another 49 coins. Again, you may break it once; that’s an extra 150 coins.
  • Now the interval is only 50 units. You need to check the first 49 points to figure out the maximum voltage - or another 49 coins.

The total expense: 59+150+49+150+49 = 457 at most.

Another better approach to this question is Square root decomposition method. I divided the array of length n into \sqrt n divisions of length \sqrt n. Now we need to now check the voltage at the mean value of voltage of every division. If it dosen’t burn out go for next division else apply linear search for this division.
Time complexicity is O(\sqrt n)

here is easiest solution
https://www.codechef.com/viewsolution/21822674

Simply check in the intervals. What I did was checked in the intervals of 1000. then in a particular 1000 range. Eg:- 1 1000 THEN FEED 1 2000 and so on till you get 1. We will know the thousand range through this. Now say you get 1 for 1 7000, this means the voltage lies between 6000 and 7000. Now check for 100 range that is
1 6000, 1 6100 etc… You will get the final 100 range. Do the same for 20 range and 5 range. Now you will have 5 elements left. Check them one by one. The worst case possibility will occur for n=150000, c=150. Even the worst case will consume 168+4*c i.e 768 coins

150000 was a very very loose limit. I am pretty sure it could have been at least 10^8 within 1000 coins.(c=150)

Here’s my solution that would work for up to 10^11 in place of 150,000.

Let’s reverse the problem and ask the following question: If we have 1000 coins initially, what’s the largest value of N for which we’d be able to always find the smallest voltage that breaks the panel. Clearly, this value is at least 150,000, since the problem statement suggests there’s always a solution. Let’s generalize this question and ask the same for any number of initial coins <= 1000. Call this function f. Let’s see how to compute f[m], where m denotes the initial number of coins:

  • If the initial guess is X, 2 things can happen:
    (1) The response is 0, meaning the resulting voltage is in range R = [X + 1, f[m]] . In this case, we would be left with (m - 1) coins. By definition, we can guess from at most f[m - 1] values, so |R| <= f[m - 1], where |R| denotes the number of integers in range R.

(2) The response is 1, meaning the resulting voltage is in range L = [1, X]. In this case, if X > 1, we need to repair the panel and pay the penalty, which leaves us with (m - 1 - c) coins. By definition, X <= f[m - 1 - c].

  • Combining these 2 scenarios, taking X = f[m - 1 - c] maximizes f[m]: f[m] = f[m - 1] + f[m - 1 - c].

By precomputing this array, we see that the value of f[1000] can become quite large. For c = 150, f[1000] = 422250194531.

The way we constructed f[m] also shows the algorithm which will help us to find the minimum voltage that breaks, without violating rules:

  • Initially, the range of possible voltages is [1, N]. The range will keep shrinking as we make guesses.
  • Let’s say the current range is [low, high] and we have M coins left. Let’s look at the value of f[M - 1 - c]. By making our guess (low + f[M - 1 - c] - 1), we guarantee that after this move we’ll either have (M - 1) coins and a range with length <= f[M - 1], or f[M - 1 - c] coins and a range not larger than f[M - 1 - c]. In both cases, we’ll be able to find the answer without a doubt.

I omitted some base cases to keep it shorter, but here’s my implementation for more details. Hope it was helpful and feel free to ask questions if something’s unclear. Cheers!

A previous IOI gold medalist told me that there’s a similar problem in POI:
when the voltage is too high, we get a penalty of A dollars
when the voltage is too low, we get a penalty of B dollars

The interesting thing is that the best strategy is to guess with a ratio 1:\alpha, where \alpha is the root of the equation

x^A+x^B=1

so in the original problem, I used wolfram alpha to solve x+x^{150}=1 (it should be x+x^{151} in fact) and got the magic number 0.97556.
Here’s my code:
https://www.codechef.com/viewsolution/21774242

I could not get this question right (I tried myself many values(testcases) and they were correct but still codechef said wrong answer?
can anyone please tell mistake in my code of MAXEP?

Similar to egg drop problem. As good as finding on which floor among 150,000 floors the egg will break with 6 eggs at most (1000//150). Can be solved with dp.

@shashank_chugh

In the condition checking of the for loop, you are comparing s against an uninitialised variable (e). That seems to be (one of the) problems.

I simply divided n into blocks of 500. if i get 1 from grader i divided it again in parts of 100 for reducing the time complexity#include <stdio.h> #include <stdlib.h> int main() { int n,c,x=1000,max=1,k,i,j,flag=0; scanf("%d %d",&n,&c); int b; i=1; while(i<=150000) { x=x-1; printf("%d %d\n",1,i); fflush(stdout); scanf("%d",&b); if(i+500>n&&b==0) { for(k=i;k<=n;k++) { if(k<=0) continue; else { printf("%d %d\n",1,k); fflush(stdout); scanf("%d",&b); if(b==1) { printf("2\n"); fflush(stdout); printf("%d %d\n",3,k); fflush(stdout); flag=1; break; } } if(flag==1) break; } } if(flag==1) break; if(b==1) { printf("2\n"); x=x-c; fflush(stdout); for(j=i-500;j<=i;j=j+100) { if(j<=0) continue; x=x-1; printf("%d %d\n",1,j); fflush(stdout); scanf("%d",&b); if(j+100>n&&b==0) { for(k=j;k<=n;k++) { scanf("%d",&b); if(b==1) { x=x-c; printf("2\n"); fflush(stdout); printf("%d %d",3,k); fflush(stdout); flag=1; break; } } } if(flag==1) break; if(b==1) { x=x-c; printf("2\n"); fflush(stdout); for(k=j-100;k<=j;k++) { if(k<=0) continue; printf("%d %d\n",1,k); fflush(stdout); x=x-1; scanf("%d",&b); if(b==1) { x=x-c; printf("2\n"); fflush(stdout); printf("%d %d",3,k); fflush(stdout); flag=1; break; } } if(flag==1) break; } if(flag==1) break; } if(flag==1) break; } i=i+500; } return 0; }

What if when -1 strikes you have to search left and right both way??isnt it?

In my code , I used random function as a way to get an arbitrary no as specified in one of the constraints.
Here is my code : CodeChef: Practical coding for everyone

I think using srqt decomposition would be better, as you only need to burn the panel 2 times to find the right voltage, regardless of the cost.
This seems more likely what one would do in real life, instead of burning the panel many times for no reason as happens in binary search approach (with ratio)…

Can you please tell how you derived the ratio??