minhcool's blog

Some thoughts about round #733
By minhcool, history, 3 years ago, In English

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)

  • Vote: I like it
  • +137
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +35 Vote: I do not like it

agree, especially problem E with a bunch of if else,it's a bit weird

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Yeah, after the observation about F(t) we have a bunch of if/elses.

    → Reply
»
3 years ago, # |
  Vote: I like it +79 Vote: I do not like it

If you thought today had too much constructive check out Global Round 9.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Most of the problems now are about CA. You can find a whole DIV.2 just constructive algorithms problems!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    I agree. Nowadays almost 90% of the problems till div2D are just stupid greedy or constructive. I know a CM who doesnt know bfs :(

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +47 Vote: I do not like it

        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.

        → Reply
»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

E is not constructive imo.
"Find the lexicographically minimal string..." doesn't ask you to construct anything.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +49 Vote: I do not like it

      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:

      • "check if two segments in a 2D plane intersect" requires casework, but it's not constructive
      • "find the length of the shortest path between nodes $$$1$$$ and $$$n$$$" isn't constructive, "print the nodes of the shortest path" doesn't make the problem constructive
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -15 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          the solution for E yesterday requires nothing else to do the problem
          so the problem is ad-hoc, but it's not necessarily constructive.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            "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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it +18 Vote: I do not like it

              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?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it -14 Vote: I do not like it

                It is different because E yesterday was about nothing but constructing a string. If it is not constructive algorithms, then what is it?

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                    Vote: I like it +9 Vote: I do not like it

                  I would say it's ad-hoc or even greedy.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                    Vote: I like it -22 Vote: I do not like it

                  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.

                  → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Imo "ad-hoc" fits more on your first definition (algorithms that are suitable for this particular problem only)

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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...

                  → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it -44 Vote: I do not like it

            No, the problem isn't adhoc. Ad-hoc => interesting and the problem wasn't.

            → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        "find the length of the shortest path between nodes 1 and n" isn't constructive, "print the nodes of the shortest path" doesn't make the problem constructive

        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:

        • The value of f(t) must be minimized.
        • The string t is the lexicographically smallest.

        Even though it has a unique answer, I would still consider this problem as constructive.

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +85 Vote: I do not like it

      "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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -19 Vote: I do not like it

        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.

        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

Idk what D is about. It just requires nothing, no graph theory, not even casework.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    is D a stupid greedy ?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        fulfilling as my wishes as possible

        Thats known as greedy

        → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
  Vote: I like it +92 Vote: I do not like it

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?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Sorry, but what problem are you disagreeing about?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like 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.

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

in my opinion, A, B, C, D, E was just a hard speedforces-like realization

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems that it is common to have some constructive problems in recent Div.2...

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

We can be happy that there weren't so much math-related problems like 2 or 3 rounds ago...

→ Reply