undefined | Better HN

0 pointsgfd4y ago0 comments

You can find the rating distribution filtered for >5 contests here: https://codeforces.com/blog/entry/71260

I am rated at 2100+ so I do agree that 1300 rating is low. But at the same time it solved https://codeforces.com/contest/1553/problem/D which is rated at 1500 which was actually non-trivial for me already. I had one wrong submit before getting that problem correct and I do estimate that 50% of the regular competitors (and probably the vast majority of the programmers commenting in this thread right now) should not be able to solve it within 2hrs.

0 comments

rfoo4y ago

1553D is a quite confusing case though.

On the AlphaCode Attention Visualization website [1], the Accepted code shown for 1553D is a O(n^2) Python one, which is supposed to be TLE. It correctly implements a two-pointer solution, but failed to "realize" that list.pop(0) is O(n) in Python. I'm not sure how it passed.

[1] https://alphacode.deepmind.com/#layer=30,problem=34,heads=11...

Jensson4y ago

Likely the python runtime has a strange string implementation for cases like this, just like javascript strings.

Veedrac4y ago

It does not. Really the strings just never get long enough that O(n²) would be catastrophic; the maximum possible length is 2e5.

1 more reply

johndough4y ago

The proposed O(N²) solution contains many unnecessary operations, e.g. the creation of list c or reversal of the input strings. Maybe it has been copied from a related problem? You can easily solve the task with half as many lines in O(N).

    for _ in range(int(input())):
        a = list(input())
        b = list(input())
        while a and b:
            if a[-1] == b[-1]:
                a.pop()
                b.pop()
            else:
                a.pop()
                if a: a.pop()
        print("NO" if b else "YES")

pedrosorio4y ago

> But at the same time it solved https://codeforces.com/problemset/problem/1553/D

To be fair, it generated a set of (10) possible solutions, and at least one of them solved the problem.

the-smug-one4y ago

I'm trying to solve this for fun, but I'm stuck! I've got a recursive definition that solves the problem by building a result string. I think it's a dynamic programming problem, but right now I can't see the shared sub-problems so :). Some real sour cherries being experienced from not getting this one!

thorwwaskeas4y ago

  from collections import defaultdict
  def backspace(s1,s2):
      h = defaultdict(lambda:0)
      for x in s1:
          h[x] = h[x] + 1
      for x in s2:
        h[x] = h[x] - 1
      j = 0
      maxj = len(s2) - 1
      for x in s1:
        if x != s2[j]:
            h[x] -= 1
        elif j < maxj:
                j += 1
        else:
            break
    return j == maxj and all(y >= 0 for y in h.values())

  def random_backspace(s1):
    res = []
    for x in s1:
        if randint(0,1) == 0:
            res.append(x)
    return "".join(res)

  def backspaceTest(s1):
    return all(backspace(s1,random_backspace(s1)) for _ in  range(100))

j / k navigate · click thread line to collapse