Shayan's blog

Codeforces Educational Round 175 (Div 2) — Video Tutorial
By Shayan, 12 hours 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
  • +34
  • Vote: I do not like it

»
6 hours ago, # |
  Vote: I like it +34 Vote: I do not like it

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

→ Reply
  • »
    »
    6 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    me also bro and wasted almost one hour

    → Reply
  • »
    »
    6 hours ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    -100 elo or so just because I forgot to read

    → Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    If you think like this, you need to use simulated cost flow, wqs binary, and use line segment trees to prevent running timeouts, which is a bit difficult for a C problem.

    → Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    also do i ^.^

    → Reply
  • »
    »
    3 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    no, you are not alone... π π

    ...
    → Reply
»
6 hours ago, # |
  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.

→ Reply
»
5 hours ago, # |
  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.

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, after reading the problem statement Minimum Maximum Penalty I thought of using Binary Search because I just remembered it XD. However, during the contest, I was unable to prove the monotonicity. Can someone please explain the monotonicity before applying binary search to me?

→ Reply
»
2 hours ago, # |
  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

→ Reply
»
109 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

When could the text editorial be visible awa?

→ Reply
»
104 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

I can not think of a way to understand A intuitively, except when I use chines remainder theorem that for a system of congruent (in this case 2 equations) with co-prime moduli (3 and 5), then we always have a unique solution mod 3*5 = 15. Then we can think of if we traverse i from 0 -> 14 and for each i, we have a = i mod 3 and b = i mod 5 then the pair(a, b) will be unique in range [0, 14] and this pair only repeat each interval of 15.

=> We just need to find the pairs of form (a, a) in the first interval from 0 -> 14 (only 3 of those which are 0,0 1,1 and 2,2), and for each pair (a,a) it will repeat each 15 based on the theorem.

→ Reply
»
20 minutes ago, # |
← 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.

→ Reply