DeMen100ns's blog

By DeMen100ns, history, 20 months ago, In English
Before the round starts

1713A - Traveling Salesman Problem

Hint 1
Hint 2
Tutorial
Solution
Feedback

1713B - Optimal Reduction

Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback

1713C - Build Permutation

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Solution
Feedback

1713D - Tournament Coundown

Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback

1713E - Cross Swapping

Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback

1713F - Lost Array

Hint 0
Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback
  • Vote: I like it
  • +279
  • Vote: I do not like it

| Write comment?
»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

so quick ^_^

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very quick editorial! thank you!

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

so fast

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Super fast editorial

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for fast editorial, I really enjoyed the contest!

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Way more balanced than the last contest.

»
20 months ago, # |
  Vote: I like it +39 Vote: I do not like it

I think problem D has the I/O time issue.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Fast editorial!Thank you!

»
20 months ago, # |
Rev. 2   Vote: I like it +35 Vote: I do not like it

The solution to D is so goated. Just making a simple observation cuts the number of queries just enough so you can pass TC.

First time it wasn't binary search lol. Awesome problem!

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    But I think it is too easy for a div2 D problem,and if it is div2 C,it may be a bit hard and strange...

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      The ratings is a little bit different than expected. We expect C to be 1500, D 1900 and E 2200, but luckily it is still balanced.

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        Yeah C is harder than D imo :p But it is still a really good contest! (Although I didn't find my mistake on problem E till now XD

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

167303250 Why does this fail on time, same logic is used as in the editorial. Thnx for the super fast editorial.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really fast editorial, good organization, thanks a lot;)

»
20 months ago, # |
  Vote: I like it +5 Vote: I do not like it

If the ML for C was 512 mb instead of 256 mb, some fun flow solutions could have passed. What was the point in cutting off O(Nsqrt(N)) Dinic algo solutions? It is not like that's super popular.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I did an overkill, but my MBPM solution passed — 167261911 I have also added library reference in code.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you provide me with good resources to learn MBPM?

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      USACO guide has some good resources for flows

»
20 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

These editorials get uploaded faster than my rating drops

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Question D did not add endl when outputting, which led to debug for a long time. I felt that the input n of the last game did not use cin to set off each other. :C

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

fast solutions , a good round xd

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Successfully get Wrong Answer in Problem C using the right idea,:( It's time for more training!

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Thx for the fast tutorial.:)

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I like this round :) Fast editorial, that's great XD

»
20 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Question: in problem D, if you follow the solution, won't the number of queries be 3/4 2^n, since you divide the number of participants by 4 every 3 queries? I thought of this solution too but discarded it due to this thought.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is 2 queries, not 3.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Oh right, I forgot... I almost got it, but didn't make the second query, only divided it by 2 and got WA

    • »
      »
      »
      20 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I have done D the exact way mention in editorial but the difference was i am taking 2 and 3 participant instead of 1'st and 4'th participant but it gave me WA. Can you please share why only taking 1'st and 4'th participant give AC? here is my solution 167295468

      • »
        »
        »
        »
        20 months ago, # ^ |
        Rev. 3   Vote: I like it +1 Vote: I do not like it

        well you don't have exactly same logic) for example if ans == 1 you suppose that i1 and i2+1 are the winners of their pairs, but is i2+1 always the winner? think of what this might lead to

        hint

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Going with groups of four at each level: you select 2 out of 4 players based on 1 query. And in the end you do one query to pick the winner.

    So 2^(n-2) queries required to remove the first half of the players. Or 1+2^(n-1) total. 1+2^(n+1)/4 is less than the limit in the problem.

»
20 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Thanks for the quick editorial! I really like problem D.

And if I don't get FST, it seems that I can reach Master :)

»
20 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Such a creative way of applying DSU in E! Nice DSU practice problem

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can any tell, for problem B, why the condition if(a[i] < a[i+1] && a[i] < a[i-1])print NO , is insufficient.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For ex in test:

    5 1 1 1 5

    Your condition would say that this array is ok, but in fact we need to do 1 + 4 + 4 = 9 operations here, while we could've sort it like

    1 1 1 5 5

    And we would've need only 5 operations

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The input array can have duplicates (eg [2,1,1,2] is NO).

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

