Блог пользователя hmehta

Автор hmehta, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • +43
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +15 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Gentle Reminder: The match begins in 1hr 30mins

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve land splitter?:(

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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$$$.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +20 Проголосовать: не нравится

      Oh, right. Thank you.

      So, how to solve landsplitter? :-)

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +13 Проголосовать: не нравится

            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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you, but why is that the cost?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
4 года назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

    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
»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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))

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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