hmehta's blog

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

Hey All!

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

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

This is the first 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
  • +43
  • Vote: I do not like it

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

Happy new year! The first SRM in 2020 :)
It's nice to see Lewin / lg5293 as writer of SRM! Last time was about 2 years ago, but it's still one of my favorite.

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

Gentle Reminder: The match begins in 1hr 30mins

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

How to solve land splitter?:(

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

    The cost is (sum of squares of starting sizes — sum of squares of goal sizes) / 2. You just need to find the maximum of $$$\sum x_i^2$$$ for any $$$A \le x_i \le B$$$, $$$\sum x_i = N$$$.

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

      Oh, right. Thank you.

      So, how to solve landsplitter? :-)

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

        You've got a hint, you could try finishing it yourself.

        Next hint: you never want two $$$x_i$$$ in the interval $$$(A, B)$$$ because moving them away from each other improves the sum of squares. Now there are several $$$O(N)$$$ solutions.

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

          Is there a book or set of tutorials to help you prepare for such problems or is this supposed to be basic stuff?

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

            Subtract x from one element, add x to another, see how the optimised function changes is supposed to be basic stuff. It works for a lot of problems.

            For continuous variables and arbitrary conditions, there's something called Lagrange multipliers that gives you a set of equations that any extremum point (that isn't on the border of the allowed region) must satisfy.

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

      Thank you, but why is that the cost?

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

        An insight for LandSplitter: Imagine that the land you are dividing is a complete graph on N vertices. The tax you pay when you cut into pieces is equal to the number of edges you cut. Thus, minimizing the total cost is the same as maximizing the number of edges that remain uncut in the end.

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

    Can anyone tell how this problem could be solved in O(1). This has done that.

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

Why topcoder doesn't allow people with the non-positive score to hack?

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

    Probably so that you couldn't have a random new account (totally not a smurf) who challenges everyone in the room on 100 tests.

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

    Really? I thought it's "negative" instead. We are able to challenge (we don't say "hack" in topcoder) for having 0.00 pts, I guess.

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

    Possibly how many failed challenge attempts for a user is mistakenly stored in an integer. If somebody failed for 1 << 31 times, they would get positive score :-p

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

Lol Jatana got more points from 250 by challenging than by solving but got challenged on it too.

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

How to solve Div1 1000?

I did something like "repeatedly get the non-decided longest path and assign values of arithmetic progression", but it failed in system test.

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

    Here's a simple counter case

    0 3
3 4
4 5
0 1
1 2
2 5
1 4

    Answer should be {0, 1/4, 5/8, 1/4, 1/2, 3/4, 1}, but yours gives {0, 1/3, 2/3, 1/4, 1/2, 3/4, 1} instead.

    how to fix
    → Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Hi, is the editorial from this SRM will be publish? ( Cuz in the link you provided the last editorial is from SRM 771 ). Thanks.

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

What was the intended solution for Div2 500 points? Thanks.

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

    Primes are quite dense, so anything reasonable that goes through all possibilities will work. (I.e., iterate over all possibilities of how many digits you add, where you add them and what they are. Stop once you find a prime.)

    For a short correct solution, special-case N=0 and N=10^9, and for any other input N check the numbers N000 through N999.

    (The first sequence of 1000+ consecutive numbers occurs only somewhere after 10^15. Our numbers are smaller than 10^12, so there is certainly at least one prime among them. See Prime gap (Wikipedia))

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

The last editorial is for SRM 771. What about editorials for 772, 773 and 774 — are they going to be made available?

→ Reply