7 days ago!!!

  • »
    »
    20 months ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    We saved it in a draft an only public after contest, like the announcement...

»
20 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

The problem D is so great!I have never seen a so ingenious problem!

»
20 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Problem D is one of my favourite interactive problems of all time!

Small issue in the editorial — I'm unable to open the links to the problems [such as when clicking on 1713F — Lost Array]. It shows access denied.

»
20 months ago, # |
  Vote: I like it +2 Vote: I do not like it

I think D is such a beautiful problem. Thanks for setting this problem hehe

»
20 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem D. You don't need to do the 2nd check on each level, just push two possible winners to the next level. Total queries' count: 2^(n-1)

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it's 2^(n-1)-1 comparisons.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      No, 2^(n-1). The last one is needed to get a winner.

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If n=2 then there are 4 people in the bottom layer, then 2 in the second, then 1. Which means you need 2+1 comparisons (2 in bottom, 1 in second). This would give 2^n — 1. If not, what's wrong with this reasoning?

        • »
          »
          »
          »
          »
          20 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You only need 2 comparisons for n=2 (4 people): 1st query to filter out 2 people, 2nd query to choose out of 2 remaining

»
20 months ago, # |
  Vote: I like it +6 Vote: I do not like it

lol 7 days ago :))

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

so fast editorial! Thank you

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1713/submission/167305017 Getting TLE on D but can't understand why, or this solution's complexity is not O(1<<n)?

»
20 months ago, # |
  Vote: I like it +4 Vote: I do not like it

A great contest :) Problem D is so great!!

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Did my submission for D get WA due to MLE? https://codeforces.com/contest/1713/submission/167297638

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    i guess, its unexpected verdict — your code doesn't fit in the required number of queries, and when your code gets -1 like an answer, it must terminate, otherwise you can get any verdict cause interactor stops to read your output

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the advice! I often get confused with the verdict of the interactive problem.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Take a look at Ticket 15999 from CF Stress for a counter example.

»
20 months ago, # |
  Vote: I like it +13 Vote: I do not like it

I could almost have finished problem E !!! So sad:(

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I like problem D. It's very awesome problem.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D is such a genius problem orz orz orz orz orz

»
20 months ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

[Deleted]

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not really, but std::endl does forcefully flush your output. I think maybe you meant this instead?

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Even without std::endl, it flushes. endl force flushes even with fast io turned on

»
20 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Here's the infamous test case on test 2 on problem D:

3
1 0 2 0 0 1 0 3
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your are faster than me ;)

»
20 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem D is so good!

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing speed for editorial,thank you so much.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why I get wrong answer in E 167313557?

»
20 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem B, isn't it enough to check if the sequence looks similar to a mountain or not? I mean by a mountain that it increases then decreases, or do one of them only (increases only or decreases only).

This is my submission but in no vain I got WA.

https://codeforces.com/contest/1713/submission/167261187

The weird is that my friend's submission effectively does the same but passed the pretests.

https://codeforces.com/contest/1713/submission/167257143

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    When you use return in your if statement, there can still be some values left to input and you're skipping them.

    Here is your corrected solution: 167318731

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by DeMen100ns (previous revision, new revision, compare).

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

here are the video Solutions for A-D.

»
20 months ago, # |
  Vote: I like it +13 Vote: I do not like it

A-E video Editorial for Chinese:

Bilibili

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hi.

I need one help in D. I submitted the same solution with just a small interchange. But I couldn't get why the one that is failing is wrong. Can anyone help?

Wrong Submission: https://codeforces.com/contest/1713/submission/167301158

Correct Submission: https://codeforces.com/contest/1713/submission/167315386

