Shifts Problem Round G - Kickstart

yaa natural me thought of only natural numbers :sweat_smile:

Short summary:

  1. Use sieve logic. easy
  2. Greedy
  3. SOSDP
3 Likes

I memoized my recursive solution for Shifts problem using map of pairs but it gave memory limit exceeded for hidden case . Any reason for that ?

Number of distinct states would be 3^n(~3e9 for n = 20)

For the third one, I used Meet in the Middle!

I thought k = 1 to 100 in the first try got WA then k = 0 to 100 got WA then i thought why and who told me to put max k = 100 then i got it that k can be max 130 for the first subtask and then i tried k = 1 to k = 130 and got 1st test Accepted. Didn’t tried the bigger test case.

1 Like

Can someone please explain the concept behind problem Equation from Kickstart round G, I am really trying hard but I can’t even understand the editorial…
Thanks.

In shifts question my O(3^n) solution passes both test cases(Visible + Hidden). Here is my solution. I think there test cases are very weak for this question.

I also want to know the approach of the second ques the equation. I have a hard time decoding the editorial as well. Help is really appreciated.