awoo's blog

Educational Codeforces Round 170 Editorial
By awoo, history, 116 minutes ago, translation, In English

2025A - Two Screens

Idea: BledDest

Tutorial
Solution (BledDest)

2025B - Binomial Coefficients, Kind Of

Idea: adedalic

Tutorial
Solution (adedalic)

2025C - New Game

Idea: fcspartakm

Tutorial
Solution (awoo)

2025D - Attribute Checks

Idea: adedalic

Tutorial
Solution (adedalic)

2025E - Card Game

Idea: BledDest

Tutorial
Solution (Neon)

2025F - Choose Your Queries

Idea: BledDest

Tutorial
Solution (BledDest)

2025G - Variable Damage

Idea: BledDest

Tutorial
Solution (awoo)
  • Vote: I like it
  • +14
  • Vote: I do not like it

»
114 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally

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

Hii everyone can anyone help me D problem?

https://mirror.codeforces.com/contest/2025/my

this was my solution

i would keep count of zeros till i

then our s could range from 0 to zeros

so my state is dp[s] which will have max check passed, so my time complexity was 5000*2*10^6

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

    https://mirror.codeforces.com/contest/2025/submission/286105592

    here i have reduced most of the redudant operations still i get tle

    what i am thinking is to have a vector which stores starting and ending point of zeros if more than 1 then i would just increment my of zeros to difference between start and end their by saving some more time am i going in the right direction?

    i would be using a unordered map to store my records.

    → Reply
»
84 minutes ago, # |
  Vote: I like it +1 Vote: I do not like it

For those, who interested in combinatorial way for problem E, using something similar to Catalan numbers: I wrote a post about it

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

Does Problem D fall under some Dp pattern saw this pattern of pushAndClear in many submissions it didn't click to me at all.

→ Reply
»
61 minute(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

isn't the code in problem A's solution $$$ O(n^2) $$$ due to string slicing?

→ Reply
»
56 minutes ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

in problem D the lazy sum thing is not so obvious for me I used vector of vector and binary search how to apply the lazy sum with my solution ?

link : https://mirror.codeforces.com/contest/2025/submission/286105111

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

for Problem c , can anyone tell why this solution is giving wrong answer on test 4 (i used binarysearch to solve this): https://mirror.codeforces.com/contest/2025/submission/285946605 thanks in advance !!

→ Reply
»
50 minutes ago, # |
  Vote: I like it +1 Vote: I do not like it

Note about Problem A ( or any other problem concerning strings ) if you use Python and fast IO like: input = sys.stdin.readline then make sure to strip the string from whitespace and newlines.

this code was tested in Windows fine:

import sys

# defined functions for fast input
input = sys.stdin.readline
readListInts = lambda type_="int", sep=" ": list(
    map(eval(type_), input().strip().split(sep))
)

# defined functions for fast output
output = lambda x: sys.stdout.write(str(x) + "\n")
outputString = lambda x: sys.stdout.write(x + "\n")

def main():
    for _ in range(int(input())):
        s = input()
        t = input()

        lcp = 0
        n = len(s)
        m = len(t)
        for i in range(1, min(n, m) + 1):
            if s[:i] == t[:i]:
                lcp = i
        output(n + m - max(lcp, 1) + 1)

if __name__ == "__main__":
    main()

However, the judges are based on POSIX systems and newlines are treated differently between the two systems. So I needed to make this small adjustment: 

 s = input().strip()
 t = input().strip()

A small detail that may cost you a submission.

I guess for veteran competitive programmers this is trivial but it cost me some time and a wrong submission on an easy problem.

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

Problem B Binomial Coefficients Kind of Video Editorial Link: https://youtu.be/y_b2Khyk28w?si=Ku5V5m1jtT8EtA1e

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

    Honestly, instead of doing this video... up solve next time.

    Or may be just downvote this comment and rant over it.

    Not that anyone asked, but felt like sharing constructive feedback.

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

_i want to know,would anyone please tell me why rating going back;

→ Reply
»
5 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

my solution to D is a little different and it does not require bs or lazysum.

let $$$dp[i]$$$ denotes the $$$max \ score$$$ we can get if we are at index $$$j$$$ and have total $$$i$$$ intelligence points
if $$$A[i] == 0$$$ we will update dp values as follows.
let $$$cnt1[x] \ and \ cnt2[x]$$$ stores no. of checks with values x of intelligence and strength respectively.

if we choose to increase intelligence points then we are sure that we will pass all the intelligence checks having value $$$<=$$$ to our current intelligence values and because all the checks with value $$$<$$$ $$$current intelligence$$$ are already covered we will need to calculate how many values = current intelligence are there on the right on the right of index i and this value is stored in cnt1[current intelligence].

$$$dp[i] \ = \ max(dp[i] \ + \ cnt2[s - i], \ dp[i - 1] \ + \ cnt1[i])$$$
here $$$i$$$ is $$$current_intelligence$$$ and s is $$$current total score = intelligence + strength$$$

here is the 285916766 to explain better (ignore the code above solve function).

feel free to ask me if you have any queries. Thanks!

→ Reply