hmehta's blog

By hmehta, history, 11 months 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

»
11 months 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.

»
11 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Gentle Reminder: The match begins in 1hr 30mins

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve land splitter?:(

  • »
    »
    11 months 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$$$.

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

      Oh, right. Thank you.

      So, how to solve landsplitter? :-)

      • »
        »
        »
        »
        11 months 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.

        • »
          »
          »
          »
          »
          11 months 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?

          • »
            »
            »
            »
            »
            »
            11 months 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.

          • »
            »
            »
            »
            »
            »
            11 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            As Xellos is telling us, it does involve basic stuff. For example, if you break it into two pieces then they have to be equal like he said, as moving them apart increases the cost.

            I had to prove that differently, if we break N into two pieces N = X + (N-X), then the cost is X*(N-X) = N*X-X^2. You can take derivative: N-2*X and set that to zero to minimize, solving that gives us X = N/2 as the lowest cost if you split into two pieces. That too is basic calculus.

            The difficulty I have is that these tasks are a linked series of basic facts and it's hard to know how to link them together to solve the whole problem. Anyway, that's where the learning comes in, so it's good. Thanks for the hints, Xellos!

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you, but why is that the cost?

      • »
        »
        »
        »
        11 months 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.

  • »
    »
    11 months 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.

»
11 months 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?

  • »
    »
    11 months 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.

  • »
    »
    11 months 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.

  • »
    »
    11 months 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

»
11 months 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.

»
11 months 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.

  • »
    »
    11 months 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
»
11 months 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.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    11 months 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))

»
11 months 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?