Difference:

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider the case when n = 3, # of wins for each contestant = [0, 1, 0, 3, 1, 0, 2, 0]. After first iteration, the contestants left is [2, 4, 6, 7]. i.e. # of wins = [1, 3, 0, 2]. For your next iteration, you'd compare contestants 2, 6 for your wrong submission, which will result in a wrong solution.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      In more detail: if you make a query about the 1st and 3rd contestant just like in the tutorial:

      If you recieve a 0: that means 2nd and 4th are guaranteed to have won the 1st round and moved on to the next stage.

      If you receive a 1: that means 1st is guaranteed to have won the 1st round and moved on to the next stage, while 2nd and 3rd are guaranteed to have been eliminated at some point (4th is undecided, so we keep them in the array)

      If you receive a 2: that means 3rd is guaranteed to have won the 1st round and moved on to the next stage, while 1st and 4th are guaranteed to have been eliminated at some point (2nd is undecided, so we keep them in the array)

      Because we want to ask about people who actually made it to the current stage, order matters: in case you receive a 2, you should record it as [... 3, 2 ...] so that the next step asks about the 3rd player

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is this giving TLE/ILE for problem D? I have used the same approach as given in the Editorial.My Submission..

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Not able to understand tutorial for problem C can anybody explain with some little example please.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try manually writing solutions for first few numbers, like upto n=10, You will observe a pattern where the last few numbers are constructed such that they a[i]+i becomes equal to the perfect square which is >=(n-1). and the problem gets reduced to a smaller problem where the same pattern is continued. Refer to my solution if it helps. 167261412

  • »
    »
    20 months ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    First, an obvious observation: $$$(a - i) + (b + i) = a + b$$$. Yes, this is obvious and might seem silly, but just keep this in mind.

    Suppose we have $$$n = 11$$$, so the permutation needs to range from $$$0$$$ to $$$10$$$.

    Start with 10. What is the next square we can reach by adding something to 10? Well, the next square is 16, which we get from adding 6, i.e., 10 + 6 = 16. So for index 10, we can place the value 6.

    If the value 6 works for index 10, then the value 7 should work for index 9, because $$$9 + 7 = (10 - 1) + (6 + 1) = 10 + 6 = 16$$$. In fact, we can keep going as follows:

    $$$10 + 6 = 16$$$

    $$$9 + 7 = 16$$$

    $$$8 + 8 = 16$$$

    $$$7 + 9 = 16$$$

    $$$6 + 10 = 16$$$

    At this point, we have mapped indices $$$6$$$ to $$$10$$$ with a permutation of values from $$$6$$$ to $$$10$$$. We are now left with the smaller problem of mapping indices up to $$$5$$$, which we can solve the same way.

    More generally, if your last value $$$L$$$ can reach a square by adding $$$k$$$ (for $$$k \leq L$$$), i.e., if $$$L + k$$$ is a square, then we can assign indices from $$$k$$$ to $$$L$$$ with the values $$$L$$$ decreasing down to $$$k$$$. We can now use $$$k - 1$$$ as our new $$$L$$$ and repeat until we eventually complete the case of $$$k = 0$$$.

    (note that it's always possible to assign a value for index $$$L$$$ because there must be a square in the range $$$[L, 2L]$$$. However, even if you didn't realize this, writing a condition to print -1 if the next square is larger than $$$2L$$$ would still be accepted, since the condition would simply never be satisfied)

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How would A be solved if the boxes weren't limited to the x and y axes?

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I believe the problem becomes NP-hard, even with Euclidean distances and integer coordinates. What this means is that even with coordinates between $$$[-100, 100]$$$, it is believed that the most efficient algorithm would still fail the time constraints. There are some decent approximation algorithms though (only because we're considering Euclidean distances), but an exact answer cannot be found efficiently.

    FYI, the Traveling Salesman Problem is a very famous problem in a class of known difficult problems (NP-complete).

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I really appreciate the effort put into the "Before round starts" section. I wish in the future, more people authors would do it. It was really enjoyable to read and it made me laugh a couple of times

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does the hint in 1713D - Tournament Countdown say that

Problem D Hint 1 Spoilers
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    My guess is that this is a typo that meant to say $$$2^n - 1$$$. The naive approach of checking every matchup would require $$$2^n - 1$$$ queries. Furthermore, if we assume each query as having only two possible outcomes, then an adversary argument would yield a lower bound of $$$2^n - 1$$$. One who is aware of this argument may not have realized that the assumptions do not hold here, e.g., it requires $$$n - 1$$$ comparisons to find the maximum/minimum from $$$n$$$ values, even if the comparisons are three-way, because the adversary can choose numbers such that equality is never returned, but the tournament setting does not provide such a luxury for the adversary (there must be a lot of equalities).

    Anyway, I think the point is that one might naturally try a $$$2^n - 1$$$ solution, thinking that this is the best that could be done, so the hint is to nudge the reader into revisiting their assumptions and realizing that equality is necessary and can be abused.

»
20 months ago, # |
  Vote: I like it +4 Vote: I do not like it

For problem B, i found that any value in the array cannot be less than both its neighbours, otherwise when we decrease the whole array by 1, we will end up with 'holes' and we will have to do more operations to complete the remaining parts.

So i did this : if a[i] < a[i-1] -> the array is decreasing.

if the array is decreasing AND a[i] < a[i+1], print "NO"

It seems simpler to me

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

cool problems had fun while solving

»
20 months ago, # |
  Vote: I like it -32 Vote: I do not like it

all those hints and spoliers make it hard to read

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How comes?

    Hints done right is a nice idea. Hints done the way they're done are not useful, but I fail to see how they can make it hard to read.

»
20 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

I wonder why no one has written about the most intuitive (IMO) way of solving C yet.

Let's generate all perfect squares that is less than $$$2n$$$. Then, iterate from $$$n-1$$$ to $$$0$$$ and for each $$$i$$$, find the largest perfect square $$$x$$$ such that $$${0 \le x - i < n}$$$ and index $$${x - i}$$$ is not used. So our answer for index $$${x - i}$$$ is $$$i$$$;

Total complexity: $$$O{(n\sqrt{n})}$$$.

https://codeforces.com/contest/1713/submission/167282216

I don't know how to prove its correctness though, would be nice if anyone does.

  • »
    »
    20 months ago, # ^ |
    Rev. 6   Vote: I like it +6 Vote: I do not like it

    Suppose you found a position $$$k$$$ such that for the biggest index $$$i$$$ you haven't used (initially $$$i = n - 1$$$) the sum is equal to a perfect square, i.e $$$k + i = pr[j] \iff k = pr[j] - i$$$ for some $$$j$$$.

    Then I argue that for the whole range $$$[k, i]$$$ your code assigns them all to $$$pr[i]$$$ (we will later see why $$$k\leq i$$$ and why we can use all indices and positions in $$$[k,i]$$$). Since in the next iteration index $$$i^{(2)} = i - 1$$$ will get matched with position $$$k^{(2)} = k + 1$$$ (keeping the sum the same), then $$$i^{(3)} = i - 2$$$ with $$$k^{(3)} = k + 2$$$ and continuing... $$$i^{(i-k+1)} = i - (i - k) = k$$$ and $$$k^{(i-k+1)} = k + (i - k) = i$$$.

    So now the problem is identical given as input $$$n' = k - 1$$$. Since we have used all indices in $$$[k,i]$$$ and all positions in $$$[k,i]$$$. What I didn't mention (but was essential for the above proof to work) was that we had used everything $$$>i$$$ (all positions and all indices) and nothing else, which obviously happens in the start and as we saw also happens after the first pile of iterations. Also you are guaranteed to find a perfect square to match with an index because of the property editorial mentions. (for a given $$$x$$$ there is a perfect square $$$y$$$ such that $$$x\leq y\leq 2x$$$)

    Interestingly, that's essentially the editorial's logic but you start searching from the biggest perfect squares, which also means the respective range $$$[k,i]$$$ will be smaller if there are more than 1 perfect square in range $$$[i,2i]$$$.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yeah, both approaches are doing the same thing, except they choose a different square to start filling out the suffixes (in the same manner). One who is able to prove the correctness of the $$$O(n\sqrt{n})$$$ approach would likely also realize that choosing the smallest square that fits the biggest index would be better (since it's also covered by the same proof of correctness), which leads to the editorial solution, which finds the square faster for an overall linear-time complexity.

  • »
    »
    20 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I did this as well

    167266697

»
20 months ago, # |
  Vote: I like it +51 Vote: I do not like it

This is one of my favorite Div. 2 rounds in a long time--the problems felt very elegant, and I particularly enjoyed the process of solving C, D, and F. (I think D took me longer than it possibly should have, but I found it somewhat surprising that the winner could be determined without effectively simulating the tournament, and figuring out how to do so was very satisfying.) The conflict with the TCO Wildcard round was unfortunate, since if I didn't have to leave midway through I think I would have had a solid chance of finishing F, but I very much enjoyed the time I was able to spend participating in the contest, and I'd love to see the authors continue writing problems.

As a bit of constructive criticism, E felt a bit standard to me--the two general ideas (transforming the problem into a graph coloring task and then solving that graph coloring problem using DSU) felt very familiar to me. Overall, though, this is a minor critique, and it didn't seem like the problem was known to too many Div. 2 competitors.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Would you be able to link some problems/resources related to the solution for E? I've never seen this technique before, and searching "graph coloring DSU" didn't lead to anything useful either...

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think "2-sat" can help.

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, you're right! This is basically 2-sat with the implicit graph having all bidirectional edges, so you can use a DSU to check for SCCs. Thanks!

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I think the code of B problem need to use long long.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The implemention of E is so clever!

»
20 months ago, # |
  Vote: I like it +11 Vote: I do not like it

your solution for problem F has a WA :D

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks for report, this is a mistake, i'll fix it now

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great round! E was one of my favorite problems I've seen:)

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

About the solution of problem E. Why if par[i] > 0 then the operation k=i should be performed? (sorry my English is not good)

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Because as I have mentioned in the tutorial, $$$par[u]=p$$$ if $$$2$$$ operations $$$k=u$$$ and $$$k=p$$$ should have the same state. Suppose $$$p$$$ is the root of the $$$ith$$$ component, because $$$par[i] > 0$$$ and we have performed the operation $$$k = p$$$, we should perform the operation $$$k = i$$$ too ($$$2$$$ operations $$$k = p$$$ and $$$k = i$$$ should have the same state).

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help me with the Unsolved mystery. QAQ

I can't understand why my first submit of D can't pass test 3. I loaded the data of test 3 after contest, there is nothing wrong with it, local. What does "wrong answer ? or ! expected (test case 1)" means? I've reconstructed my code using scrolling array in contest, but the logic is nothing differerent, but it passed.

This is my WA3 code durning the contest.

https://codeforces.com/contest/1713/submission/167282903

This is debug code(with output & input).

https://codeforces.com/contest/1713/submission/167344378

This is passed code with scrolling array.

https://codeforces.com/contest/1713/submission/167298523

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in WA3 code, in main function, maybe you forget '!' when output the answer for case a.size()==1

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh you're right. Thanks! so sad, why i can make such mistake):

»
20 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I cannot believe that the two comments are from the same person.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by DeMen100ns (previous revision, new revision, compare).

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it
Spoiler
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution LINK

Applied logic is similar a[i-1]>a[i]<a[i+1] but its getting failed in some edge case. It would be a great help if someone will tell me whats the test case in which it has failed. Thank You!!

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    it is $$$a[i] > a[j] < a[k]$$$ for $$$i < j < k$$$, not $$$a[i-1] > a[i] < a[i+1]$$$

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sorry i made mistake while typing.. when i am using upper_bound in code its doing the work of a[k] if any number is greater than a[j] from the (j+1)th index to the end and i am checking this condition whenever a[j-1]>a[j] because whenever this happens we can check as one bigger value is in left side, if its present then the answer is wrong.

      My intuition was to get atleast one greater number in left side and atleast one greater number in right side

      Thank You for your reply, plz check the code

      • »
        »
        »
        »
        20 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        You can't use upper_bound if the array is not already sorted :)

»
20 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can the solution for B also be implemented using mountain array, i mean if the permutation is a mountain array(including sorted), it will have least number of operations?

  • »
    »
    20 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yup. The requirement for optimality is that the array can be partitioned into a non-decreasing prefix followed immediately by a non-increasing suffix. Either of the two parts can be empty, which leads to the sorted and reverse-sorted array respectively, but having both as non-empty would yield the mountain array.

    The required invariant is that it must always be possible to cover all non-zero elements in a single operation, which means the 0 values only accumulate at the prefix and/or suffix of the array.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is another code for 1713C — Build Permutation

Code
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B can be solved in other way with two steps:

  1. Squeeze an array (remove consecutive equal elements, leave 1)

  2. Check if $$$a_{i-1} > a_i < a_{i+1}$$$

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

guys i need your help! in 1713D — Tournament Coundown my code has no output in test 3 while i check in my vs that the code is work whats worng? https://codeforces.com/contest/1713/submission/167304528

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in the C solution i don't understand this part: int s = sqrt(2*r); s *= s;

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can consider that is a ceil function

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That line means declaring a variable $$$s$$$ which is the largest perfect square number not exceeding $$$2 \times r$$$.

»
20 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

i found another way to solve D in only 2^(n-1) queries:)

first we ask about the players 1 3, we will have 3 Possible answers: 1 : which means 1 won the first game and since 3 can't be the last winner it dosen't matter if he won the first round or not so we will assume that 4 won which means there will be a round where 1vs4

2: same as the above but this will lead to 3vs2

0 : 1 and 3 lost the first round and there will be 2vs4

we do the same from 5 to 2^n and now we removed half the players and we do that again :)

