Блог пользователя Dart-Xeyter

Открытая олимпиада школьников по программированию (с разбором A, C, D, E, F, G, I).
Автор Dart-Xeyter, история, 3 года назад, По-русски

Кажется, подобного поста ещё не было, поэтому... Здесь вы можете обсуждать всё об Открытке 2021-2022 :)

Также, вы можете прочитать мои решения некоторых задач (возможно, их число — разобранных — будет постепенно увеличиваться).

Условия задач. Таблица результатов.

Наконец-то добавленный официальный разбор.

Решение А.
Решение С (красивое).
Решение С (напрашивающееся).
Решение D.
Решение Е.
Решение F.
Решение G.
Решение I.

Полный текст и комментарии »

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

tourist-а забрали в армию! [HELP]
Автор Dart-Xeyter, история, 4 года назад, По-русски

Недавно я наткнулся на фотографию, шокировавшую меня. С первого взгляда на ней не изображено ничего примечательного: обычный солдат, стоящий по стойке смирно. Есть только один нюанс: военный на фотографии, это Геннадий tourist Короткевич.

Сказать, что я удивился — значит ничего не сказать. Оказалось, что не смотря на значительные заслуги Геннадия в области спортивного программирования, его всё равно забрали в армию республики Беларусь.

Считаю, что в случае войны tourist будет гораздо полезнее в качестве стратега, нежели обычного солдата, поэтому призываю всех распространить данную информацию, и помочь Геннадию Короткевичу избежать воинской повинности!

#СпасёмГеннадия

Полный текст и комментарии »

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

Some easy but useful optimization in Python.
Автор Dart-Xeyter, история, 4 года назад, По-английски

I have a few friends who write rounds in Python, and I noticed that they don't use some very simple optimizations, and the program ends up getting TL. Meanwhile, if you use these constructions, in half or more cases TL is removed.

I will show everything using the example code of my friend I_am_Drew from a 1413B - Новая техника. This code received TL (worked longer than $$$1$$$ second).

for __ in range(int(input())):
    n, m = list(map(int, input().split()))
    kek = []
    for i in range(n):
        el = list(map(int, input().split()))
        el.append(0)
        kek.append(el)
    stolb = list(map(int, input().split()))
    ind = 0
    for i in range(m):
        if kek[0][i] in stolb:
            ind = i
            break
 
    for i in range(n):
        kek[i][m] = stolb.index(kek[i][ind])
 
    for j in range(m-1):
        stolb = list(map(int, input().split()))
 
    kek.sort(key=lambda x: x[m])
    for elem in kek:
        elem.pop()
        print(*elem)

First, as you know, data input and output takes quite a long time. Fortunately, this can be fixed using the sys module. I usually write this way because it's the quickest fix, but of course it's not exactly code-style :)

from sys import stdin, stdout
input, print = stdin.readline, stdout.write

The stdin.readline function reads a string like input, but faster. Also, if necessary, there is, for example, the stdin.read function, which reads all input as a string (then you need to put ^D after it is completed), and others, but I usually do not use them. The output is more complicated, the stdout.write function accepts only strings, and does not output a line feed or other separator after it. Therefore, you have to write as in the example below, it is also not very long to fix it, the main thing is not to forget :) After the conversions, you get this code. (Note that the input code has not changed at all, but the output at the end is quite a lot).

from sys import stdin, stdout
input, print = stdin.readline, stdout.write
for __ in range(int(input())):
    n, m = list(map(int, input().split()))
    kek = []
    for i in range(n):
        el = list(map(int, input().split()))
        el.append(0)
        kek.append(el)
    stolb = list(map(int, input().split()))
    ind = 0
    for i in range(m):
        if kek[0][i] in stolb:
            ind = i
            break

    for i in range(n):
        kek[i][m] = stolb.index(kek[i][ind])

    for j in range(m - 1):
        stolb = list(map(int, input().split()))

    kek.sort(key=lambda x: x[m])
    for elem in kek:
        elem.pop()
        # print(' '.join(map(str, elem)))
        for q in elem:
            print(str(q)+' ')
        print('\n')

It is also known that global variables work longer than local ones, so if you put all the code (of course, without other functions) in, for example, main, it will also work faster. The final version of the code looks like this:

from sys import stdin, stdout
input, print = stdin.readline, stdout.write


