Shayan's blog

By Shayan, 14 months ago, In English

Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.

2070A — FizzBuzz Remixed

Video

2070B — Robot Program

Video

2070C — Limited Repainting

Video

2070D — Tree Jumps

Video

2070E — Game with Binary String

Video
  • Vote: I like it
  • +28
  • Vote: I do not like it

| Write comment?
»
14 months ago, hide # |
 
Vote: I like it +49 Vote: I do not like it

Am I the only one who thought that in C you need to find the SUM of penalties?

»
14 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I initially thought D was a combinatorics problem and got WA several times, but now I see it's actually DP.

»
14 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

D is easier than usual and I'm completely stuck by the problem E. I try to guess the conclusion, but failed finally.

»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

FOR 2070D — Tree Jumps

I know it's a DP question, but I approached it more like a combinatorial problem and got a WA as a result. I want to understand why I got WA. Can anyone provide a test case where my approach fails or explain the reason behind it?

308241176

»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

When could the text editorial be visible awa?

»
14 months ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

Problem B doubt

def s_extend(s, n, k):

quo = k // n 
rem = k % n 
return s * quo + s[:rem]

t = int(input())
for i in range(t):

n, x, k = map(int, input().split()) 
s = input() 

s_n = s_extend(s, n, k) 

pos = x
cnt = 0
rp = 0

while k > 0:
    if s_n[rp] == 'L':
        pos -= 1
    elif s_n[rp] == 'R':
        pos += 1

    if pos == 0:
        cnt += 1
        rp = -1

    rp += 1
    if rp == len(s_n):
        rp = 0

    k -= 1

print(cnt)

For problem B, how can you optimise further ?? Got TLE on Test 1 last input.

  • »
    »
    14 months ago, hide # ^ |
    Rev. 2  
    Vote: I like it +1 Vote: I do not like it

    Your code runs for k which can be 1e18, what you can do to optimize is to find the first time it will cross origin let it be t1 and then find the first time it will come again to origin let it be t2. Now in this case the counts will be like t1+t2+t2+.....<=k the number of terms in this is our answer or you can say 1+(k-t1)/t2 My Code : 308252587 Feel free to ask if any doubt