hmehta's blog

By hmehta, history, 9 days ago, ,

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

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

 » 8 days ago, # | ← 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.
 » 8 days ago, # |   +12 Gentle Reminder: The match begins in 1hr 30mins
 » 8 days ago, # |   0 How to solve land splitter?:(
•  » » 8 days ago, # ^ |   +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$.
•  » » » 8 days ago, # ^ |   +20 Oh, right. Thank you.So, how to solve landsplitter? :-)
•  » » » » 8 days ago, # ^ |   +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.
•  » » » » » 7 days ago, # ^ |   0 Is there a book or set of tutorials to help you prepare for such problems or is this supposed to be basic stuff?
•  » » » » » » 7 days ago, # ^ |   +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.
•  » » » » » » 7 days ago, # ^ |   0 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!
•  » » » 7 days ago, # ^ |   0 Thank you, but why is that the cost?
•  » » » » 6 days ago, # ^ |   +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.
•  » » 5 days ago, # ^ |   +3 Can anyone tell how this problem could be solved in O(1). This has done that.
 » 8 days ago, # |   0 Why topcoder doesn't allow people with the non-positive score to hack?
•  » » 8 days ago, # ^ |   +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.
•  » » 8 days ago, # ^ |   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.
•  » » » 8 days ago, # ^ |   -39 Do we say "f*ck you moron" in topcoder?
•  » » » » 8 days ago, # ^ |   +83 ...what?
•  » » » 8 days ago, # ^ |   +16 My score was -25pts and I got this popup. I was denied hacks. Spoiler
•  » » 6 days ago, # ^ |   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
 » 8 days ago, # |   +34 Lol Jatana got more points from 250 by challenging than by solving but got challenged on it too.
 » 8 days ago, # |   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.
•  » » 8 days ago, # ^ | ← 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 fixInstead of longest path, choose a path where (difference in endpoints) / (length of path) is minimized. We can show that this quantity only increases at each iteration which helps prove correctness.
 » 7 days ago, # |   -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.
 » 7 days ago, # |   0 What was the intended solution for Div2 500 points? Thanks.
•  » » 6 days ago, # ^ |   +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))
 » 7 days ago, # |   0 The last editorial is for SRM 771. What about editorials for 772, 773 and 774 — are they going to be made available?
•  » » 4 days ago, # ^ |   +2 We are working on it. Should have them up within a week.
•  » » » 4 days ago, # ^ |   0 Great, thanks!