laxmi_kanth's blog

By laxmi_kanth, history, 4 years ago, In English

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")

```

  • Vote: I like it
  • -4
  • Vote: I do not like it

| Write comment?
»
4 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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.me/contest/1692/problem/H .

»
4 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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