hmehta's blog

Topcoder SRM 773
By hmehta, history, 5 years ago, In English

Hey All!

Topcoder SRM 773 is scheduled to start at 12:00 UTC -5, Dec 21, 2019. Registration is now open in the Web Arena or Applet and will close 5 minutes before the match begins.

Thanks to misof for writing the problems and coordinating the round.

This is the last SRM of Stage 1 of TCO20 Algorithm Tournament.

Stage 1 TCO20 Points Leaderboard | Topcoder Java Applet | Next SRM 774 — Jan 11, 12:00 UTC-5

Some Important Links
Match Results (To access match results, rating changes, challenges, failure test cases)
Problem Archive (Top access previous problems with their categories and success rates)
Problem Writing (To access everything related to problem writing at Topcoder)
Algorithm Rankings (To access Algorithm Rankings)
Editorials (To access recent Editorials)

Good luck to everyone!

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

Comments Comments (12)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Reminder: 2 hours to start! Good luck and enjoy the last SRM of 2019!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Haven't been able to get past the "Completing login... One moment please..." screen in the web arena for the last fifteen minutes.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problems, but 900 wasn't hard enough for the last spot. My solution is to replace all tests by the maximal one, compute LCM and try adding divisors of the LCM that increase GCD(sum, LCM) until LCM divides the sum. Simple and effective.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

    Funnily enough, adding divisors of LCM(1..22) greedily in descending order till the total sum is LCM(1..22) also works.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So the task gets more interesting if you can't add elements with value less than $$$23$$$

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nope, you can find the answer with simple greedy even if you will forbid adding numbers that are at most $$$22$$$. You can look at my submission.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      At least it wouldn't let me make an unhackable solution trivially.

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -20 Vote: I do not like it

Div1 500 was the unlucky problem publishment for misof. The very similar problem has appeared on AtCoder Japanese Student Championship Qual Problem D — Classified. Just this time sheyasutaka was few months earlier.

However, in Div1 500, it was not specified to "minimize" the number of airlines. If "minimize", the thinking step will be much trivial and I can come up with solution in few seconds. But this time, since it was not specified, it took about 4 minutes to come up with it. So I emphasize that it's somewhat different.

→ Reply
»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

It's $$$\lceil{log_2(N)}\rceil$$$ the minimum number of airlines required for the Div1 500 problem ? If it's true how to prove that is a lower bound ?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    If $$$2^k < n$$$, then you can find two vertices which are always in one part. So there is no edge between them.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hahaha, wtf is that 500pt. It should be like B on some educational round. I've seen this like million times, it's so super standard trick.

→ Reply