Topcoder SRM 740 is scheduled to start at 12:00 UTC -4, Oct 20, 2018. You will be able to register for the SRM in the Arena or Applet 4 hours prior to the start of the match. Registration closes 5 minutes before the match begins, so make sure that you are all ready to go.
Editorials: https://www.topcoder.com/blog/single-round-match-740-editorials/
T-shirt winners: http://apps.topcoder.com/forums/?module=ThreadList&forumID=641988&mc=3
T-shirts: T-shirts will be awarded to the following members*:
Top 4 and 2 Random participants having scores > 0 in Division I
Top 4 and 2 Random participants having scores > 0 in Division II
*Only those members who registered on Topcoder on or before 09:00 UTC -4 October 18, 2018 are eligible for winning T-shirts.
Featured Problem Writer: misof — misof
Interested in writing problems for Topcoder Matches? Learn more and submit your ideas here.
TCO19 Points Leaderboard: https://tco19.topcoder.com/home/algorithm/algorithm-leaderboard
Topcoder Java Applet: https://drive.google.com/file/d/1gVJZxhWYMuUNx3PfSSTkkk-b9AeJkL4j/view
Hope to see most of you competing! All the best!
Next SRM 741: October 30, 21:00 UTC-4
Interesting fact: The Top-5 TCO points (which can be seen from this blog) is 17, 16, 15, 14, 13, which is all distinct!
hmehta Sorry that I am bringing this issue up so late but I am doing so only since prizes are involved in this srm.
Does topcoder have a plagiarism detector ? I bet you don't. Let me just tell a little story to ya. Its about the SRM 738 and how a man can perform to the extent of superhuman(tourist) 's capabilities.
A person participates in SRM 738 Div2. He solves the first problem getting 171.92 points on the first one. He also solves the second problem passing sample cases and scoring 257.43 on the second problem. Nothing special so far. Alright, then comes the challenge phase. I open up the division summary phase and notice 2 people with the same name (So what ???). One of them is the person I mentioned above and another person (Hold on to your seat belts ladies and gentleman, this will blow you up) scores 249.26 on the first one (So what you just need to be a fast typist). But wait, that's not all for it. He also scores 599.96 / 600 on the second one (WTF!!!). I mean seriously. (You want more ???) And the person's a gray coder. (Not too often that you see grays getting that high a score). The kind of problem it was, even tourist could not have got more than 599 on that (It takes at least some time for even him to type the code or does it ???). Then, I notice that there is another person with a similar name participating in div2 the one I mentioned above. I look at both of their codes and well even my linux's diff couldn't distinguish between the codes for both of their 600 pts. problem. (Man, brain to brain communication is already happening. These are amazing times that we are living in.)
...And now off to the climax of the story (Did anyone say happy ending ?). The first person's solution gets hacked by someone in the challenge phase and the second person fails the system tests. End of the emotional story.
BTW, here's the first person and here's the second one.
And here are the submissions: * 250 pts. First second
My point here is that it's just a single instance and believe me this is the first time I have seen such a thing. The reason that its gonna have a bigger impact is that on topcoder your score is counted from the time you open up the problem statement so these incidences of opening a fake account to submit a problem and then using your original account to submit to get almost a full score may increase a lot (Maybe they are already happening, who knows ?) I didn't bring it up earlier since it was only about ratings earlier and I don't think even with a fake account a man can beat the red coders unless he himself is a red coder. But since you are offering T-shirts here, There might be many such instances and of course the ratings also count towards TCO 19. So, it directly influences there (or does it ? IDK).
What's worse is that this problem cannot be solved even just by solely using a plagiarism detector. Since SRM problems are not full feedback (not even checked against samples, thats your responsibility), a person just viewing with a fake account and submitting with his real one would ruin the competition. I think it's time to upgrade the competition structure at TC as a whole. From the arena to the way the actual contests work. This will take time but it'll be good in the long run.
Hey roll_no_1, Thanks for bringing this to our notice, we do have a plagiarism detector script which we run after the match. Sometimes we are able to find out these cases manually too as we keep on looking at the codes being submitted during the contest. And, there is a case from the previous SRM which we are investigating.
Also, yes we will be more careful with prizes and points involved. :)
Plagiarism detector will solve nothing. You can open the problem with one account, think it, code it, test it and then, once you're sure your solution is correct, open again with another account and submit for a full score.
Checking codes for plagiarism isn't enough in Topcoder. A participant can open statements in one account, read a problem and solve it locally, submit from their main account. When there are prizes involved, you should look into times when someone opened and solved a problem. If someone opened a problem at 10:00 and solved in 3 minutes, then opened the next problem in 40:00 and solved in 10 minutes, that's suspicious.
If someone is cheating like that but submitting a problem in seconds, they are stupid. But waiting for a few minutes can be detected only in a way I described above, I think. The only alternative I see is doing a more complicated cross-check to see if two accounts open problems in some connected pattern in multiple rounds.
What about doing nothing for 1 hour, then spend 5 mins on each problem? It even can be the case of real participant, just being late to the round (probably in reality he/she would just skip but if he/she is confident...)
Even worse: what about solving A in the last 5 minutes, B in the last 10 minutes, C in the last 15 minutes?
I kew it, topcoder is great again
I was late to register, Is it correct that I couldn't see statements until the contest end?
I'm getting the impression I completely misunderstood 250 (that's what the samples are supposed to avoid, right?). So tourist's code, when given ilkoProb = 0, deliverProbs = {}, returns probability 1. Wut? If the model's success rate is 0%, then the forecast (passed through nobody) will always match the weather?
Ilko has perfect knowledge and can say the inverse of the forecast
I got 14 hacks because of this :D
Can't he do more things than just decide if he wants to say the inverse? Why is only deciding if he should say the inverse optimal?
His whole output is one bit. Thus, one point of view is that he can only choose that bit in the best way possible.
Still, I like a more detailed point of view here: There are exactly two things he can do (that matter).
First, when reading the output of the model he should invert it if the model's success rate is below 50 percent. Once he does that, he knows what he wants the station to broadcast. Then, he needs to compute which of the two options he should actually tell them so that it will be more likely that they will broadcast the one he wants them to broadcast. So in some cases he may essentially negate the answer twice before sending it.
Can't he just make a better model? Pretty sure there's nothing in the statement saying he can't.
Yes, you did. You are not alone in that (by far), and this was expected and intentional.
Take this as a warning that you read statements too quickly. Skimming the statement and guessing half of it from the samples is a valid risk you can take, but you need to be aware that you are taking a risk when doing so, and this was a deliberate case of a problem where said risk doesn't pay off.
Please stop creating problems.
Wow, that's quite harsh. Care to elaborate?
So, you gave a round which consists of:
250: There is no algorithmic problem or math problem or problem at all. It's just 'write what is written in statement'. You gave this to prove some point about reading the statement, now I see that it was intended. I don't think that you can do this to participants.
500: This is ridiculously easy problem for 500. The problem itself is OK, with limitations about 1e9 for numbers on dices it could be good div1easy.
1000: This one is pretty straightforward too. DP is simple and well-known, and then you can just copy matrix exponentiation or (worse) Berlekamp-Massey. Worse because it is harder to write by yourself AND there was blogposts about it recently.
About Berlekamp-Massey and overall difficulty estimation. Don't you think that platform coordinator should be frequent participant and know about current state of art in CP?
I'm sorry you feel that way. I cannot change the way you feel, but I can at least offer some comments from my point of view.
With the medium problem we are currently aiming at somewhere between 40 and 60 percent of people solving it. By eye, the actual number is probably a bit over 50 percent and I think that's quite good. Ridiculously easy for you and ridiculously easy for our average div1 contestant aren't the same thing. It does mean that you are really good at solving problems, but we don't want SRMs that are only fun for the top 10.
I mean, this was not a straightforward DP, you need to combine a greedy choice (of a subset of numbers to try), DP, and the observation that it doesn't hurt if you end with a die with fewer pips than needed. Sure, to someone with your level of experience all those steps seem trivial, but there are many other contestants who can learn to make them on problems like this one.
As for the 1000, both me and the tester (monsoon) had different matrix-based solutions and I found both of them cute. We did miss the alternate approach via Berlekamp-Massey, and that's fully my bad. (The problem is still hard but I agree that the existence of this solution makes it less interesting if you know it.)
As for the 250, this is a math problem for people two colors below you. Computing the probabilities is actually a very simple form of dynamic programming, and you need some kind of mathematical maturity to see it instead of being stuck on 2^50 subsets of liars. This problem would absolutely be too hard for a Div2 250, for example.
And finally, the point I wanted to make with the 250 isn't just about reading the statement. The intention was to go a bit beyond your comfort zone. The easy problems in programming contests are often turning into typing contests only, and that's a shame. Hence, I tried to create a problem that's conceptually really easy but you have to really think about it and correctly model what it tells you instead of just typing. I went to great lengths to make sure the statement is as clear as I could make it, and I even inserted the Note I already mentioned to tell you that something is going on.
500 had two DP approaches:
First one is just above 1e8 and it is unclear if it will fit in time. #2 clearly should fit the TL. I really hate such situation when you come up with a solution and doubt if it should fit the TL or should you improve further. I wonder why you had chosen such limit.
On the other note, is there a greedy solution to this problem?
IIRC, my reference solution (that implements the first approach you mention, as I wanted that to pass) runs in 0.2 seconds for the largest test case on TC's servers. I thought that margin was wide enough for comfort.
I'm not aware of a greedy solution. There might be one, but the few approaches I tried didn't work.
Is something wrong with the above? Why did this particular post get downvoted?
I went back and checked, the worst-case running time of the reference solution was indeed 0.26 seconds. (And that's Java, C++ is usually a bit faster.) Many contests set time limits to values like "four times the reference solution", this is still about twice as much.
Already 10 years ago "10^8 steps" meant "you are safe" in all contest with not-crazy limits. The machines could do 10^8 simple operations per second, and in this particular situation (a DP with arrays that has to be fast because it's cache-friendly / recursion with memoization that obviously avoids enough states to be fast too) I wouldn't even hesitate.
Do you really see this differently? If yes, can you explain why?
Did anyone try this type of solution and actually get TLE for their (C++ or Java) implementation?
(Or is it because I can't magically disprove the existence of a greedy solution? I have honestly no idea here.)
I agree with you on the difficulties. Um_nik is a massive cunt (or at least that's how he'd word this) in that he expects everyone to be on his level. With 3 problems, it's better if 500 has a decent number of solutions and 1000 has a number of solutions in double digits.
Still, you completely missed the point in trying to make sure the statement is understood by people who really think about it / don't skim the statement. Explaining the same unclear thing multiple times (the note) doesn't help. I, for example, assumed it's just something formal because no other option remained available and face it, notes like "the solution doesn't depend on properties of the RNG" or "it can be proven that blah" are just that. Ilko can do [unspecified].
Here's what would work: use a sample that takes care of this, don't explain it. Let people figure out what it means, spend time thinking about wtf is going on and maybe solve the problem correctly. Or just don't make it a testable sample but part of the statement (with a correct output, ofc). I'm not sure if it would've helped me, but at least I would have had no cause for complaint. It's really weird how, just 2 rounds after you mentioned samples aren't there to test the correctness of your solution, but understanding of the problem, you make a problem where samples don't do that. They're like US cops at this point, aren't even required to help.
Finally, you have better contests for experimental problems. Make an educational CF round, put shellgame-lite there (for non-Slovaks, shellgame is a troll problem on a local judge). TC doesn't need any less contestants.
Those are all valid points, thanks.
For another perspective, for me it worked exactly as intended: after a quick read I did not understand the problem, but after reading carefully the wording of the statement really helped me to pick the correct formalization of the problem.
How did you decide that should be the correct formal statement? It just felt right?
It felt right indeed (i.e. the statement made perfect sense with the correct formalization), but in particular this wording was insightful: "Every day at 4:47 pm, Ilko runs the model, reads its output, thinks about it, and finally he sends a one-word instruction to the TV station: he either tells them to broadcast the word "sunny" or the word "rainy"."
I.e., from this sentence it became clear that the output of the model and the instruction sent to the TV are two separate things, where the latter can be based on the former but is not necessarily equal to it.
Yeah, I noticed that, but it just confused me more. Example: so he can just send a better model's prediction?
Xellos, did you understand 250 problem after editorials?
If author have given good samples in the contest there would not have been point in 250. It would have losen it's value.
250 should be classified as risky problem(I understand intentions of author now, but it didn't work out in reality, did it?). Especially with combination with current 500(since it is a bit easy). I have finished coding 30min before end of srm. for 1000 I had no idea. For me srm was like TCO 1A round.
What authors should strive is not passing rate for particular problem, but to keep coder busy. To pursue close call. The battle with ticking time.
c*** word is unfortunate. Let be polite in site. Umnik is not 100% wrong.
I don't think I need an editorial for 250, it's a question of interpreting the statement, not of knowing how to write the code. I now understand why one can arrive at this interpretation of the statement, but still consider it confusing.
There's nothing wrong about the easy problem being easy, especially if the general intent in SRMs is now to make the second and third problem not overkill like before. There's something (not all) wrong about making an easy problem harder by making the "understanding" part harder.
Oh, that's a very, very bad idea. You keep coders busy with casework, problems with nasty implementation or geometry... or geometry with nasty implementation.
Listen to this advice, Um_nik!
On every given thought you see only negatives. Why so?
By making coders busy I meant making them busy without all you mentioned. How? to work out non trivial bijection, some nice combinatorics or biparate matching or some other graph theory(PerfectTriangle is excellent geometry by the way in previous SRM).
The 250 problem remains easy. If statement is unclear why red coders solved it then?
In arena tourist explained you that idea came to him light and easy. It is us who rushed and neglected this problem. Understanding problem is difficulty of the problem.
I read only relevant messages of Umnik. non relevant messages I even did not bother to downvote )).
I could ask you the same question.
What you're saying is basically that you want to make nice problems and be a good problemsetter. Sure. Everyone wants that. I don't think it even needs mentioning :D
I could set a problem "print 0 or 1" with 1 hidden test. The statement is unclear, yet approximately 50% of red coders should solve it.
I didn't point out that you're blue. Do you really want to make colour relevant to this discussion?
I didn't rush, as I mentioned here already. I read this properly, didn't understand at all, so I guessed. And do you really want to compare with tourist or other people at the complete top?
Also misof points out that tourist resubmitted.
Now I see Umnik's nasty answer. misof is a great writer. Everyone's effort who tries to help community is huge since one writer contributes more than 100 of participants. keep it up misof.
regarding our discussion: On some points we agreed 0=0.That's a good sign.Writing good problems is hard.
By comparing to Tourist(or any other topper), why not to compare? Look at tourist's code. Does it make big difference with my wrong solution. No. There is small catch. Maybe what tourist wanted to say is to take a little bit different perspective?
Ok I don't want to argue. The 250 was tricky one. I just wanted to look positive sides of it. If you ask me to give negatives I can make list of it)))
By the way I hate being this color.
Um_nik is a massive cunt without ors. But under be polite you people (probably not you Xellos) hiding something like "leave your opinion to yourself".
I didn't know that you changed 'rules' about percentage of people solving given problem. Then my point about '500 being easy for 500' is of course invalid.
But this raises another question. This year you introduced TCO stages with greater amount of points given to participants in top-25 and top-10. Also only 11 people will get something from one stage. So for ~30 people who really have a chance to be in this top-11 the round consists of 1 not very hard problem and insane amount of hacks. Do you think that this is OK?
I agree that I was wrong not to consider majority of participants, for them problems were of reasonable difficulty and this is great. Since I'm very selfish I now see SRMs as a race for TCO points. And this SRM was not good in this sense.
I see only one solution. Give more problems. I think that one more problem in this SRM would make it significantly better.
I completely agree. One more problem in this SRM would make it significantly better for the people racing for TCO points. I'm not ready to change the SRM format yet, but it's certainly something I'm thinking about. Times change and sometimes we have to change with them.
Please stop posting useless hateful comments. Grow up and learn how to give constructive criticisms.
Oh really? Don't think that you can give me advices on writing useful comments.
come on, first bmerry is gone, and now you want misof to retire from problem setting?
Not really, but I think that his decisions this time were bad, and if I wouldn't tell about that, he might not know. And yes, I'm pretty sure that I am one of very small amount of people who are stupid enough to say that out loud.
Wording is not important, but feel free to give me your almighty downvote to teach me a lesson.
For what it's worth, I did upvote your second post on the matter (the one where you gave your opinion on the problems). Writing down actual arguments is good, and so is receiving feedback. As an author I want to learn just as I did as a contestant, I'm carefully reading all feedback everyone posts, including yours, even if it's negative.
(On the other hands, empty negative posts with no arguments are just a way to create bad feelings but never a way to help another person grow. Please learn to give feedback without resorting to those.)
I wouldn't put it that strongly, but here are my longwinded thoughts to both @Um_nik and @misof.
I do think that topcoder has by far the most unfriendly ruleset and it is really punishing to noobs (because the pretests are intentionally weak + challenge system), and the experience is made much, much worse by these kinds of "gotcha" rules.
"It's expected and intentional" that the problem statement and examples deliberately try to make you fail the problem. Huh? Why not just have honest problem statements and examples that showcase all the relevant features of the problem? It's trying to create artificial difficulty by obfuscating the core ideas of the problem. I don't come to TopCoder to read novels about the adventures of Alice and Bob, where if I didn't read some random postscript inserted somewhere about how actually Bob says the opposite answer from what you expect if X=0, then I instantly fail.
Yes, this is skill testing ("its a skill to create your own test cases", "its a skill to read the problem statement carefully", etc.), but everything is skill testing, including reading the problem statement if it was in 13375p34k. So it also matters what the priority is.
In my opinion, the problem statement and limits should be designed so that it is about solving the spirit of the problem, not about corner-case gotchas where you randomly fail the problem. The priority of problem setting, should be to creating interesting problems that can be solved with nice ideas, and packaging these nice ideas neatly for the user to discover through solving problems.
When you make gotchas the focus of the problem, or at least a principal component, it makes people feel really bad when they fail. They feel it is undeserved because they can get the idea of the problem, code a solution that is 95% of the way there, but score 0 instead of 100. Maybe you say tough luck, but I think there is a better way shown in other CP platforms.
When I do TC, even nowadays, I expect to fail the problem like 50% due to a corner case. When I do a contest on CF, maybe that is like 10%. That disparity is because of the mindset of the problem setter. I remember as a noob, being crushed that my code would always be challenged or fail systests later. I basically scored 0 on most SRMs I ever did, and I always went into the SRM with that expectation (and never had that expectation on other CP platforms.) Even today, having gotten into GCJ Rd3 3 times now, my rating on TC is still beginner (~1200) for this reason.
I'm not going to say one view is clearly better overall, but I think no-gotchas is a better experience for new coders, and that's why I think the culture should change. As a problem writer, you have the ability (if desired), to change it directly. I don't think gotchas should be inserted into otherwise fine problems in an effort to artificially increase difficulty. If the problem is not the right difficulty, it should be run in a different slot for which it is the right difficulty.
Thanks for reading this and thanks to um_nik for bringing this issue up.
Thanks for the detailed feedback, I understand how you feel.
I do agree that Topcoder's system is less friendly, and given that there are fewer problems per round, more punishing in case of mistakes.
One thing I did now is that I looked at some statistics you may find interesting. For the last 21 div1 easy problems in SRMs and non-fun TCO rounds the median submission success rate is 78% and the mean is 78.5%. (This measures "if you submitted, did it pass?")
One point I see differently from you is that in the 250 I didn't try to make a statement that deliberately obscures what you need to do. I tried to make a statement that is as clear as possible without telling you explicitly what to do. To me, there is a difference between the two.
I didn't ignore things. I thought about them and simply didn't have a clue what they're supposed to mean. What was I supposed to do?
If I encounter some things in a statement that I don't understand, all I can do is assume they're flavor text as much as that it's Iľko. Then I can at least assume if it matters, the samples will catch it — according to your own words, they're supposed to help understand the statement, so expecting them to help me understand the statement is not a mistake.
You can always make a clarification request if a part of the problem statement doesn't make sense. Was your situation such that you couldn't think of what to ask, or were you unaware that you can?
How do I do that? I thought about it and didn't find out how. The "Messages" button was my best guess and it only shows public messages.
Keep in mind I didn't grow up with TC, something like that may be obvious to you but not to me. Now that I'm trying to look it up, I still don't know.
In the chat window: You can do that using whisper to admins for any problem clarification.
Ok, that's not obvious at all. Whisper works on people who aren't in my room too?
Yup!
I'm sorry this was the case. We probably need to come up with a way to make this more obvious. As a quick fix, maybe we can broadcast this as a message before each of the next few rounds?
I suppose. I will know at this point, but it's really something non-intuitive. The whole arena UX is awful, whether Java or "web". I would've helped with that if I was a NEET.
We are aware of the same and are constantly working on it. The backend of srms and marathons are currently being rebuilt and then we will start rebuilding the new arena front end.
Till then we will patch up and make the experience better.
Extremely sorry that the experience is not great currently, but appreciate that you are still competing.
And we promise to bring a better experience soon! :)
I couldn't think it is something fun. I hope you don't justify it because I love SRM that gives me a lot of fun by cool algorithm problems. I'm participating in SRM for fun not for learning reading English or avoiding trivial traps.
BTW, I remembered this.
I can guarantee this problem was a one-time experiment that should not repeat in the foreseeable future.
That being said, I would like to hear more specific feedback on the language used in this problem statement from contestants who feel that their English is not good (including yourself, if you feel so).
For example, was the language too complicated, and if so, do you think it could have been written in any better way (without giving away the point)?
Hmm, just I wanted to tell you is "I hope you don't justify it" not about specific problems.
You also said "this was expected and intentional". These sounds not good so I posted above comment.
I hope that SRM is still one of the most interesting contests. gl&hf.
Thank you. I do not want to turn SRMs into reading contests. In fact, one of the invisible things I do is that I care a lot about non-native English speakers and ways to write the statements in such a way that everybody can understand them as easily as possible. This is not something that magically happens, this needs a lot of work and experience.
E.g., if you have ever been at an IOI translation session, you may have noticed that often a statement that is 100% correct English and is crystal-clear to a native speaker can still be misunderstood by a person coming from a different cultural background.
All kinds of feedback on this are always welcome -- in particular, if someone feels they were unable to understand the language of the statement for some reason, I want to learn that reason.
One of the particular feedback (not related to today's SRM, and I don't remember which problem since it was years ago): please avoid pronouns like "that" or "this", sometimes "the" works similarly as much as possible, especially there are more than one objects contestants might notice.
Yeah. This is a very useful lesson for all problem statement writers, as this can make a statement confusing to native speakers as well. It applies to an even wider class of pronouns, both object and demonstrative ones.
The rule for English is actually very simple for us programmers: these pronouns should always describe the last mentioned object they can describe. For example, in "Sarah came to John and took a bite out of her apple" the apple belongs to Sarah, but in "Sarah came to Lucy and took a bite our of her apple" the default interpretation is that the apple belonged to Lucy, because she is the last valid target for "her" in that sentence.
But even though there are these rules, the "golden rule of writing" takes precedence: whenever a sentence may be unintentionally ambiguous, rewrite it from scratch in a different way.
(The danger here is that the author may write the sentence about Sarah and Lucy with Sarah's apple in mind, and they won't even realize the ambiguity is there because the model in their head makes sense. BTW, I find it interesting that issues like this are really close in spirit to programming bugs. Proofreading by a second person really helps to catch these issues, in both cases.)
tactical dot: .
BTW what about disbanding Alices, Bobs, Mehrads and Mishas from the problem statements altogether?
That's a valid question. There are certainly people who prefer a formal statement without any story. But in my experience, what those people actually hate are stories that are long-winded and useless.
I believe that asking for no stories at all is not completely correct. I aim for a reasonable middle ground: a problem statement that is 100% formally correct, but may involve a metaphor/story to the extent to which it helps explain or motivate the problem. And I have lots of evidence that a well-chosen metaphor can in fact often make the statement shorter and less ambiguous.
For reference, here are a few of the suggestions I'm currently sharing with SRM writers:
One other useful thing about short and reasonable stories is that they give you a good way to remember a good problem and to talk about it to other people.
I think that having weak samples in 250 is perfectly fine, but the wording could have been better — e.g. just add a sentence that "Ilko doesn't necessarily have to report the same weather that his prediction gives him".
IMHO the round was good and I enjoyed both 250 and 500.
When will you announce T-shirt winners?
This was my first contest on topcoder, can I really win a T-short from a div2 round even though I'm div1 in codeforces?
Topcoder and Codeforces are completely independent. You were a regular div2 participant (good job, by the way!) and I guess with results like that you won't stay in div2 for long :)
T-shirt winners will be announced within 12 hours from now. :)
Why? You can't choose 2 people? Please don't do it. So many people should wait for 12 hours. We waited for SRM one day.
The plagiarism check takes a while to check and we do a post-match investigation before announcing the results when we have prizes involved.
Sorry to keep you waiting but it does take some time and we want to be more careful and fair when it comes to giving prizes.
How to solve Div 1 1000?
Before the editorial is ready I can paste the comments I wrote in my solution. Ask if you need more details.
(There is also another solution mentioned by Um_nik in this thread that guesses/knows that the values must satisfy some linear recurrence and uses DP to find its first terms and then Berlekamp-Massey to do the rest.)
Thanks for the round! My thoughts about the problems:
250: Nice idea but samples could have been a bit stronger. Typically the purpose of samples is to confirm the reader's understanding of the problem, and that was not the case this time. Should note that there are still some interesting challenges to be made even after a basic breaking sample (e.g.
10, {}) is added.500: I liked this problem a lot. It reminds me of the classic TopCoder style -- heavy focus on problem-solving and reasonably loose bounds (so most polynomial-time solutions should pass). I thought the number of solves was almost exactly right too.
1000: Decent problem. I thought having weak samples here was pretty reasonable, and the number of solves also turned out pretty well. Solution idea was a little standard but not overly so.
Overall, nice to see the difficulty set to a level where most competitors have at least one or two problems they can approach. Huge improvement in my opinion from previous contests where >50% of participants finish with 0 :)
Right, thanks for posting this! I think Um_nik has a point that many people are reluctant to criticize, but even more people are reluctant to praise.
I agree with your assessment on 500 and 1000, whereas for 250 I think it was actually a good problem as well — the samples did not catch a certain bug in the "formalization of the problem" step, but the statement really went to great lengths to clarify how the problem should be formalized. I think it would not look so good in a problem where the solution itself is hard (i.e. people who got the solution but formalized incorrectly would feel bad), but given the simplicity of the solution, formalizing the problem is the most difficult thing here, so it's justified to fail the problem if you fail to formalize correctly.