We invite you to participate in CodeChef’s Starters 50, this Wednesday, 3rd August, rated for Div 2, 3 & 4 Coders.
Time: 8 PM — 11:00 PM IST
Joining us on the problem setting panel are: - Setters: Utkarsh Utkarsh.25dec Gupta, Abhinav abhinavvv306 Sharma, Shanu ShanuSingroha Singroha, Tejas tejas10p Pandey, TheScrasse TheScrasse, Ashish Kryptonix Gangwar, Pratik i.am.pratik Kumar
Testers: Utkarsh Utkarsh.25dec Gupta, Nishank IceKnight1093 Suresh
Statement Verifier: Nishank IceKnight1093 Suresh
Editorialists: Pratiyush foxy007 Mishra
Contest Admins: Abhinav abhinavvv306 Sharma, Tejas tejas10p Pandey
The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.
Also, if you have some original and engaging problem ideas and are interested in them being used in CodeChef's contests, you can share them here.
Hope to see you participating. Good Luck!
Hopefully no error 403 this time
The live rating graph is a very cool feature!
How to do
ADDSUBTRACT?The idea I used is basically:
In this way, the whole range of numbers in array will get halved each time I will do these $$$2$$$ operations, thus a total of $$$2 \log(\max(a_i))$$$ operations.
But, I don't know where I am wrong. It is failing test cases $$$12, 13, 18, 19$$$.
Submission.
If it helps, this was the test case: link.
Basically it contains only powers of 4.
Dang it, I thought I am halving the range each time, but this isn't true in this test case. Thanks a lot, man!
I have optimized my operations a bit, and it passes test cases 12, 13, 19. However, it is still failing test case 18, what could be that test case ?
I feel that test case 18 is a bit large one, because it's runtime is maximum..
Submission.
Here is the test case: link
As far as I remember it contains many numbers <=1000 and very few numbers closer to 1e5 and nothing in between.
How to solve Beautiful Array?
Observation: You have to check only for $$$A[i]\pm 2$$$ where $$$0 \leq i \leq n-1$$$. (Actually in the contest I took the value to be $$$\pm 10$$$ without thinking too much, but I tried now with $$$\pm 2$$$ and it worked, not sure why)
So you would need a $$$2\times 5$$$ $$$dp$$$ array, where: $$$dp[1][j]$$$ $$$\rightarrow$$$ when you add $$$(j-2)$$$ to $$$A[i]$$$, what is the minimum possible answer from all the previously calculated answers (i.e. values calculate for $$$A[i-1]$$$, and stored in $$$dp[0][k]$$$) and such that the condition $$$GCD(A[i-1]+k-2, A[i]+j-2)=1$$$.
Link to submission (I've tried to add comments)