DeMen100ns's blog

By DeMen100ns, history, 2 weeks 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
  • +269
  • Vote: I do not like it

»
10 days ago, # |
  Vote: I like it +1 Vote: I do not like it

so quick ^_^

»
10 days ago, # |
  Vote: I like it -10 Vote: I do not like it

Super fast editorial.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Very quick editorial! thank you!

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

so fast

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

so quick,Thank you

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone got stuck on pretest 2 B? Or am i the only one:(

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

    me too

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    me too,Steve .

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    me 2

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got stuck too, but then I tried random graphs like input where I found this, n=10,1 1 1 2 2 3 2 2 3.

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i got the right idea but it wasn’t complete, instead of using max prefix and suffix array, i just compare a[i] to min(a[i-1], a[i+1]) for the whole array (except the first and the last element) so that’s why i didn’t got AC:(

      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        tf is your dp

        • »
          »
          »
          »
          »
          9 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          do you mean dynamic programming? if so i didnt use any dp at all, heres my submission if you wanna check out, i only loop through the array and make simple checks :')

      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i corrected it by noting the slop

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Super fast editorial

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for fast editorial, I really enjoyed the contest!

»
10 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Way more balanced than the last contest.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

wow editorial came faster than system testing thanks

»
10 days ago, # |
  Vote: I like it +39 Vote: I do not like it

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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Fast editorial!Thank you!

»
10 days 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!

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    really? it's the first time you're seeing an interactive problem that isn't a binary search problem?

  • »
    »
    9 days 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...

    • »
      »
      »
      9 days 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.

      • »
        »
        »
        »
        9 days 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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

speed++

»
10 days 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.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 days 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.

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

These editorials get uploaded faster than my rating drops

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Fastest ever seen ~ Appreciate !

»
10 days 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

»
10 days ago, # |
  Vote: I like it +1 Vote: I do not like it

fast solutions , a good round xd

»
10 days 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!

»
10 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Thx for the fast tutorial.:)

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 days 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.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is 2 queries, not 3.

    • »
      »
      »
      10 days 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

    • »
      »
      »
      10 days 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

      • »
        »
        »
        »
        10 days 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

  • »
    »
    10 days 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.

»
10 days 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 :)

»
10 days 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

»
10 days 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.

  • »
    »
    10 days 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

  • »
    »
    10 days 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).

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can try this : 5 2 2 2 2 5

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    5 2 2 3

  • »
    »
    10 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    loop is from i = 1 to i = n-2. Basically, my idea was, that if there is a valley we can improve the result. PS: My bad, faulty implementation.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

7 days ago!!!

  • »
    »
    10 days 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...

»
10 days 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!

»
10 days 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.

»
10 days 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

»
10 days 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)

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      10 days 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.

      • »
        »
        »
        »
        10 days 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?

        • »
          »
          »
          »
          »
          10 days 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

»
10 days ago, # |
  Vote: I like it +6 Vote: I do not like it

lol 7 days ago :))

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

so fast editorial! Thank you

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for the fast editorial ^_^ Waiting for the system testing to start.

»
10 days 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)?

»
10 days ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
10 days 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

  • »
    »
    10 days 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

    • »
      »
      »
      10 days 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.

  • »
    »
    10 days 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.

»
10 days ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
10 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

D is such a genius problem orz orz orz orz orz

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

This is how early all contest tutorials should be uploaded.

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

[Deleted]

  • »
    »
    10 days 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?

    • »
      »
      »
      10 days 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

»
10 days 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
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Your are faster than me ;)

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

Problem D is so good!

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing speed for editorial,thank you so much.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 days 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

»
10 days 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).

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

here are the video Solutions for A-D.

»
10 days ago, # |
  Vote: I like it +13 Vote: I do not like it

A-E video Editorial for Chinese:

Bilibili

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

After, reading the editorial for D, Hell yeah, it's kind of an observational problem and interesting as well. I wasted most of the time thinking of doing some kind of binary search, {i had a bad habit of relating every interactive problem with binary search LOL}.

»
10 days 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:

  • »
    »
    10 days 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.

    • »
      »
      »
      10 days 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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

alot of mathematical problems

»
10 days 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..

»
10 days 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.

  • »
    »
    10 days 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

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think problem C can be solved by more elegant way of filling in numbers. Your text to link here...

  • »
    »
    9 days 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)

»
10 days 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?

  • »
    »
    9 days 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).

»
10 days 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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does the hint in 1713D - Отсчет турнира say that

Problem D Hint 1 Spoilers
  • »
    »
    9 days 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.

»
10 days 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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

cool problems had fun while solving

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Without recursion solution of problem C

Solution

167326787

»
10 days ago, # |
  Vote: I like it -32 Vote: I do not like it

all those hints and spoliers make it hard to read

  • »
    »
    10 days 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.

»
10 days 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.

  • »
    »
    9 days 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]$$$.

    • »
      »
      »
      9 days 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.

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

    I did this as well

    167266697

»
10 days 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.

  • »
    »
    8 days 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...

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think "2-sat" can help.

      • »
        »
        »
        »
        5 days 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!

»
9 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The implemention of E is so clever!

»
9 days ago, # |
  Vote: I like it +11 Vote: I do not like it

your solution for problem F has a WA :D

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

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

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 days 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)

  • »
    »
    9 days 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).

»
9 days 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

  • »
    »
    9 days 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

    • »
      »
      »
      9 days 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):

»
9 days ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
9 days 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).

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it
Spoiler
»
9 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

It got accepted but I don't have proof why it worked ,can anyone help me with proof ?

»
9 days 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!!

  • »
    »
    9 days 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]$$$

    • »
      »
      »
      9 days 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

      • »
        »
        »
        »
        8 days 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 :)

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          ohhh blunder!! Thanks for the reply

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for fast editorial ^_^