def main():
    for __ in range(int(input())):
        n, m = list(map(int, input().split()))
        kek = [list(map(int, input().split()))+[0] for _ in range(n)]
        stolb = list(map(int, input().split()))
        ind = 0
        for i in range(m):
            if kek[0][i] in stolb:
                ind = i
                break

        for i in range(n):
            kek[i][m] = stolb.index(kek[i][ind])

        for j in range(m - 1):
            stolb = list(map(int, input().split()))

        kek.sort(key=lambda x: x[m])
        for elem in kek:
            print(' '.join(map(str, elem[:-1])))
            print('\n')


main()

Note that there were very few changes, but the program accelerated at least $$$2$$$ times and now gets OK, working in $$$545$$$ milliseconds. Of course, you can come up with a lot of optimizations, but these are the main ones, and they work on most tasks and are easy to write. You should understand that, of course, this is not a panacea, and if, for example, in the task input or output $$$1$$$ number, optimization of fast input-output becomes useless. However, it comes in handy in many tasks.

Also, keep in mind that although PyPy3 is usually much faster than Python3 (for example, in this task it is $$$1.5$$$ times faster), there are situations when Python3 is faster, and I know problems where Python3 solutions get OK, but Pypy3 didn't. This does not mean that every TL needs to be forwarded to Python3, collecting a fine, just keep this in mind. In my experience, Python3 is often faster in problems on string, but of course it's different every time.

I hope this blog will help you use Python even more successfully :)

Полный текст и комментарии »

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

Multiple contributions CF
Автор Dart-Xeyter, история, 4 года назад, По-английски

P.S. You may have already seen this text, I accidentally published it in the Russian part of Codeforces :)

Hello, Codeforces! I immediately want to apologize for my English, I use a translator and the result may be very stupid :)

So, we all know that Codeforces has a contribution system, if you write something useful (or good memes :), your contribution increases, and you can have more influence on the life of Codeforces (as far as I know, if your contribution is large enough, your vote counts for 2, or even 3).

But sometimes there are situations when a post is made by many people, but only one person can publish it, and because of this, the entire contribution goes to him.

An excellent example is the Education Rounds. As you know, all these rounds are made by the same team of people: awoo, Neon, BledDest, Roms, adedalic and of course vovuh :) But the announcements of rounds are always published by pikmike, and in the end we get that awoo has a contribution of +182, and Neon — 0.

I know that there is a "co-authors" button, and the people you listed there can edit your post and so on, but they still don't get the contributions from this post.

I suggest adding to the "co-authors" button the function of adding a contribution for these people too, or, for example, adding a separate line for listing people who also add a contribution for this post.

Of course, I understand that some people may write something bad and add people like MikeMirzayanov as co-authors, so it might be worth making this button available, starting with candidates like for editing tags for problems, etc.

Another solution to the problem that T1mofey778 suggested to me is that when you are listed as a co-author, you will receive a notification and you would agreе or not, then people like tourist can receive a lot of spam, but you can set a limit, as in messages, people with what minimum rating can try to indicate you as a co-author.

In any case, you should think about this problem and, of course, if I made a mistake somewhere, correct me in the comments :)

Полный текст и комментарии »

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

Решение задачи С с МОШа (Московская олимпиада школьников по информатике).
Автор Dart-Xeyter, история, 5 лет назад, По-русски

Сразу скажу, это единственная задача, которая не вошла в https://codeforces.me/blog/entry/74106, основанный на МОШе, и не зря, ведь в ней нужно ифать кучу случаев, и у меня, например, было 98 баллов :)

Условие
Решение
Код на Python
Код на C++

Полный текст и комментарии »

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

Решение за O(n) задачи В из прошлого раунда.
Автор Dart-Xeyter, история, 5 лет назад, По-русски

Не знаю, в чём проблема, я сразу написал так.

n = int(input())
a = list(map(int, input().split()))
s, d = {}, {}
for q in range(n):
    s[a[q]] = q
    d[a[q]] = d.get(a[q], 0)+1
q2, ans = 0, n-1
for q1 in d:
    while d[q1] > 1:
        d[a[q2]] -= 1
        q2 += 1
f = set()
for q in range(n):
    ans = min(ans, q2-q)
    if a[q] in f:
        break
    f.add(a[q])
    q2 = max(q2, s[a[q]]+1, q+1)
print(ans)

Полный текст и комментарии »

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