Topcoder SRM 788 is scheduled to start at 07:00 UTC -4, July 24, 2020. Registration is now open for the SRM in the Arena or Applet and will close at 06:55 AM, so make sure that you are all ready to go. Please note that the coding phase will begin at 07:05 AM UTC -4 but the registration will still close at 06:55 AM UTC -4.
Thanks to square1001 for writing the problem set. Also thanks to misof for testing and coordinating the round.
This is the first SRM of Stage 1 of TCO21 Algorithm Tournament.
Choose Your Competition Arena
There are two ways to compete in Algorithm Competitions or Single Round Matches (SRMs). Read here to find which works best for you.
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!
RIP Applet. RIP TC.
#makeTCgreatagainTopcoder is slow.
This time, since my twin brother is the problemsetter, I am really looking forward to participating in this contest! :)
Login Time Out. Please try again later error is coming again and again when tried to login into the arena. Did anyone also has the same problem?
Hey! Web Arena is down. We are actively working to bring it back up. I will update here as soon as it is back up. Applet is working perfectly fine and you may register for the contest using the applet.
Sorry for the inconvenience caused!
Ok Thanks
Well now it is opening
How to access any(all previous) SRM editorials?
You can access by typing in the google, the editorial for any specific SRM.
Recently, there is a convenient thing called "thrive". We can search most editorials, from the old to the new, in this system.
Hello from Japan! I am square1001. This time, I'm writing a contest of SRM for the first time in my life.
If you are new to Topcoder and do not know how it works, I suggest you to read an official guide which is easy to understand. This explains how to participate in a TopCoder SRM, and how the contests of TopCoder SRM works, in particular.
Please note that the registration ends at 6:55 AM (UTC-4). I am really looking forward to your participation!
I thought for a moment it's some deep-fried meme or something. This background is very bad, it's hard to read some parts.
Gentle Reminder: The match begins in 1hr and 40 mins :)
The point values are disclosed!
[Deleted]
Thank you for your participation! How was the contest? Was it enjoyable?
If possible, I want you to answer a questionnaire about today's SRM 788, because I seriously want to improve my contest creation skills, and also want to improve TopCoder itself.
P.S. Editorials are up! If you prefer PDF, it is available here.
Thank you for writing such a detailed editorial! I wish everyone wrote editorials this way.
That was awful even by TopCoder standards
The easy and hard were too standard, true. But I kind of liked the medium, even though it wasn't super complex either.
The medium was nice, I agree. But that doesn't justify giving easy and hard in any contest.
Actually, I did not think that Div1 1000 was so standard. When I submit problems, I rate "how good the problem is (quality rate)" for all problems I submit, for thinking around 20 minutes. This is rated from 1.0 to 9.9 which larger value generates the good answer for problem.
In this scale, I actually rated Div1 500 as "one of best problem I created this year", and rated Div1 1000 as "confidently publishable in AtCoder contests", which means exceeding average quality rate of AtCoder Regular Contests.
I know that after the contest many people regarded Div1 1000 as typical-side problem. Maybe I need to practice flow problems. Since I am an OI person, I am of course not good at problems of flow algorithms. So, the quality rate of Div1 1000 has decreased a little after the contest.
However, I thought that Div1 250 was standard. But it is not standard for blue and lower-yellow people. Creating problems that is both interesting to blue coders and targets, are very difficult task for all human being.
This problem is worse than (I think) all non-100/200 AtCoder problems I have seen.
How many minutes did you think about rating the problems? I thought, even in ARCs, I rate ARC 084-E, ARC 092-E, ARC 072-D as lower than this Div1 1000 by a far margin.
I also publish many problems in AtCoder, yes. But I rate Div1 1000 as higher than one third of the problems (at least 300 points) I published in them.
I thought that your comment "thinking around 20 minutes" was laughable, but you seem to stand by it. The time is bounded by [time needed to solve the problem] + 1 minute. Why would I need more?
All 3 problems you have linked are much better than todays hard.
No. I don't think so. That's because I have more evidence. My quality rate is based on how many people are enjoyable and how many people can feel "algorithm is a nice thing!", not by "how one person Um_nik feels good".
In reality, some red coders regarded Div1 1000 as "enjoyable problem". This is not a joke.
I only care about "how one person Um_nik feels good" and he doesn't feel good about this problem.
You and your brother are "some red coders" so that's probably true. Doesn't make this problem enjoyable for other red coders though.
No, you are false. My brother is currently yellow in TopCoder, so I mean other people. Currently no one rated less than 3 stars for Div1 Hard.
Also, you said 'I only care about "how one person Um_nik feels good"'. Do you mean that, when you make problems in Codeforces or elsewhere, you disregard all the other people's impression!?
When you are give opinions about not your problems you also ask a lot of people and form your opinion based on their opinions? I now rate your problem, and I rate your problem as shit. Of course I base my opinion on my feelings, what other criteria do I have? Consider me as someone who give this problem 0 stars.
I am replying this because I am thinking that post-contest discussion is a great way to reflect on my problem creation. I really want to improve my problem creation skills.
If I am a contestant, I evaluate problems in two ways. The first one is feeling, which how good I felt by solving this problem.
The second is the detailed quality rating. That is because I want to improve my quality assurance skills, and increases many samples of reasons for making/not-making quality for participants. If there is a sample of each problem which has a quality of 5.9, 6.0, 6.1, ..., 8.0, 8.1, and 8.2, we can determine the quality by binary-search that compares quality of problems.
Of course, I respect all people's impressions of problems. So, I embrace your opinion as one person's evaluation.
And what this quality measures? How good the statement is written? How detailed are sample explanations? How good are test coverage? You say that the quality is a number but you don't give any guidelines how to calculate it.
Since my quality rating system is run only for 1 year, it is not concrete, but I have a guideline.
First, I write all steps of any possible solutions. And for each way, I find how interesting each step is. This is the "first-part quality".
Second, I assume a person who sees the problem statement at a glance. Some people will think "it doesn't seem to be a solvable problem". If this value is higher, the more they will be impressed in a moment when they come up with the solution. In this meaning, problem statement also matters, because it may increase how they want to solve problems.
Third, I think about how people can gain skills about algorithmic thinking. For this reason, math-only problems tend to have lower quality rate in my guideline.
For Topcoder-only rule, if the input is large and requires random generators, the quality rate will be lower.
I think that your method is bullshit (and later I will explain why), but for the argument's sake let me use your guidelines to calculate quality of your problem.
How one person Um_nik feels about this problem, but now with numbers!
First: write steps of any solution. I will describe how did I solve this problem during the SRM.
1. Read the statement.
2. I know this problem.
3. Copy-paste Dinic.
4. Write ugly restoration of answer.
I actually consider only 2nd as "part of solution", but even considering all 4 I give this problem score of 0/100 for First step.
Second: I was a person who saw the problem statement "at a glance", so let's consider my reaction. My reaction was "I know this problem, it's obvious flow". How would I measure "it doesn't seem to be a solvable problem" effect? Hmm, let me see... I would say 0/100, because I instantly knew the solution, so this problem gets score of 0/100 for Second step.
Third: I have now idea what do you mean by "algorithm thinking" and how do you measure from which problems people can gain algorithm thinking. I will give score of 0/0 for "indeterminable criteria".
Total score: 0 stars, shitty problem!
Now about methodology.
All of your scoring are subjective (because, let's face it, all we say is subjective), but you try to make it quantitive to make it scientific. The difference with my method is that I'm bold enough to say that I just measure how I feel after solving this problem. And I would say that this is even more accurate than try to dissect the problem into parts, score each part and then combine the scores. Because problems are different and that's great! We shouldn't compare data structure problems to constructive problems — they are different and we should embrace it! Good mathy problems don't need any algorithms, good graph problems don't need any segment trees, and good data structure problems don't need any ad-hoc things.
How I feel about the problem already includes all of your scoring parameters (except "how people can gain skills about algorithmic thinking", I still think that you have some mental problems) and mixes them in right for this particular problem proportions. I'm sure that I won't be able to find the exact same problem, but this problem doesn't feel fresh and it's enough for me to dismiss it as not fresh.
First of all, I would like to appreciate for your detailed explanation. For me, "2. I know this problem" was quite surprising because:
First, no one knows all problem. Since I only have rating 2772 in TopCoder, it is difficult to think about how rating-3300 people are working on the problem. Third, you are saying that the quality rating is subjective, but you are being the most subjective. That is because, you are not thinking about other people.
I know that you are stronger than both writer and tester in this case. In this reason, if I respect every words on you, we can read it as you're saying "people who is below your rating should not do the writer."
This time I believe your words that you already knew the problem. So, your opinion is very biased because most did not know the problem — supposing that we did not know the problem, we have to come up with (as written in editorial):
Now everything is clear. You rated quality low because you knew this problem. That's all. I am sorry that I was not capable of knowing this problem.
I didn't say anything about "lower rated people shouldn't be authors". But coordinator should reject such problems, that's for sure.
If you think that "subjective" has negative connotations I don't know how to discuss anything with you. You are now saying that your subjective opinion + your tester's subjective opinion (= objective opinion suddenly?) dominates my subjective opinion. That may be true, because 2 subjective opinions are better than 1, but at only 2 times, and that doesn't mean that you can dismiss my subjective opinion. My subjective opinion + majk (I'm sorry, I know that you are a very nice person and you probably do not agree with my harsh words) subjective opinion are already not less (and counting by experience probably even more) than your "objective" one.
You can see that I have never said that yours or your tester's opinion about this problem are incorrect. Because that's not true, these are your subjective opinions and of course they are correct! Based on these opinions you thought that the problem is great and decided to use it in contest. That's ok, now I can say my subjective opinion that this problem is really bad. Please don't dismiss my subjective opinion because you already formed your objective opinion that this problem is great.
This is not a personal attack on you (though I certainly hate you and most of the things you stand for). You are afraid of having subjective feelings for some reason, and you try to hide them behind some "scientific numbers". That's a huge mistake.
No one solved this problem by reducing to ILP and then to flow. That's crazy. The fact that grid can be colored in checker coloring and the graph is bipartite is well-known, and using it as means to make problem about matchings/cycles (yep, they are very close, you can think why) to matchings/flows on bipartite graph is also well-known. Basically that's what I'm saying when I say "I know this problem". As I said earlier, I don't think that this particular problem appeared before (or at least that I have seen it). But it's basically educational problem on "grid -> bicoloring -> flow" pattern which I have seen many times, so yes, this problem is not fresh.
Here, I would like to leave some comments here.
I am very seriously receiving the post-contest discussion into my heart. That is because, I made my best effort on creating this problemset. There are of course, things that improvements are needed — I did not realize that Div1 1000 was a typical-side problem. I thought that it was completely concept-based.
I am also ready to analyze other things. I think problem statement can be improved. I think examples and its explanations can be improved. I think test data can be improved. I think qualities of all 6 problems can be improved. I think that problem difficulties was not perfect. I even think that editorials can be improved.
That is what I consider all the time when creating the contest for seventy hours of preparation. I do not want to finish things like "I created the contest. It's finished. That's all". In my thinking, a contest is an artwork of which is viewed for tens of years after the round. I modestly say thanks to those participants who enjoyed the art gallery, which means SRM 788 itself. If some people thought "wow, algorithm is a nice thing!" in the exhibition, I will be very happy because this is one of the reason of which I create contest.
I am seriously considering the impact of COVID-19 pandemic. As shown in Div2 Easy, today is the holiday to celebrate the beginning of "Tokyo Olympic 2020", but it was postponed, so a large number of Japanese citizens are in the empty feeling. I know that many people are under lockdown. I know that, for example, many university students are suffering from lots of work under online classes. I know that many people turned life not to be exciting. I hope that the artwork of SRM 788 could give any bits of light for those people.
Here it's midnight in Japan. As an afterword, again, thanks for your participation.
square1001
Take it easy)
The problem of "well-known" problems is that they are well-known for someone, and not for others. I solved too many maximal-flow problems, when they were popular, so when I see problem like this, I see the maximal-flow immediately, but that's my experience. For someone who didn't compete when these problems were popular, it may be very tricky.
To avoid situations like this, it's a good practice to show your problemset to some experienced contestants. But even this may not guarantee that the problem is new. For example, when we prepared the problems for IOI 2016, in the day before the tour, we found out that one of the problems was used in some ICPC regional contest.
It happens, it does not mean that your problemset is bad. I enjoyed it very much. Hope to see more SRMs from you.
After every SRM always here criticism. So take it easy :) and take as just a feedback.
I liked div1000 but got hacked :)
It's good to want some feedback @square1001, so here's a general advice — if you aren't strong in some topic, you must ask a friend (or just someone strong at it) if the problem is good. That's especially important for hard problems. I was always scared to create problems on flows, strings, and game theory. That fear made me cautious and it helped me avoid giving boring/standard/bad problems.
I took a look at the problems, and I agree that d1-easy and hard are very standard. The bipartite grid thing in div1-hard occurs (or occurred?) frequently in icpc trainings and contests. Something as standard as div1-easy should be used only in div2 or educational contests IMO. But div1-med indeed seems interesting (though I would likely start thinking about $$$O(2^{22})$$$ solution during a contest, as $$$22 = \sqrt{500}$$$).
Thanks for the round! The medium was very nice indeed. My easy-hard-medium strategy has hurt me this time, as after submitting the hard I saw others get 500+ points for the medium and submitted it without enough thinking, leading to a resubmit later.
My screencast: https://youtu.be/yrFAMaDVbOo