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)
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?
please add “unofficial” to heading. btw, good work.
Thanks…!!!
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.
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.
Thanks…!!!
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?