hmehta's blog

By hmehta, history, 5 years ago, In English

Hey All!

Topcoder SRM 779 is scheduled to start at 11:00 UTC -5, Feb 21, 2020. Registration is now open in the Web Arena or Applet and will close 5 minutes before the match begins.

Thanks to misof and lazy_fox (CF:mridul1809) for writing the problems and coordinating the round.

This is the sixth SRM of Stage 2 of TCO20 Algorithm Tournament and TCO20 Regional Events Qualification

Stage 2 TCO20 Points Leaderboard | Topcoder Java Applet | Upcoming SRMs and MMs

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
  • +3
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem Writing page seems to be not working.

»
5 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I am still not able to subscribe to your newsletter.

https://codeforces.net/blog/entry/73920#comment-580920

»
5 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Why you do this TC ?

(I'd swap atcoder with CF though)

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

I saw that the statement to problem ArraySorting was updated, but i refreshed my page (2 times) and dont see nothing, so i just submitted the problem considering that the values range from 1...1000, and just now (in the end) realized that the values ranges from 1...2000, thats when i closed and reopened the problem right in the end of the contest :(

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it -36 Vote: I do not like it

    I was wrong before. The size of dp table is dependant on the range of values.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      One my friend though that original numbers are in range $$$[1, 2000]$$$ but we can only change to $$$[1, 1000]$$$. This matters cause this gives incorrect answer for $$$[2000, 2000, 1000]$$$, for example.

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

      It does. In the old statement if the values are 1-1000 then you can make tests like 1997 2000 1999. You can use 1 step in the new version but not in the old version.

      I made this mistake too and solved on the old statement :) didn't notice the announcement

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Completely unrelated to this SRM, but I noticed that the (Java) arena doesn't update everything when it's sufficiently out of focus — when I'm on desktop 2 and the arena is on desktop 1, then:

  • when systests in practice finish, it shows the last state I saw before they finished
  • when a new phase starts, the timer updates, but the name of the phase (e.g. CODING) doesn't

I'm sure there are other cases. I can understand why it's done this way (to save bandwidth when I'm not using the arena), but it's objectively inferior to the purely client-side approach with server-side validation.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve SubstringQueries?

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Will there be any recalculation of the scores? I see some people had to resubmit and some even didn't and their problems fell because of that (for example I managed to challenge dreamoon's solution which looked at up to 1000). Although I did rather well, I don't think that's fair.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    But there was an announcement in Applet (not sure about web arena though).

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

      Sure, but what if you submitted before the announcement?

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

For OneGCD problem how is answer phi(y[i])

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

    Read D's soln. Same problems. https://codeforces.net/blog/entry/73467

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Main observation is that, given some positive integer $$$m$$$, any interval of $$$m-1$$$ consecutive integers has same number of numbers coprime to $$$m$$$. So, you can just count the number of numbers coprime to $$$m$$$ that are in $$$[0,m-1]$$$, which is exactly $$$phi(m)$$$.