majk's blog

By majk, 4 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +153
  • Vote: I do not like it

By majk, 5 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Full text and comments »

  • Vote: I like it
  • +159
  • Vote: I do not like it

By majk, 5 years ago, In English

Hi!

Are you tired after a weekend of three (3) contests? Or are you ready for another one? On Dec/17/2019 18:05 (Moscow time) we will host Codeforces Global Round 6!

It is the sixth round of a new series of Codeforces Global Rounds supported by XTX Markets. The rounds are open for everybody, the rating will be updated for everybody.

You will be given 8 problems and 150 minutes to solve them. The scoring distribution will be 500-750-1250-1750-2000-2500-3500-4000.

The prizes for this round:

  • 30 best participants get a t-shirt.
  • 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2019 (current results):

  • In each round top-100 participants get points according to the table.
  • The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
  • The best 20 participants over the whole series get sweatshirts and place certificates.

The problems of this round were developed by me. I will be available on Discord to discuss the problems after the contest.

I would like to thank:

UPDATE: The round is over! I hope you enjoyed it despite the second half being more difficult than anticipated. The system test will begin shortly.

UPDATE 2: Editorial

UPDATE 3: Congratulations to winners:

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

UPDATE 4: Global Rounds 2019 final results

Full text and comments »

  • Vote: I like it
  • +323
  • Vote: I do not like it

By majk, 5 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +87
  • Vote: I do not like it

By majk, 5 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Full text and comments »

  • Vote: I like it
  • +30
  • Vote: I do not like it

By majk, history, 5 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Full text and comments »

  • Vote: I like it
  • +64
  • Vote: I do not like it

By majk, 5 years ago, In English

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.me/spectator/ranklist/e354b9b95c3626a3cfdfdb9eb37a7a6f)

Editorials: day1 day2

Full text and comments »

  • Vote: I like it
  • +313
  • Vote: I do not like it

By majk, history, 5 years ago, In English
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

Full text and comments »

  • Vote: I like it
  • +151
  • Vote: I do not like it

By majk, 5 years ago, In English

Hi!

On Jul/20/2019 18:35 (Moscow time) we will host Codeforces Global Round 4.

It is the fourth round of a new series of Codeforces Global Rounds supported by XTX Markets. The rounds are open for everybody, the rating will be updated for everybody.

You will be given 8 problems and 150 minutes to solve them. The scoring distribution will be 500-750-1250-1750-2000-(1500+1500)+3250+4000.

The prizes for this round:

  • 30 best participants get a t-shirt.
  • 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2019:

  • In each round top-100 participants get points according to the table.
  • The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
  • The best 20 participants over the whole series get sweatshirts and place certificates.

The problems of this round were developed by me. I will be available on Discord to discuss the problems after the contest.

I would like to thank:

UPD: The round is finished. I hope you enjoyed the problems! I am very sorry about the issue on E.

UPD2: Editorial

UPD3: Congratulations to:

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

UPD4: The results after four rounds.

Full text and comments »

Announcement of Codeforces Global Round 4
  • Vote: I like it
  • +875
  • Vote: I do not like it

By majk, 6 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +336
  • Vote: I do not like it

By majk, history, 6 years ago, In English
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

Full text and comments »

  • Vote: I like it
  • +154
  • Vote: I do not like it

By majk, 6 years ago, In English

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

Full text and comments »

Announcement of Good Bye 2018
  • Vote: I like it
  • +1032
  • Vote: I do not like it

By majk, 6 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Full text and comments »

  • Vote: I like it
  • +178
  • Vote: I do not like it

By majk, 6 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +352
  • Vote: I do not like it

By majk, 6 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +47
  • Vote: I do not like it

By majk, 6 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +117
  • Vote: I do not like it

By majk, history, 7 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Full text and comments »

Tutorial of VK Cup 2018 - Round 1
  • Vote: I like it
  • +164
  • Vote: I do not like it

By majk, 7 years ago, In English

The round 1 of VK Cup 2018 will take place on March 10 at 18:35 MSK (check your timezone). The contest "VK Cup 2018 — Round 1" is for teams qualified from two Qualification Rounds. The top 400 teams will advance to the Round 2, along with teams that qualify in the Wild Card Round 1 a week later. As usual, there will be two parallel rounds for those ineligible to participate in VK Cup, one for each division.

I'd like to thank KAN for steering my crazy ideas into a coherent unit, the coordination and also for suggesting one of the problems, AlexFetisov, qwerty787788, winger, Errichto, Tommyr7 and misof for testing the problems, MikeMirzayanov for building Codeforces and Polygon and VK for organising the contest.

All three rounds last 2 hours, and all are rated. The VK Cup and Div. 1 will have six identical problems while the Div. 2 contest will consist of five problems. The scoring distribution will be announced before the contest.

The main heroes of this round will be Alice and Bob. Beware that Eve might attempt to foil their plans.

This is my first round on Codeforces and hopefully not the last. Wish you many submissions, high hacks and successful rating.

UPDATE: The scoring in Div.1 and VK Cup round 1 is 500-1000-1500-1750-2250-3000. For Div.2, it is 500-1000-1500-2000-2250.

UPDATE2: The round is finished. I hope you enjoyed it. Tune in a bit later for editorial.

UPDATE3: Congratulations to winners!

Div.1

Div.2

VK Cup

UPDATE4: Editorial

Full text and comments »

Announcement of VK Cup 2018 - Round 1
  • Vote: I like it
  • +251
  • Vote: I do not like it