here is the code https://codeforces.com/contest/1713/submission/167278880

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This solution is wrong. Unfortunately our tests were not strong enough to kill it.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I suppose, the below numbers of wins will hack your solution: 2 0 0 1 3 0 1 0 2 0 1 0 4 0 1 0

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I tried them, they does not

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Yeah, you are right. Nice trick on x==2. It does matter!!

        • »
          »
          »
          »
          »
          20 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Thx, i first tried it without it but i got wa so when i changed it it work

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, is there any specific strategy you use when approaching problems like yesterday's C?
I got stuck with an R->L constructive solution, and wasn't able to understand why exactly it was wrong during the contest.

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

There is a typo in hint 1 for problem D.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, my solution for B is giving me runtime error, although if I start debugging everything seems fine. I thank in advance everyone who wants to help.

Good morning!

https://codeforces.com/contest/1713/submission/167403306

btw it says that the error may be on line 35, but it says core dumped after g[p — 1] has reached a size of 4 and i process two queries.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for B was to calculate in O(n), the number of operations needed to make the input array all 0's. If this was equal to the maximum element, then the answer is Yes (the maximum element in the array gives you the minimum number of moves of one of its permutations). Otherwise, the #of operations has to be greater, so the answer is No. To get the number of operations itself, I tried "extending" operations from elements before me. EX: If element i is a 5 and element i-1 is a 7, then I can extend 5 operations from the previous element for free. If element i is a 7 and element i-1 is a 5, however, then I can extend 5 operations from the previous element for free, but I'll need 2 more operations.

