I won't talk about the result of the round or cheaters, but about the statements
B, D, E, and G are obviously constructive algorithms problems
Is it a little bit odd to have half of the problems being constructive algorithms problems? (Sorry for my bad English btw)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
agree, especially problem E with a bunch of if else,it's a bit weird
Yeah, after the observation about F(t) we have a bunch of if/elses.
If you thought today had too much constructive check out Global Round 9.
I didn't say that this contest is the only one with the "1-tag" problem. There are some other "math forces", "DP-forces", "greedy-forces" and "constructive-forces" contests.
Also, I agree that GR9 is just a bunch of constructive algorithm problems.
Most of the problems now are about CA. You can find a whole DIV.2 just constructive algorithms problems!
I agree. Nowadays almost 90% of the problems till div2D are just stupid greedy or constructive. I know a CM who doesnt know bfs :(
I know one who does. What's the big deal. I think that after that level of Problem Solving maturity he/she would take a lot less time to master bfs than, say, a complete newbie leaning bfs.
My motive is not to highlight bfs, but rather trying to say that in recent problem trends, one doesnt need to know the very basic standard algos to reach a good rank which was not possible 2 years back.
E is not constructive imo.
"Find the lexicographically minimal string..." doesn't ask you to construct anything.
So what did you do to solve that problem? You can't say something like "Since the statement doesn't contain the word 'construct', I'll confidently say that the problem has nothing to do with constructive algorithms". I respect your opinion, but imo you should come up with a better argument.
I did a lot of casework.
However, the problem has a unique solution, so I think it's closer to "find the answer" than to "construct an answer".
Other examples:
Your examples require some other things
check if two segments in a 2D plane intersect requires geometry
find the length of the shortest path between nodes 1 and n requires graph knowledge
So you can say that the problem is about geometry or graph, which is completely fine
However, the solution for E yesterday requires nothing else to do the problem.
Also, You don't do anything to find the answer, you just if/else and print it out.
the solution for E yesterday requires nothing else to do the problem
so the problem is ad-hoc, but it's not necessarily constructive.
"Also, You don't do anything to find the answer, you just if/else and print it out."
So it is not about finding the answer but constructing one
Why so? For literally all problems, you can claim that you are constructing an answer and then printing it out. What is the difference between finding an answer and constructing an answer?
It is different because E yesterday was about nothing but constructing a string. If it is not constructive algorithms, then what is it?
I would say it's ad-hoc or even greedy.
Okay, I agree that it is ad-hoc or greedy also. But you just can't say that this is not constructive, because in the code, you are just constructing the solution and do nothing else.
IMO, constructing — implementation of construction which you came up by yourself. And finding — implementation of some algorithm, that finds solution, pattern for which you don't know.
Imo "ad-hoc" fits more on your first definition (algorithms that are suitable for this particular problem only)
By "came up by yourself" I mean that you know pattern of answer before you have written any code. Surely not all ad-hoc problems fit that, or we mean different things by ad-hoc...
No, the problem isn't adhoc. Ad-hoc => interesting and the problem wasn't.
I think "print the nodes of the shortest path" can be categorized into constructive because it's like asking you to construct a path that has a special property that is having the smallest distance. But since it is just a classic graph problem and most people are already familiar with this, some people might consider this as just graph problem.
Problem E is also the same. It's like asking you to construct a string t that has 2 properties:
Even though it has a unique answer, I would still consider this problem as constructive.
Consider statement that way: "From given set of letters construct lexicographically minimal string that also minimize prefix-function property.", And I don't know any solution other than implementing optimal construction, do you know one?
"From given set of digits, construct smallest possible number of length 9". Come on, it isn't constructive. Otherwise, all minimization dp problems would become constructive too.
I agree with your example, but DP is DP. Main point was lack of non-constructive solution.
Official problem tags also thinks this is constructive.
BTW, his point about uniqueness of solution makes me less sure that this problem can be called constructive.
Idk what D is about. It just requires nothing, no graph theory, not even casework.
is D a stupid greedy ?
My solution is just based on the fact that after fulfilling as my wishes as possible,permute the unvisted positions in ascending order and if after permuting some positions match their index, just revrse them , just handle case of odd length and case when length=1 separately.
https://codeforces.com/contest/1530/submission/122857075
Thats known as greedy
My solution isn't greedy I don't know what would I call it. Some indexes wanted to gift to a certain another index as per input.. I grouped them.
And then I just took one from each of the group-wise indexes and assigned their wishes.
Now as for the rest I could always assign them to a wish (which is not equal to their value) as long as the size of the remaining unassigned indexes was >=2
The only case where there can be an issue is when the size of unassigned indexes is just 1 and supposing the remaining unassigned index becomes = to the index we need to assign for, then just swap with someone from the wish group it belonged to.
Is the new trend slapping the constructive tag onto everything that is neither data structure, graph, DP nor string?
Just because you are asked to print out the optimal solution doesn't necessarily mean that it is a constructive problem. Do you call a shortest path problem constructive if you're required to print out the minimal lexicographically shortest path?
Sorry, but what problem are you disagreeing about?
That was for E.
G is certainly one and I somewhat agree that D also is although the main part is just about handling the case where $$$b[i] = i$$$. B is more of greedy and you don't really need to come up with any special insight/idea to solve it.
Well, as I have said in the comments above, the problem is nothing much other than constructing the string. Yes, some greedy and the observation about F(t) is needed, but it is still very much a constructive algorithm problem.
There is one more difference too. Constructive and ad-hoc problems usually don't require algorithmic optimizations. If you find any answer or solution, it is most likely already optimal and does not need to be optimized. And I think that is true for problems B, D, E, and G. While for other kinds of problems you usually can very easily propose some non-optimal solution, and then you look for a faster solution.
And of course, this is not always the case, but in my opinion it kinda confirms the opinion of the author about this contest.
in my opinion, A, B, C, D, E was just a hard speedforces-like realization
Absolutely agree with B-E, but as for me, A is pretty good.
A was a copied problem.
From where?
He's right, I definitely recall seeing A sometime in the last few months on Codeforces, although I can't remmeber which contest.
https://leetcode.com/contest/weekly-contest-219/problems/partitioning-into-minimum-number-of-deci-binary-numbers/
Sweat, that took some digging.
It seems that it is common to have some constructive problems in recent Div.2...
We can be happy that there weren't so much math-related problems like 2 or 3 rounds ago...