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

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

To all problemsetters!

The first ever European Girls' Olympiad in Informatics will take place in Zurich in June 2021. We are looking for interesting problems for the contest! The authors of selected proposals will be invited to the onsite event.

You can find more information about the contest and the call for tasks on the EGOI website.

The submission deadline is 31.10.2020.

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

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

Автор majk, 4 года назад, По-английски
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

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

Разбор задач Codeforces Global Round 6
  • Проголосовать: нравится
  • +159
  • Проголосовать: не нравится

Автор majk, 4 года назад, перевод, По-русски

Всем привет!

Скоро состоится Codeforces Global Round 6, время начала: 17.12.2019 18:05 (Московское время).

Это шестой раунд из серии Codeforces Global Rounds, которая проводится при поддержке XTX Markets. В раундах могут участвовать все, рейтинг тоже будет пересчитан для всех.

Соревнование продлится 2 часа 30 минут, вас ожидает 8 задач, при этом одна из задач будет представлена в двух версиях. Разбалловка 500-750-1250-1750-2000-2500-3500-4000.

Призы в этом раунде:

  • 30 лучших участников получат футболки.
  • 20 футболок будут разыграны случайным образом среди участников с 31-го по 500-е место.

Призы в серии из 6 раундов в 2019 году (текущие результаты):

  • За каждый раунд лучшим 100 участникам начисляются баллы согласно таблице.
  • Итоговый результат участника равны сумме баллов для четырех лучших выступлений этого участника.
  • Лучшие 20 участников по итоговым результатам получают толстовки и сертификаты с указанием места.

Задачи этого раунда придуманы и подготовлены мной. После раунда я буду доступен в Discord для обсуждения задач.

Я благодарю следующим людям:

Присоединяйтесь!

UPDATE: Раунд окончен! Надеюсь, что он вам понравился, несмотря на то, что последние задачи оказались сложнее, чем мы думали. Системное тестирование скоро начнется.

UPDATE 2: Разбор

UPDATE 3: Поздравляем победителей:

  1. webmaster
  2. sunset
  3. tourist
  4. whzzt
  5. hos.lyric
  6. eatmore

UPDATE 4: Финальные результаты всех Глобалов в 2019 году

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

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

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

This is the editorial for the ETH selection contest, which took place on Saturday 19th October. The problems are in a mashup contest where only the participants have access. To see the problems, first join the group.

UPD: Apparently, you cannot display tutorial for non-public contest. You can download PDF with tutorial. Author's codes are below.

A
B
C
D
E
F
G
H
I
J
K
L

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

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

Автор majk, 5 лет назад, По-английски
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

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

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

Автор majk, история, 5 лет назад, По-английски
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

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

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

Автор majk, 5 лет назад, По-английски

The 26th Central European Olympiad in Informatics will take place in Bratislava, Slovakia, during July 23rd-29th 2019. The most gifted high school students from 13 countries will have the opportunity to prove their knowledge and skills in informatics.

Codeforces will organise the online mirror for this year's competition. The online mirrors will take place after the finish of each of the 2 competition days, having the same scoring format.

The online mirror schedules are the following:

Contest format

  • The contest will be unrated for all users.
  • You will have to solve 3 tasks in 5 hours.
  • There will be full feedback throughout the entire contest.
  • The scoreboard will be hidden until the end of the contest.
  • The tasks will have partial scoring. The maximum score for each problem will be 100 points.
  • Among multiple submissions only the one that achieves the maximum score is counted towards the final ranking.
  • The submission time does not matter for ranking.
  • There will be enough fun for all colours ranging from newbie to international grandmaster. Legendary grandmasters can spice it up by turning it into a drinking game (ask Radewoosh for details).

Link to onsite contest with official rules and scoreboard

UPDATE: Much nicer scoreboard than on the first day made by arsijo. Many thanks!

Congratulations to all onsite contestants who battled our unusually hard problemset for 10 hours. You can view the final standings.

Many thanks to KAN for running the mirror, MikeMirzayanov for both platforms, all of our authors, testers and the whole CEOI staff and sponsors!

Day 1 mirror:

  1. mnbvmar 300
  2. Benq 300
  3. gamegame 281
  4. ainta 271
  5. Tutis 254

