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!
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.
Gentle Reminder: The match begins in 1hr 30mins
How to solve land splitter?:(
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$$$.
Oh, right. Thank you.
So, how to solve landsplitter? :-)
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.
Is there a book or set of tutorials to help you prepare for such problems or is this supposed to be basic stuff?
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.
Thank you, but why is that the cost?
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.
Can anyone tell how this problem could be solved in O(1). This has done that.
Why topcoder doesn't allow people with the non-positive score to hack?
Probably so that you couldn't have a random new account (totally not a smurf) who challenges everyone in the room on 100 tests.
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.
Do we say "f*ck you moron" in topcoder?
...what?
My score was -25pts and I got this popup. I was denied hacks.
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
Lol Jatana got more points from 250 by challenging than by solving but got challenged on it too.
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.
Here's a simple counter case
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.
Instead 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.
Hi, is the editorial from this SRM will be publish? ( Cuz in the link you provided the last editorial is from SRM 771 ). Thanks.
What was the intended solution for Div2 500 points? Thanks.
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))
The last editorial is for SRM 771. What about editorials for 772, 773 and 774 — are they going to be made available?
We are working on it. Should have them up within a week.
Great, thanks!
hmehta it's literally been a year, no editorial for 774? :-(