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

Автор Achilles221B, история, 4 года назад, По-английски

Today when my brother was trying to solve 1355B - Young Explorers with Python3. He got wrong answer on Test 10.

81011086

81011086 May/23/2020 13:44UTC+2 ThetaSigma B — Young Explorers Python 3 Wrong answer on test 10

When he told me about his solution, I thought about it for a bit and I couldn't come up with anything. So I just tried submitting it with PyPy3 and weirdly enough it got accepted.

81011123

81011123 May/23/2020 13:45UTC+2 ThetaSigma B — Young Explorers PyPy 3 Accepted

For anyone curious, here's the code:


from sys import stdin def inp(): return stdin.readline().strip() t = int(inp()) for _ in range(t): n = int(inp()) e = [int(x) for x in inp().split()] e.sort() x = list(set(e)) big = max(e) results = {} for i in e: if results.get(i,0): results[i] += 1 else: results[i] = 1 groups = 0 counter = 1 for i, j in results.items(): groups += j//i if i != big: results[x[counter]] += j%i counter += 1 print(groups)

Does anyone have any idea about what's happening here?

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

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

When he told me about his solution, I thought about it for a bit and I couldn't come up with anything.

Erm you just submit it on not even a minute later.

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

    Yeah, you are right. But If you looked at his previous submissions. You would find a slightly different solution with wrong answer on test 3. He told me about it when he made that submission. but since it isn't relevant I didn't mention it.

»
4 года назад, # |
Rev. 6   Проголосовать: нравится +13 Проголосовать: не нравится

Iteration respecting insertion order was only added in CPython 3.6 (CPython is the default implementation of Python) and standardized in Python 3.7. Maybe Codeforces' PyPy does not yet support Python 3.7. If you are depending on result.items() returning is in the same order they appeared in e (that is, in sorted order), this might explain your issue. Try using OrderedDict instead?

Technically, mutating a dict while iterating over it is undefined behavior in Python 2 and Python 3 (in practice, mutating values only is probably fine, so I guess this is not your issue). From PEP 3106:

As in Python 2.x, mutating a dict while iterating over it using an iterator has an undefined effect and will in most cases raise a RuntimeError exception. (This is similar to the guarantees made by the Java Collections Framework.)