The first problem was easier while the second one involved some math and big modular arithmetic. I solved just the first problem. Will I possibly qualify ? Also, how did you solve the problems ?
Same here ,the second problem was a bit tricky. Felt a bit sad . 
. Could have done better.
Ya, once I heard the logic, it felt but-obvious, but then, the past is past…
About the 2nd problem, I was trying something like this, but I couldn’t implement in the exam (so no use basically). Only now, I got clarity in what exactly I was thinking then.
Number of non periodic strings for ‘n’ = 2^n - (Sum of Number of non periodic strings for each factor of n other than n)
If it’s wrong please feel free to disprove it.
Also, how did you solve the first problem? I could only think of an O(N^2) algorithm which would pass the first sub task.
I calculated the cumulative sum of b array at each index. Then I had a loop with i running from 1 to N and an inner loop with j running from i+1 to N and similarly a loop with i running from N to 1 and inner loop with j running from i-1 to 1 and accordingly updated maximum based on Ssum[i,j]. And another loop to update maxi based on the value of a[i] alone. Won’t pass, I am sure.
I spent around 1 hour debugging my first problem’s code, even though it was a useless solution only to find I had interchanged a + and - somewhere in between. And I was messing up the pow function in 2nd one.
Could have done heaps better. My mind seems to work better after the exam, I guess plenty of timed contests is the way to go for me 
I did 1st one. It was a nice DP. First calculate the maximum sum possible for i less than j using Kadane’s algorithm (had to modify it a bit). For i greater than j, precalculate the maximum sums possible and traverse the array one. Overall complexity O(n).
Couldn’t solve the 2nd problem completely. Solved first subtask using Inclusion Exclusion Principle. Since w = v^n. Therefore |w| = n|v| where |s| denotes the length of string s. So for n>=2, find all factors of |w| and use IEP to find all the possible periodic strings. Now in the end subtract this value from 2^n.
Another answer: Here we will consider ‘1’ as a prime number. Now the total periodic strings will be:
2^p1 + 2^p2 +… - 2x(k-1) where k are the number of prime factors of n (including 1 and excluding n). SO the answer will be 2^n - (2^p1 + 2^p2 + … -2x(k-1))
About the cutoff, I think it will be around 130-140 this time :’(
I initially did some inclusion exclusion nonsense for the second problem, but that turns out to be totally wrong. Wasted 1.5 hours doing that.
Finally I decided to at least do the 65 mark subtask with what I thought was an O(N^2) algorithm. Your DP is correct as far as I know. You have to find all the divisors for all the divisors of N. I assumed this takes N^2 time, but apparently not - it worked for all subtasks.
I even checked by running my program on all possible inputs (n = 1 to 150000) and it was taking maybe 1 second to run for 100 n’s even close to 150000.
I honestly doubt it’s going to be more than 125 (all subtasks but the last on each problem). It’s always been 100 in the past. You overestimate how much others are getting
It’s right? But I didn’t implement it. I wasted time on the 1st one, 1st subtask. How bad is that?
As far as the cutoff is concerned ,I think it will be >=125, considering most of the students solving the first question correctly ,and the second question … duh … say most with subtask 1 correct.
Could have been selected , if had may be 1/2 hrs more … but yeah … past is past…
You have two years to go, don’t worry
Did anyone feel that the sample testdata for Subtask 3 (and maybe 4 also) of Problem 2 was incorrect?
I think one of them at least is easy to prove wrong.
Input:
1260 99999989
Output:
3323612
(2^1260) mod 99999989 is 3007916. So their answer is more than 2^n, not possible.
I know its mod, but there’s no way that the amount you have to subtract is 99684293, that’s way too large.
Really crossing my fingers that those answers were wrong, I attempted only Problem 2!
I do hope so. Expecting 130. You?
That’s exactly how I did it; it’s not O(N^2) because the number of factors a number has is very small. See bounds on omega (n).
@sandy999 Yeah, that was more or less the way I did it, except I grouped the factors by prime numbers and took away all the strings of that length, not just non-periodic strings.
200 unless I made stupid mistakes
Yeah I assumed it was something to that effect but I wasn’t really sure. I assumed that some number might exist for which the time taken is quite high, but nope.
Ah, I blooped on problem 1. Curse me.
I won’t be getting more than 100, does that mean I’d fail to qualify ? (if only I’d studied Maths more)