»
9 days 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?

  • »
    »
    9 days 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.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Simple Solution to Problem-C :

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is another code for 1713C — Build Permutation

Code
»
9 days 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}$$$

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

thank you for the fast Editorial.

»
9 days 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

»
9 days 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;

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can consider that is a ceil function

  • »
    »
    9 days 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$$$.

»
9 days 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

  • »
    »
    8 days 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.

  • »
    »
    8 days 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

»
9 days 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.

»
9 days ago, # |
  Vote: I like it +1 Vote: I do not like it

There is a typo in hint 1 for problem D.

»
9 days 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.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain the proof why always answer exists for problem c? by taking an example

»
9 days 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

»
9 days 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!

  • »
    »
    9 days 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.

»
9 days 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.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
8 days 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.

»
8 days 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!

  • »
    »
    7 days 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

»
8 days 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?

  • »
    »
    8 days 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 :)

»
8 days 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)

»
8 days ago, # |
  Vote: I like it -11 Vote: I do not like it

Can anyone help me why this solution isn`t acceptable? Approach Used-> If we have to go to any coordinate on any axis then while returning to (0,0) the total number of moves would be 2*max(coordinate-1, coordrinate-2).

include <bits/stdc++.h>

using namespace std;

int main() { int t; cin>>t; while(t--) { int n; cin>>n; int cnt=0; while(n--) { int a,b; cin>>a>>b; a=abs(a); b=abs(b); int k=a+b; cnt+=k; } cout << cnt*2 << endl; } }

»
6 days ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

In problem C when i am using vector<pair<int,set<int>>>v i am getting tle on test case 3 167745306

but , when i am using this vector<pair<int,queue<int>>>v it is getting accepted 167745148

can anyone please explain why ?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This may be because the time complexity of the add, delete, modify, and check operation of set is O(logn), while the time complexity of queue is O(1), I guess

»
6 days ago, # |
Rev. 4   Vote: I like it -10 Vote: I do not like it

codeforces round 812! (problem E)

  • diagonal elements are to be untouched as they play no role in swap.

  • Every non diagonal element can have two relative positions A[i][j] and A[j][i] only if A[i][j]!= A[j][i].

  • Then for certain k ( 1<=k<=n) row can be swapped with it's corresponding column to make matrix lexicographically smallest. Here( for upper half of diagonal) we have to choose some i where i<j and check if A[i][j]> A[j][i] or A[i][j]< A[j][i]. Then why is it we require DSU .Here initially DSU represents k different sets where each number ( 1<=k<=n) is it's own parent.

  • Then through union and find operations the set's have to be segregated into two forms that the operation can be performed for kth node or not.

  • ( find using path compression optimization. This concept can be find here
int n;
int arr[2000],p[1000];
int find(int u){
  if(u==p[u])return u;
  return p[u]=find(p[u]);
}
//simple union 
void Union(int a,int b){
  a=find(a);
  b=find(b);
  if(a!=b)
      p[a]=b;
}

void solve(){
   cin>>n;
   int mat[n][n];
   //matrix input
   for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin>>mat[i][j];
    }
   }
   /* let's consider 2n nodes , where first half of the nodes 
      depict the group that have same states whereas another group depicts 
      elements to have different states. 
       example matrix
         0 1 2 3
       0  a b c d
       1  e f g h
       2  i j k l
       3  m n o p

        suppose we compare for b and e , and b>e then we have two options either to do operation for
        k=0 or k=1. so we put (0 + n )and (1) in same group and (1 + n ) and 0 in same group.
        Here one more condition can occur if b<e then we put 0 and 1 in same group ( why? because if we perform k=0 operation 
        and k=1 operation then it does not affect the b's positon).therefore  i+n and j+n is done and i union j is done.

   */
   for(int i=0;i<2*n;i++)
    p[i]=i;
   /* Now to be lexicographically smallest matrix 
   we counter with those elements which are upper half of the diagonal of 
   the matrix*/

   for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      if(mat[i][j]<mat[j][i]){
      /*if previously it was calculated that i and j  have to be in different 
      groups so be dont mind it because we have to find lexicographically smaller one*/
        if(find(i)==find(j+n)||find(i+n)==find(j)){
           continue;
        }
        else{
          /*otherwise just form same groups*/
           Union(i,j);
           Union(i+n,j+n);
        }
      }
      else if(mat[i][j]>mat[j][i]){
        /*if they are already in same groups don't dipatch them as already it is 
        leading to answer*/
        if(find(i)==find(j)||find(i+n)==find(j+n))
          continue;
        else{
          /*if not then form groups */
          Union(i+n,j);
          Union(i,j+n);
        }
      }
    }
   }
   /* remember diagnol elements doesn't change */

 for(int i=0;i<n;i++){
  for(int j=i+1;j<n;j++){
    /*if i and j+n and j and i+n belong to same group  then just swap relative 
    elements*/
   if(find(i)==find(j+n)&&find(j)==find(i+n)){
    swap(mat[i][j],mat[j][i]);
   }
  }
 }  
 for(int i=0;i<n;i++){
  for(int j=0;j<n;j++){
    cout<<mat[i][j]<<" "; 
  }
  cout<<endl;
 }
}
int main() {
  int t;
 cin>>t;
  while(t--)
  solve();
}
»
6 days 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.

  • »
    »
    6 days 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.

    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much. You've helped me a lot. I always make mistakes in details,haha:)

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What does it mean by "fill the three dots with (0,0)"?

»
3 days ago, # |
  Vote: I like it +5 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).

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Naive solution for problem C(almost TLE lol) 168047272