It is very sad to see interlude at the bottom of the user rating by contribution. I liked Round #745, even considering that I solved only one problem in the first division. The tasks seemed interesting to me, they do not have complicated statements and there is something to think about.
It seems to me that many people did not like that the C problem was solved by a complete brute force with clipping.
My solution works like this: we iterate over the upper left cell of the rectangle containing the portal, then its height, and we will iterate over the width until the number of actions to create a given portal exceeds 16 (it is from so many cells the portal of the minimum allowable size consists). It is not immediately clear why, with such a clipping, the solution will work quickly, most likely this task could seem difficult to contestants. (You can try to read my comment. Maybe it will help you to understand why it works fast).
Although, it seems to me, this is not such a rare technique when in a not very complex problem (that is, in a problem where complex algorithms are hardly used), in which it is not immediately clear what to do, the optimal solution is a slightly optimized brute force.
The tasks following C were also probably difficult for most of the participants in the second division.
In any case, the tasks were of high quality and not boring. There were also no significant problems with statements or tests during the round. Such an amount of hatred towards authors seems unreasonable to me. Therefore, before you put downvote, think carefully about your decision.
Many thanks to the authors for good tasks, I am looking forward to participate in the next contest prepared by you.
I completely agree with you.
Though there could be some minor improvements in the contest like clarifying the language for a few problems and maybe adding a problem between B and C, but all the problems all together were an amazing set.
I don't think people are wrong either by expressing their anger towards the contest, but it just feels a bit sad to see that someone who had putten so much effort into making up a (Div 1 and Div 2) contest on codeforces getting so many downvotes.
If people just keep in mind the efforts that are required to make a contest like this, it would make the world a better place : )
Agreed. There were few issues with tight time limit and weak pretests and the problems were a bit harder. But you cannot always expect 100% perfect and balanced contest. The problems were quite good and enjoyable. I don't mind solving hard problems. How will I become stronger if I am not able to solve harder problems.
We already have very few Div1. contests and treating contest authors like this will not motivate anyone to create good contests anymore. At least try to give some valuable feedback rather than down-voting and abusing contest authors.
Yeah, not 100% perfect but How do you define the below statement and there were many other blunders too.
the diameter of the graph must be strictly less than k−1
What about writing k-2147483648 next time, I think it would be more satisfying distraction
Just a random guess. Maybe problem setters are big fans of one of the K-1 things and wanted to have a reference to it in the problem statement?
Oh no, there's $$$~-1~$$$ in the statement, I can't read this.
No it's not like we can't read this, but why!? just why?
I agree about the part that authors should not have got that much downvotes, but, tbh I think problems were:
Div2 A was harder than usual, many people will lose motivation if they can't solve first problem, when you get first AC you get motivated to solve further and usually get more focused. An easy problem (800-900) to start off round is probably good option.
How didn't testers notice anything? I don't know how they test, but I assume they try to solve problems and tell what they think of round, and they could say: "it's maybe harder than usual", "maybe add easier problem in between", "swap B and C" etc... But, I don't know, they probably told authors everything was fine, when it was not, and then it leads to this.
I think more people should test, so we can prevent these types of inconvenience.
Even if testers say about some problems there's no guarantee they will be fixed.
Believe me or not, the final version of the contest is actually considerably better than what I tested :). For example, the Latex texts were very poorly written, statement for C was terrible, A and B being trivial problems (they replaced them with new problems later on), and on and on. That the actual contest consisted of understandable statements is a significant development. So I think testers (not me) did contribute to improving the round — just, apparently, not enough.
About Div. 2 A. Almost every tester (at least, in the first phase I think) solved it within the first 3 minutes. I find it to be a generally easy and quite interesting A; I'm actually quite impressed and had there been any discussion about removing or keep the problem, I would be a fairly vocal supporter for keeping (I don't think it's more than 1000?). So we didn't find it to be a problem. Of course it might be because there were a lack of Div. 2 testers (again, in the first phase), but the issue did manage to fly under the radar. I think most of us didn't expect it to be difficult for you guys.
I'm not sure about other issues. Can you address them? With the exception of B's complexity being a bit... controversial, I'm not aware of them.
Give them constructive, they will cry. Give them DSA and they will still cry.
[Sorry for this comment.It's now deleted.]
"OI(Can't see verdict after submitting, get result after the contest ends)"
Like seriously or maybe I just misunderstood it?
Was D1A really bruteforce? It felt pretty evident that answer at max can be 16. And it was pretty intuitive that for every point you cannot iterate over many rows/columns before you exceed 16 and this limits the number of iterations. I am not sure about the time complexity, do tell me if I have it wrong. I do agree it was harder than usual D2C/D1A.
After reading the editorial, I realized that this solution does not coincide with the author's. Time complexity of author's one is clear. I consider my (coinciding with yours) solution to be brute force, because it iterates over all possible rectangles (with some clipping). But its time complexity, it seems to me, is also O(n^2*m).
This is so because:
1). Firstly, we iterate over left upper angle of our rectangle (it is O(n * m)) and then we iterate over height of the rectangle (in total it is O(n^2 * m)).
2). When left upper angle and height are fixed, we iterate over rectangle width in increasing order (recalculation of the answer for current rectangle takes O(1)). We finish iterating over width when current answer (!!! read end of the comment for details !!!) exceeds minimum answer found earlier (it is not more than 16).
Why total complexity is O(n ^ 2 * m)? -Because if for fixed i, j, k (coordinate of left upper angle and height, respectively) we made l iterations over width it means that for rectangles with i from [i + 1; i + k — 2] and j from [j + 1; j + l — 2] and arbitrary height we won't make many iterations over width (not more than approximately 16). In other words, it means that we will process each rectangle with i from [i + 1; i + k — 2] and j from [j + 1; j + l — 2] and arbitrary height in O(1). It is so because these rectangles do either include part of obsidian border of initial rectangle (i, j, k, l) (so we need to delete these obsidian blocks to make a portal from current rectangle) or the current rectangle is completely contained inside the empty part of the initial one (so we need add obsidian blocks on the border of current rectangle to make a portal from it). Of course, there can be "holes" in obsidian border or obsidian blocks in "empty part" of initial rectangle but their total size doesn't exceed 16 so we can neglect this.
You can look through my solution 130348658 for better understanding.
(!!! details from p.2) !!!)
I didn't write it quite correctly in the editorial, in fact, we end up iterating over the width of the rectangle if x exceeds the minimum answer found. x is the number of actions required to turn not the entire current rectangle into a portal, but a part of it (that is, everything except the right column). This part is highlighted in red in the illustration.
That is, we count how many actions it will take to turn the red part of the rectangle into the corresponding part of the portal, if this number of actions exceeds the answer found earlier, we break, otherwise we add the number of actions it will take to turn the green part of the rectangle into the corresponding part of the portal and only now we recalculate the answer.
Let x(i, j, h, w) be the required number of actions to turn the red part of the rectangle (i, j, h, w) into the corresponding part of the portal, and y(i, j, h, w) — to turn the entire rectangle into a portal. Then x(i, j, h, w) <= y(i, j, h, w) <= x (i, j, h, w + d), so the solution works correctly.
I read the Editorial and our solution is indeed bruteforce even though it gives amortized complexity same as the intended solution. I agree with people being mad. It seems way harder to be a D2C now. I apologise.
I'm just wondering — what is the point of contribution rating? "It is very sad to see interlude at the bottom of the user rating by contribution", why is it that sad? Maybe he/she doesn't even care
I think that often it's the coordinator and testers who deserve the downvotes. The author invents problems, writes statements, prepares tests. Testers should check statements (including explanations of samples) and give feedback on problem difficulty (which is very difficult to estimate for the author himself). The coordinator should be experienced at dealing with constraints and IMO it's his fault that $$$n \leq 100$$$ was used with $$$O(N^5)$$$.
Though, the authors deserve a downvote for not including any test in div1A where the optimal rectangle is bigger than 20x20. And I hope that everybody stops choosing TL and constraints "to make the intended solution pass" and instead the goal should be "to make the slow solutions fail". Well, best consider both and choose the geometric average of running times.
Regarding weak pretests, I fail to see how hacks can't solve that.
It's sad actually how the useful and interesting part of contest format is neglected because of the strange popular opinion, to the point that authors feel it right to add pretests during the contest.
I didn't say anything about pretests. Tests were weak and authors shouldn't rely on hacks that much.
Yeah sorry, I misread "tests" as "pretests". Still, the point stands: if hacks were encouraged by the current meta, instead of being shunned to ridiculous depths, pretesting would be essentially helped by hacks, and the problem's final tests would end up being just fine.
because people r desperate for rating.just because tourist is number 1 doesnt mean hes the best.the inability to solve make people hate the problem.typical cp-er
The problems A-C were to me "ok I know what to do, gotta beat my implementation like a redheaded stepchild till it gives AC". They weren't bad, I'm fine with the contest and wouldn't downvote it, but they just weren't very exciting — in retrospect trying to find a nice solution to either of them, rather than relying on my knowledge of optimisation, would've given me a worse score.
"what are you doing, stepchild?"
Even though I got a good rank, I think they probably deserve that. Here are some reasons. (From a div-2 contestant point of view).
I downvoted the blog when the author said that O(n*sqrt(n)*log(n)) can pass E and the intended complexity for D is O(n^5).
I am not down vote the contest but I'm pressing because the problem C div 2 have announcement but doesn't update in problem. So I think the corners must have value :(((
I hope you understand this comment
Sorry if my english not good :(
Who cares about contribution?
TBH, I think this is very unfair to the problemssetters. They spend lots of time to prepare for a contest, to creat clear statements, correct solutions, validators and generators. The creator may not have enough experience to set proper time limits, prepare strong pretests and adjust the difficulty of the contest, but they are definitely contributing to the community.
It's not easy to prepare for a contest, so try to be more tolerant of others. If you spend months preparing for a contest, and all you get is negative feedbacks and downvotes, do you want to make a contest again? It's fine to point out the mistakes of the contest, but should such a contest really be downvoted to -1200?