167242256

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How dsu is applied in problem E. Can anyone explain me from basics? My mind is completely out of that negative numbers/parent idea. Thanks in advance!

  • »
    »
    20 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    You can see all the elements of the diagonal as nodes in a graph. For each of these elements, you can either leave them in their original position, or "flip" them. Each element of your diagonal has 2 possible states, so your graph will have 2*n nodes (for a n*n matrix).

    Then, the edges between those nodes represents constraints. Consider this matrix:

    3 3 1 2
    1 1 3 1
    3 2 3 2
    2 3 3 1
    

    Here, you would want to swap a[0][1] and a[1][0], So that means you either want k0 flipped, or k1, but not both (k0 being the first diagonal element, and k1 the second). So in your graph, you would have an edge between k0 and k1', AND k1 and k0' (k0' representing the flipped state of k0).

    You would store these relationships using DSU, and only add constraints if ki and ki' would not end up in the same tree, because a node cannot be flipped and 'not flipped' at the same time. Try to draw the graph and the constrains by hand, it helped me understand the problem

    Hope it makes more sense.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot! Now , I understood the approach. This was really a nice question.

»
20 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Optimal reduction( B ) can be done using single iteration over the entire array, and with O(1) space complexity. This solution is too complex.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wait B can be done in O(1)? Elaborate further pls

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      $$$O(1)$$$ space complexity. The best possible time complexity is $$$O(n)$$$.

»
20 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Here is a much simpler way for 1713B — Optimal Reduction

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

long long f(vector<int> a) {
	long long res = a[0];
	for (int i = 1; i < int(a.size()); ++i) {
		res += max(0, a[i] - a[i - 1]);
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt;
	cin >> tt;
	while (tt--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (int i = 0; i < n; ++i) {
			cin >> a[i];
		}
		long long x = f(a);
		long long min_x = *max_element(a.begin(), a.end());
		cout << (x == min_x ? "YES" : "NO") << '\n';
	}
}

First, let's find f(a) and then find that array's minimum f possible permutation. It can be proved that the minimum possible f is equal to the maximum element of the array. (We know that we must have at least x operation (max element). Now we give an example for that -> sort the array in reverse order and then do f on it)

Now we have found the lowest f of permutations of a.

if it's equal to f(a) then all of the other permutations are greater or equal to f(a) and the answer is YES otherwise NO.

»
20 months ago, # |
  Vote: I like it +13 Vote: I do not like it

I've updated the new tutorial for B. The old tutorial is super trash that the idea is simple yet i tried to make everything so complicated.

Sorry for the inconvenience!

  • »
    »
    20 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I wanna share my B solution, I think it can be interesting for someone.

    Let's find the $$$f(a)$$$, it's equal to $$$\lfloor \frac{a_1 + a_n + abs(a_2 - a_1) + abs(a_3 - a_2) + \dots + abs(a_n - a_{n-1})}{2} \rfloor$$$.

    Now we want to $$$f(a) \le f(b) \rightarrow f(a) = min(f(b))$$$. The one way to get minimum $$$f(b)$$$ is sort array $$$a$$$. Now we have to compare $$$f(sorted(a))$$$ and $$$f(a)$$$

    167622000

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried solving E with the hints but got stuck, please help!

Think of the most to the least significant cell of the matrix.

I try to fix cells least first to most significant at last to make it lexicographically smallest.

How many positions in the matrix can a cell travel to after performing the operations?

2

And for each position that that cell can travel to, how many ways are there we can make it?

2 — either swap the column or row

is my above reasoning correct, if yes how can i try 2 ways to swap efficiently?

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you have gone this far and still haven't figured out the answer yet, please read the tutorial :)

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for the great contest and fast editorial (even though my comment isn't so fast)

»
20 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I've tried submitting a solution to problem D ------>167785392 But I get Idleness limit exceeded on test 3, I modified a small part ------>167782691, but it seems to be working Ok, how it works?it confuses me.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When n is even q1.size will never be 2 (eg for 6 on the test case you are failing q1.size will be 64 -> 16 -> 4 -> 1) and the second loop never gets run. As you've moved the print outside the loop in the second version it works.

»
20 months ago, # |
  Vote: I like it +13 Vote: I do not like it

For problem F, very interesting by the way, I get stuck in the last part, when we have array b of size n and want to expand it to b' of size m.

The editorial says: Create array c with sum over supermask, then set zeros the positions [m-n, m) and do sum over supermask again. Why sum over supermasks, and do it two times?

(I understand that sum here means xor).

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain in more details, why solution for F does work? Especially, we want to find such $$$b'_i$$$ for $$$i \in [0, m - n)$$$ that subset sum will have zeros in all elements $$$\in [n, m)$$$. Why operation explained in editorial do that?

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In fact, we can implement DSU in much more brute ways. Since we only need to do up to n-1 join operations, so we could join i and j by brute force over range [1,n]. The total complexity is O(n^2) despite a larger constant factor, it still fits the time limit.

»
14 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

F is the first 2900+ rating problem I've solved (without tutorial). Also in the contest I may not have enough time to deal with it, it's pretty easy for me (as a div2F).

We can solve F by divide and conquer. Calculate brutely to about n=7 and we can find a pattern: Let eq_i is the i-th xor equation we need to solve, then eq_1^eq_2, eq_3^eq_4, ... form a smaller equation system with size n/2, which variable are all even-indexed elements (a2,a4,...) or odd-indexed elements(a1,a3,...) and the pattern of them are completely same with the situation of n/2. Therefore we can solve it first. If n is even, then we get all odd-indexed elements, and all even-indexed equations form another equation system with size n/2, but at this time we solve for even-indexed elements. If n is odd, then we get all even-indexed elements, and all even-indexed equations form a same equation system with size (n-1)/2... but to solve for odd-indexed elements we need it's size to be (n+1)/2. We need to do xor for b_n,n and all a_k where k is even and ((n-k)&(n-1))==0, and add the result to the equations to form an array with size (n+1)/2 and solve it for odd-indexed elements.

Equations for n=7:

#1 a1^a2^a3^a4^a5^a6^a7=b1

#2 a1......^a3......^a5.....^a7=b2

#3 ......a2^a3...........^a6^a7=b3

#4 ............a3................^a7=b4

#5 ................a4^a5^a6^a7=b5

#6 .......................a5....^a7=b6

#7 ...........................a6^a7=b7

if we do #1^#2, #3^#4, #5^#6, we get:

#1' ...a2...^a4...^a6=b1^b2

#2' ...a2...........^a6=b3^b4

#3' .........a4.....^a6=b5^b6

which is same as what we get when solve for n==3.

Also, if we move even_indexed terms of #7 to the right hand side, we get:

#2 a1...^a3...^a5...^a7=b2

#4 ........a3............^a7=b4

#6 ................a5....^a7=b6

#7' .........................a7=b7^a6

which is same as what we get when solve for n==4.

»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem E feels like 2000/2100, A simpler solution(also uses DSU):

Trivial observations:

  1. For all cells with $$$i = j$$$, their position isn't affected by any operation.
  2. $$$A_{i, j}$$$ is only affected by operations with $$$k = i$$$ or $$$k = j$$$.

Let us call $$$op(i)$$$ = Number of operations with $$$k = i$$$.

Now $$$A_{i, j}$$$ gets swapped with $$$A_{j, i}$$$ only if $$$parity(op(i)) \neq parity(op(j))$$$.

We will now maintain dsu sets (elements in them are all the possible choices of $$$k$$$) such that for every dsu set, for any two elements in the set, we know the relation between their parities (equal or not equal).

To generate the lexicographically smallest matrix, we will iterate over cell $$$A_{i, j}$$$ from the most significant cell to the least significant cell, and skip the cell if we already iterated over its mirror cell. Cases:

  1. $$$i$$$ and $$$j$$$ already belong to the same set. We already know the relation between their parities, just swap $$$A_{i, j}$$$ and $$$A_{j, i}$$$ if their parities aren't equal.
  2. $$$A_{i, j}$$$ < $$$A_{j, i}$$$. These should not be swapped in the final matrix, and we can ensure this, as the relation between parity of $$$op(i)$$$ and $$$op(j)$$$ hasn't been defined yet. So just unite the sets of $$$i$$$ and $$$j$$$, such that $$$op(i) = op(j)$$$ is reflected in the union (corresponds to defining the relation between $$$op(i)$$$ and $$$op(j)$$$.
  3. $$$A_{i, j}$$$ > $$$A_{j, i}$$$. Same as the case 2, except that these 2 will be swapped in the final matrix, and we can ensure this. Unite the dsu sets in an appropriate manner.

This is obviously optimal because we iterate from most significant cell to least significant cell.

Implementation: link