Day 2 mirror:

  1. zx2003 230
  2. saba2000 230
  3. TLE 200
  4. cuizhuyefei 200
  5. panole 200
  6. dacin21 200

Results of both days combined: (https://codeforces.com/spectator/ranklist/e354b9b95c3626a3cfdfdb9eb37a7a6f)

Editorials: day1 day2

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

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

Автор majk, история, 5 лет назад, По-английски
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code

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

Разбор задач Codeforces Global Round 4
  • Проголосовать: нравится
  • +151
  • Проголосовать: не нравится

Автор majk, 5 лет назад, перевод, По-русски

Всем привет!

В 20.07.2019 18:35 (Московское время) состоится Codeforces Global Round 4.

Это четвертый раунд из серии Codeforces Global Rounds, которая проводится при поддержке XTX Markets. В раундах могут участвовать все, рейтинг тоже будет пересчитан для всех.

У вас будет 150 минут на решение 8 задач. Разбалловка 500-750-1250-1750-2000-(1500+1500)+3250+4000.

Призы в этом раунде:

  • 30 лучших участников получат футболки.
  • 20 футболок будут разыграны случайным образом среди участников с 31-го по 500-е место.

Призы в серии из 6 раундов в 2019 году:

  • За каждый раунд лучшим 100 участникам начисляются баллы согласно таблице.
  • Итоговый результат участника равны сумме баллов для четырех лучших выступлений этого участника.
  • Лучшие 20 участников по итоговым результатам получают толстовки и сертификаты с указанием места.

Задачи раунда разработаны мной.

Я хочу поблагодарить:

UPD: Раунд закончен. Надеюсь, что вам задачи понравились! Прошу прощения за проблему с задачей Е.

UPD2: Разбор

UPD3: Поздравляем:

  1. ainta
  2. Radewoosh
  3. tzuyu_chou
  4. LHiC
  5. Benq

UPD4: Результаты после четырех раундов.

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

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

Автор majk, 5 лет назад, По-английски

I realised I have too much contribution anyway, so I write this blog about G of today's contest.

This problem was plagued by technical issues from start to finish. When you read some of them, you will probably ask yourself how the hell did I get red in the first place.

Originally, the problem had n a product of just 2 primes. We then decided to raise it up to 10 primes. I was really confused that I had two types of runs — either they passed with runtime 30ms, or they got TLE or ILE. I added time measurement to the interactor itself, and found out that the 30ms solutions in fact took more than couple seconds to run. The same solutions reported run time of couple seconds in Gym contest that we used for testing. During post contest discussions with MikeMirzayanov I realised that I still don't understand how Polygon and Codeforces measure time for interactive problems.

I am not the fastest duck in the pond, so I investigated my Tonelli Shanks implementation for bugs, found and fixed a couple, but it was still too slow. Only at this point I actually calculated the number of operations needed to find a square root modulo a prime and facepalmed. I realised that only about 10 queries can fit into time limit in the worst case. 10 queries were too few to achieve reasonable success probability even for 2 prime factors.

Luckily, if the prime is of format 4k + 3, one can find the square root with just 1 modular exponentiation instead of 5 - 10 for Tonelli Shanks solving the general case. So the problem was changed to only support these primes, the TL and success probability was suddenly more than enough.

We made a way for the contestants to understand the implications of the runtime of the interactor, and were happy with the problem. Oh, how wrong we were! (Side note: After the contest, Mike suggested a better way of doing that, and I will change the problem for practice using this suggestion.)

Fast forward to contest — there is a crashing solution of Shik getting TLE on interactor. I don't see the interaction log in CF interface, so at first glance it seemed to me that he simply used too many queries and the time accumulated. Mike proved me wrong, as his logs showed that my interactor never returned answer to some of the queries.

I took the test case and the queries and modified the interactor so that it just uses stdin/stdout, and I can test and debug it manually outside of Polygon. For some strange reason the GCD was not returning the answer in a timely manner.

In the ensuing chaos we misjudged the situation and introduced the query limit of 100, but it only made matters worse.

I was looking at my GCD implementation like an idiot. More precisely, it is not my GCD implementation -- I am using someone else's library for big integers! I've made a few changes to it, but I considered it good, as it never failed me in a contest. Everything seemed fine except it wasn't. Then arsijo pointed out this loop:

do {
    b >>= b.count_trailing_zeros();            
    if (cmp_abs(a, b) > 0) a.words.swap(b.words);
    sub_unsigned_overwrite(b, a);
} while (b.size() > 0);

You don't need to know too much about my implementation to understand that this is roughly equivalent of:

do {
   if (a>b) swap(a,b);
   b -= a;
} while (b != 0);

You don't need to be a freaking red to understand that this is really stupid way of writing gcd.

I sighed, changed it to a = Num::mod(a, b) and ran it against Petr's and mine solution in Polygon. You don't need to be freaking red to understand that this is an incorrect fix. You need to have some Polygon experience to understand that this will use your CPU quota in Polygon and lock you out for 5 minutes, which is definitely something you appreciate when you have 10 potentially frustrated/angry contestants getting Denial of judgement.

I sighed again, changed it to b = Num::mod(b, a), committed the problem and asked arsijo to test it. He managed to lock himself out for some reason as well, and then the polygon returned HTTP 502 for some time. Magic MikeMirzayanov fixed it, saw that it runs correctly and pushed the change to Codeforces. It didn't change the verdicts in the slightest, but luckily it was just a case of a stale cache and it was fixed promptly.

We added a few minutes to the contest duration, but I understand that for some people the contest was already quite unfair or broken. I hope that during the post-contest investigation we found the least possible unfair solution. I would like to thank arsijo and MikeMirzayanov for the immense help with this difficult situation.

For anyone who managed to read this far: the downvote button is just below this sentence, and it looks like a triangle standing on one of its vertices.

Update: I realised I forgot to talk about one more important subject. Why the hell did we not find the issue with gcd during contest preparation? I think I know why. All of our solutions apparently did something along the lines of:

  • find random x in [1, N)
  • ask for square root of x * x

The crucial thing is that in expectation x is N / 2, hence x2 is N / 4. For these values, the subtraction gcd seems to run fast in expectation, and we never noticed the issue. When contestants did something else, suddenly things broke. For me, this is an important lesson about testing my problems.

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

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

Автор majk, история, 5 лет назад, По-английски
Tutorial is loading...
Code (by arsijo)
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code (by winger)
Tutorial is loading...
Code

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

Разбор задач Good Bye 2018
  • Проголосовать: нравится
  • +154
  • Проголосовать: не нравится

Автор majk, 5 лет назад, По-английски

The end of the December is fast approaching and it is time for the best last contest of the year! The Good Bye 2018 round will take place on Sunday, December 30, 2018 at 14:35 UTC.

As the people who already engaged in discussions about the ultimate problem suspect, I am the problem writer. As such, I'd like to thank to:

The round will last for 2:30 hours and you will be given 8 problems for both divisions. There will be an interactive problem.

You have the last opportunity to reach Your rating goals for 2018. Good luck!

UPD: The top 3 participants eligible for ICPC 2019/20 season can win a great prize.

UPD2: The scoring distribution is 500-1000-1750-2250-3000-3000-3750-4000.

UPD3: Round is finished. I hope you enjoyed the contest! I am really sorry for the duck-up in problem G. I'll share more details once the important things (systest, editorial ...) are taken care of. The systest might be slightly delayed because of that.

UPD4: Editorial

UPD5: We apologize for the issue with problem G. We are still investigating this issue. Verdicts “Idleness limit exceeded” may be changed to other. We will write a full report about it later.

UPD6: The results are final, rating will be recalculated shortly. Congratulations to the winners:

  1. tourist
  2. eatmore
  3. Um_nik
  4. ecnerwala
  5. Radewoosh

UPD7: Some more information about problem G

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

Анонс Good Bye 2018
  • Проголосовать: нравится
  • +1032
  • Проголосовать: не нравится

Автор majk, 5 лет назад, По-английски
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

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

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

Автор majk, 5 лет назад, По-английски

Hungry for yet another contest? On Sunday, October 7, 2018 at 17:05 UTC the Lyft Level 5 Challenge will start with the Round 1! This is a combined round having 7 problems and lasting 2 hours, and it will be rated.

The top 100 participants of this round will win a Lyft Level 5 Challenge t-shirt. The top 30 contestants located in the San Francisco Bay area will be invited to the Final Round.

In the Final Round the top three onsite contestants will fight for the cash prizes:

  • First place: $2000
  • Second place: $1000
  • Third place: $500

Interested in an internship or a job at Lyft?

Many thanks to:

I'll be on the community Discord server shortly after the contest to discuss the problems.

UPDATE 1: The scoring distribution will be 500-1000-1500-2250-2750-3250-4000.

UPDATE 2: The contest is over and there is an editorial.

UPDATE 3: Congratulations to the winners:

  1. tourist
  2. V--o_o--V
  3. DearMargaret
  4. Errichto
  5. 300iq

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

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

Автор majk, 6 лет назад, По-английски

Hello! On Saturday 15th September 16:00 UTC the contest HackerEarth HourStorm #3 will take place. It’s the third version of a short contest, that runs for 1 hour! The problem set consists of 3 traditional algorithmic tasks of various difficulties.

For traditional algorithmic tasks, you will receive points for every test case your solution passes — so you can get some points with partial solutions as well. Keeping the IOI tradition alive, the order of the difficulty of getting full points might be different from the order of difficulty of getting partial points, so make sure you read all the tasks. Check contest page for more details about in-contest schedule and rules.

I am the author of the tasks; but don't despair, they'll be (slightly) easier than my last CF round! Many thanks to jtnydv25 for testing and valuable feedback. As usual, there will be some prizes for the top three competitors:

  1. $75 Amazon gift card
  2. $50 Amazon gift card
  3. $25 Amazon gift card

In addition, top 5 on the scoreboard with rating less than 1600 will win HackerEarth t-shirts.

Good luck to everyone, and let's discuss the problems after the contest!

UPD: Contest finished. Winners:

  1. tourist
  2. Lewin
  3. Egor

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

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

Автор majk, 6 лет назад, По-английски

Topcoder SRM 736 is scheduled to start at 15:00 UTC, August 15, 2018. Note that as per the new Topcoder Open Algorithm rules (see associated discussion on CF) this round counts towards 2019 Topcoder Open Online Stage 1.

The tasks were prepared by me. I'd like to thank misof and paulinia for comments and testing.

You will be able to register for the SRM in the Arena or Applet 4 hours prior to the start of the match. Registration closes 5 minutes before the match begins, so make sure that you are all ready to go.

Refer to this guide to set up your environment for competing.

Good luck, have fun, positive rating!

UPD: Congratulation to the winners:

  1. rng_58
  2. ksun48
  3. tourist
  4. Um_nik
  5. xudyh

UPD2: Editorial

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

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

Автор majk, история, 6 лет назад, перевод, По-русски

Большое спасибо arsor за перевод разборов на русский язык!

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

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

Разбор задач VK Cup 2018 - Раунд 1
  • Проголосовать: нравится
  • +164
  • Проголосовать: не нравится

Автор majk, 6 лет назад, перевод, По-русски

Раунд 1 VK Cup 2018 пройдет 10-го марта в 18:35 MSK (время в вашем часовом поясе). Соревнование "VK Cup 2018 — Раунд 1" предназначено для команд, прошедших из двух Квалификационных раундов. Лучшие 400 команд пройдут в раунд 2, вместе с командами, отобранными в Уайлд-кард раунде 1 неделей позже. Как обычно, параллельно пройдут два обычных раунда, по одному для каждого дивизиона, для тех, кто не может принять участие в VK Cup.

Я хотел бы поблагодарить KAN за приведение моих безумных идей к виду законченного набора задач, координацию и идею одной задачи, AlexFetisov, qwerty787788, winger, Errichto, Tommyr7 и misof за тестирование, MikeMirzayanov за платформы Codeforces и Polygon, а также VK за проведение соревнований. Также спасибо arsor за помощь с условиями на русском языке.

Все три раунда будут идти 2 часа, и все являются рейтинговыми. Раунды VK Cup и первого дивизиона будут иметь шесть задач, одинаковые в обоих раундах. Раунд второго дивизиона будет содержать пять задач. Стоимости задач будут объявлены перед раундом.

Главными героями раунда будут Алиса и Боб. Конечно, Ева попытается разрушить их планы.

Это мой первый раунд на Codeforces и, надеюсь, не последний. Желаю вам много посылок, крутых хаков и положительного изменения рейтинга.

Поздравляем победитетей!

VK Cup

Div.1

Div.2

Разбор тут.

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

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