majk's blog

By majk, 3 months 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.

Read more »

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

By majk, history, 3 months 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

Read more »

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

By majk, 3 months 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. MakeRussiaGreatAgain
  3. Um_nik
  4. ecnerwala
  5. Radewoosh

UPD7: Some more information about problem G

Read more »

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

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

Read more »

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

By majk, 6 months 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. CongLingDanPaiShang3k5
  4. Errichto
  5. 300iq

Read more »

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

By majk, 6 months 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

Read more »

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

By majk, 7 months 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

Read more »

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

By majk, history, 12 months ago, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

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

By majk, 12 months 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

Read more »

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