Блог пользователя laxmi_kanth

Автор laxmi_kanth, история, 22 месяца назад, По-английски

My solution of code forces round div 3 for C (train queries) was hacked and I didn't find the case where I would fail.Please help me find that case. I really appreciate any help you can provide.

Here is my code ```

def solve(): d = defaultdict(list)

# n = int(input())
# s=input()
e=input()
n,m=list(map(int,input().split()))
#
lis = list(map(int, input().split()))
# lis1=input().split()
# lis2 = list(map(int, input().split()))
# lis3 = list(map(int, input().split()))
# n,r,b=list(map(int,input().split()))
# order=list(map(int,input().split()))
# r2,c2=list(map(int,input().split()))
# ans=[[-1 for _ in range(m)] for _ in rnage(n)]
for i,ele in enumerate(lis):
    d[ele].append(i)
for _ in range(m):
    u,v=list(map(int,input().split()))
    if(u not in d or v not in d):
        print("NO")
        continue
    if(d[u][0]<d[v][-1]):
        print("YES")
    else:
        print("NO")

```

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Read the hack message: TLE (time limit exception.) Most python/pypy3 solutions suffered the same fate due to slow hashing and input. The time limit should be raised for problem C for python definitely (O(N) solution fails whereas other languages pass and have same logic/time complexity).

Another problem with similar results (most python solutions hacked) https://codeforces.com/contest/1692/problem/H .

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The hack abuses the python hash function see https://codeforces.com/blog/entry/101817 it makes the construction of the hash table being O(n^2) and hence the TLE