Here is the worst solution for 1st sum which i did.
Dp[i][j][k] denotes the minimum number of boxes taken upto ith day such that u have a balance of j,and k denotes if on that day a box is taken.
Dp[i][j][0]=min(dp[i-1][j+k][0],dp[i-1][j+k][1])
Dp[i][j][1]=min(dp[i-1][j-(n-k)][0],dp[i-1][j-(n-k)][1]) + 1
Dp[i][j][1]=inf for i%7==0
Really good solution @taran_1407.
I think the 3rd problem can be solved using dp.
We’ll take the two cases(a1a3… and a1>a2<a3…) separately.
Let dp[i][j] denotes the minimum swap needed to make array great for indices 1 to i and N-i+1 to N with j denoting if this element is swapped or not.
We start from left and move to center.
We have following recurrence:
Val1=dp[i-1][0],val2=dp[i-1][1]
dp[i][0]=min(val1,val2) here first u should check if these satisfy the relations(i mean lets say if i-1 is not swapped then check a[i-1],a[i] and a[N-(i-1)+1],a[N-i+1]) if they dont accordingly set val1 Or val2 to inf.
Similarly,
Dp[i][1]=1+min(dp[i-1][0],dp[i-1][1])
My ac solution(though implemented now and not in contest):
https://www.codechef.com/viewsolution/17125237
Edit:This solution should fail since i didnt consider the case for -1 when n>=4 and n is even and middle 2 elements are same
(Lucky)
My both Solutions got AC in one go.
Problem: SURVIVE
My short solution in PYTHON-3.5:Mine is O(n) could be done in O(1) also.
te=int(input())
for _ in range(te):
n,k,s=input().split()
n,k,s=int(n),int(k),int(s)
capacity=k*s
availablity=n*s
availablity-=n*(s//7)
maans=0
if(capacity<=availablity):
answer=0
counter=0
for i in range(s):
counter+=1
counter%=7
if(counter!=0):
maans+=1
answer+=n
if(answer>=capacity):
break
print(maans)
else:
print("-1")
LOGIC:-
Maxmimum choclates he needs is ks which is capacity. And the availablity of chocolates is ns-(n(s//7)) as on Sunday shop is closed and he can’t buy any chocolates. So if capacity > availablity print(“-1”) as it is not possible to purchase. Else Run a loop to find the number of days and dont forget not to calculate sundays and add n chocolates only on non sundays.*
Problem: MULTHREE
My Short solution in PYTHON 3.5:-Time Complexity O(1)
test=int(input())
for y in range(test):
k,dig0,dig1=input().split()
k,dig0,dig1=int(k),int(dig0),int(dig1)
sum1=dig0+dig1
for i in range(3,k+2):
y=sum1%10
sum1+=y
if(y==2):
ter1=((k-i)//4)
ter1*=20
sum1+=ter1
ter=k-i
if(ter%4==3):
sum1+=18
elif(ter%4==2):
sum1+=12
elif(ter%4==1):
sum1+=4
break
if(y==0):
break
if(sum1%3==0):
print("YES")
else:
print("NO")
LOGIC:-
For a number to be divisible by Three sum should be divisisble by 3.Keep on adding sum and finding digits(sum%10); if digit is 0 then break as sum will remain same even after u do any operation so break.
Else break when u find a two as 2,4,8,6 block will keep on repeating. therefore add ((k-i)//4)(2+4+6+8)
to sum ((k-i)//4) is floor division plus remaining 4 12 or 18 depending on whether 4 or 4,8 or 4,8,6 is remaining. This block’s size is got by (k-i)%4.Then at last check whether sum is divisible by 3.
Essentially almost same as solution of @taran_1407
Like,Comment, Follow and award reputation points if u like. For any other queries or doubts contact me.
For Codes as files to download visit:-
THIS PAGE
The first problem can be solved in O(1) time complexity per test case,
here is my code in cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
int n,k,s;
cin>>n>>k>>s;
int sundays = s/7;
int TOTAL = k*s;
int buy = n*(s-sundays);
if(buy < TOTAL){
cout << "-1" << endl;
}else{
cout << ceil(float(TOTAL)/n) << endl;
}
}
return 0;
}
The logic: If total number of chocolates needed for S days is MORE that the number of chocolates possible to buy in that (S-number of Sundays) days then it isn’t possible to survive, else it is just ceil(float(TOTAL Needed chocolates)/(maximum number of chocolates possible to buy per day i.e. N )) … ceil() function is used as integer division will exclude some days at the end. i.e. a box of chocolates should be bought at the day number of chocolates left is less than K.
When will the editorial for problem MAGA be up ?
Do they plan to release the official editorial for the MAGA problem? -_-
I followed a bit general approach for the second problem as I didn’t have enough time to actually think of all the edge cases. So I saw in the test cases that after the 3rd element there is a pattern. So I stored that pattern in a vector and checked how many times it will get repeated in the final number.
And then I just added first three numbers+(sum of vector)*(number of times it is repeated in the final number) + remaining numbers.If this sum is divisible by 3, then the answer is YES otherwise,NO.
Here is the solution
Solution
Doesn’t change the solution though!!
Yupp.The solution remains same.
Buy everyday, because if you don’t buy everyday, it may cause problem on coming Sunday. Take care to exclude X boxed later only if you can survive.
Second thing, why diff is initialized to N?? It should be 0.
for e.g if i take the test case 13 10 8
then on the first coming sunday the chocolates we would be having are less than k. So the answer should be -1. But the correct answer is 7. What am i missing? coz for this test case my code is giving output as -1
Please post it at the announcement thread- which is the official thread for feedback. It will be seen by problem setting panel there.
I wasted two hours on third problem messing with if else blocks. and yes, if i manage to solve it soon (by tomorrow i mean) i will write editorial.
Glad you liked it!!
Same here buddy. My entire time whooshed away in those if else. BTW, check out this solution, you might like it-
Here’s the simulation of first 7 days for your TC. Set dif = 0, count = 0,
Day 1:
diff = diff+10-8 = 2, count = 1
Day 2:
diff = 2+10-8 = 4, count = 2
Day 3:
diff = 4+10-8 = 6, count = 3
Day 4: diff = 6+10-8 = 8, count = 4
Day 5: diff = 8-8 = 0, count = 4 Your mistake, as you didn’t buy this day and later on concluded insufficiency of sweets.
Day 5: diff= 8+10-8 = 10, count = 5
Day 6: diff = 10+10-8 = 12, count = 6
Day 7: diff = 12-8 = 4, count = 6.
Hope this makes clear.
And to all who read this comment, if stuck in a simulation, use print statements to do all this. 
Very much liked it @vijjju123 !! Just loving it…
A 200-line solution shoved under the nose of an innocent boy. 
Though your solution is nice one, it have a worse Time complexity of O(Slog(7*S)) while above mentioned solution has time complexity of O(S).
You can improve your check function to work in O(1) by a simple change, and even shorter code.
I think binary search is an overkill here. But well, Binary search is <3 .