Stepavly's blog

Codeforces Round #693 (Div. 3)
By Stepavly, history, 4 years ago, translation, In English

Happy New Year, Codeforces!

UPD: We have received such different opinions about the order of problems, that we cannot be completely sure about it. We recommend you to read all the problems and do not strongly hope that the difficulty for you necessarily coincides with the order in the round.

<almost-copy-pasted-part>

Hello! Codeforces Round #693 (Div. 3) will start at Jan/04/2021 17:35 (Moscow time). You will be offered 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially. The round will be hosted by rules of educational rounds (extended ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. We tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 7 problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

The problems for this round were invented by MikeMirzayanov and prepared by Supermagzzz and Stepavly

Thanks to MikeMirzayanov for platforms and coordination of our work. Thanks to darkkcyan, Aris, Mukundan314, PrideBlack, Nemo, pashka, Rox for help in round preparation and testing the round.

Good luck!

</almost-copy-pasted-part>

UPD: Editorial

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

Comments Comments (142)
| Write comment?
»
4 years ago, # |
  Vote: I like it +83 Vote: I do not like it

Is this the first Div. 3 contest announcement by a "newbie"?

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

New Year Magic -- Newbie arrange a contest for LGM....xD.

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

Seems no tester will ask to give him contribution for this contest.

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

No Hello 2021 this time?

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

    Very Unlikely as first contest is hello and is not scheduled yet and a div3 after 2 days which makes it nearly impossible.

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

    This round will be in New Year's style. This isn't Hello 2021, but we hope you will enjoy it!

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

      New Year is celebrating the fact that the earth orbited the sun an integer number of times since an arbitrary day...

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

Missing vovuh

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

Happy New Year Codeforces! <3

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

Thanks a lot to Supermagzzz and Stepavly for preparing the div. 3rd competition.

→ Reply
»
4 years ago, # |
  Vote: I like it -62 Vote: I do not like it

As a LGM, Give me some contribution!!.

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

pog

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

Div 3 will flood LGM xDDDD

→ Reply
»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it
meme
→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

this blog proves that upvotes are given on the basis of rating mainly!

blog was written 92 minutes ago and still only 63 upvotes xD

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

If I change my rank to Pupil can I participate?

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

Count of LGMS participating officially in Div3 will be more than that of pupils and newbies xd

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

Why is only one Div 3 conducted in a month? I feel for beginners at least 2-3 Div. 3 Should be conducted for Practice. [Just a Suggestions]..

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

    do them

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

    It's not easy to make Div 3's. Problems should be interesting as well as beginner friendly. If you want more beginner friendly contests, do all ABC's.

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

      I tried solving ABC's but it's hard to find Editorials of past Contests since mostly they are written in Japanese. For Recent Contests, it's available, even If I try asking here on CF instead of helping me people just downvote me. That's why I was asking for a few more Div 3. Since 4-5 Div. 2 are also happening every month and their Questions are also Unique in the same way at least 2 Div. 3 Should also be conducted for Practice. because Editorials are available and more number of People Give Codeforces Contests so It's easy to discuss with them after the contest.

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

        ABC blog comments are more than enough to understand and solve all problems. Don't put in your own comment if it's not a genuine query. There are multiple comments explaining all problem solutions already. Also dont ask people to debug. figure it out on your own. you won't be downvoted otherwise. as for Div2's, they are prepared by various authors. but Div3's are only prepared by a handful of people and that is not likely to change.

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

Meow hopes that he gets some positive delta this contest :3

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

    +50 delta for everyone who participates... lol!!

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

wow 7 problems on a div3, this is gonna be interesting :))

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

As an expert, give me contribution

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

will we have any extra rating rise as a new year gift? jk XD !!

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

Codeforces Please fix the problem of rendering as

Unable to parse markup [type=CF_MATHJAX]

$

Unable to parse markup [type=CF_MATHJAX]

instead of real data in Questions after update or maintenance you made today between 0:05 to 4:05. All question are showing

Unable to parse markup [type=CF_MATHJAX]

$$$$ instead of data .

→ Reply
»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it

is this contest rated for me?

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

For a moment, I was like "oh my god did vovuh changed his handle..." and then I saw vovuh on the top contributor list. sigh of relief...

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

Hoping for less plagiarism this year cheers!

→ Reply
»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Happy New the Contest !! 1st contest of 2021 is for the the beginners of the programming world

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

I love it when div 3 contests are unrated for me. I wait for the day when I could say the same for div. 2 contests :)

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

As a tester, please give me the problem setters contributions. They have done a great job preparing fun, yet challenging problems! I highly recommend reading all problems ;)

→ Reply
»
4 years ago, # |
  Vote: I like it -27 Vote: I do not like it

as a grandmaster, I won't participate in this contest . . . so Newbies can improve their rankings (lmao . . . happy new year)

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

this contest will be div 3 so does this means there will be more cheating in this contest than the previous one, are measures taken regarding plagiarism?

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

First contest of the year! And first ever unrated official contest for me!

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

For anyone interested, I'll be doing a post-contest stream on Twitch.

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

    Hey man! Any reason for choosing Twitch over YouTube?

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

      My impression is that Twitch is "streaming-first", but I don't really know haha, I just picked one. I do upload all my past broadcasts to my YouTube, though, if you'd like to watch there.

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

Since almost half of the players are cheaters in almost every cf/cc contest as it is revealed. so if you feel sad due to poor performance then be happy with your performance as you are not the cheater and assuming you original rank as current rank/2 xd.

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

2021 be like: Newbie makes div3 for Legendary Grossmaster. 

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

can i take part in thí contest ?? i'm newbie.

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

    Yes, everyone with a rating less than 1600 can take part in DIV3 contests

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

Tomorrow is my birthday. I will try to be green on the basis of the results of Codeforces Round #693(Div3) .

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

everyone has dream to become Legendary Grandmaster

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

Anyone from react-native background here?

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

Hello guys happy new year. New Year new me and now i am PUPIL so for the new year resolution i will no longer post troll comments and will become red coder in 2021.

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

Message the from writers: We have received such different opinions about the order of problems, that we cannot be completely sure about it. We recommend you to read all the problems and do not strongly hope that the difficulty for you necessarily coincides with the order in the round.

Сообщение от авторов: Мы получили настолько противоречивые мнения о порядке задач, что не можем быть полностью уверенными в нём. Рекомендуем прочитать все задачи и не сильно надеяться, что сложность лично для вас обязательно совпадёт с порядком в раунде.

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

The best way to do good in DIV 3 is to think like DIV 3..

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

What happened to Hello 2021?

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

Such a nice contest with excellent problems!

Though problems where a bit on the easy side.

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

Enjoyed it

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

(AFTER CONTEST) How to solve E? I tried Binary Search but it had some problem, maybe implementation,I don't Know.

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

    Binary Search + Segment Tree (My solution is probably overkill)

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

    I sorted the input by pair<height,width> . For first case where $$$h_j<h_i$$$ and $$$w_j<w_i$$$ , we can traverse the array and keep track of person with smallest width for height less than $$$h_i$$$.

    For the other case , we can take $$$h_i = w_i-1$$$ , $$$w_i = h_i-1$$$ and we can solve it similar to above.

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

      I had same approach. Some implementation problem must be there.

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

        your code is giving TLE on my computer on test 1 2 10 2 1 9 .You can use that to debug .

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

      I sorted by pair<min(height, width), max(height, width)> because basically width and height could be exchanged as per the problem. Made the implementation very easy

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

    E has some serious implementation complexity.

    Let's say we first consider the case of both in same orientation (both standing or both lying on the side).
    Just sort the array of pairs(height, width) by height.
    Now, suppose you want to find the answer for ith index.
    Then find the last index say j before i such that height of j is < height[i].first (c++ array of pairs). If there exists such a j then its possible range will be [0, i-1].
    Also, keep another array of minw of pairs which will contain minimum width of the sorted height array till ith index and the index of the minimum width found.
    Now, the answer will be minw[j].second.
    Another implementation detail. You need to keep the original indices preserved somehow since those will be changed when you will sort.

    Now, do this again with different orientation.

    I could come up with this only and it works fine but it is too heavy on implementation.

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

      You can solve E with 1 Fenwick Tree easily

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

      For every entry, keep three things : 1. x: min(height, width), 2. y: max(height, width), 3. z: original index. Now sort them with x and start from left, when you go to right, you are guaranteed that the x will only be increasing so you can always get lesser x in left, to find the lesser y, keep track of the lowest y you have seen so far. If current y is greater than the lowest you've seen so far, then its impossible case.

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

    sorting + one variable to hold current minima

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

What is test 2 of Problem E?

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

    Sorry for being rude. I didn't meant that :(

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

      Actually, to the contrary, I think I'm reasonably close, otherwise I wouldn't be asking :)

      This is similar to a problem that I've seen before so it's likely my implementation has a bug.

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

      A person who has been expert in the past can solve most Div.3 E. So, i don't think there is any flex here.

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

      You are not correct. For example my solution for G when i submitted first give WA on test 2 but after i saw my mistake and got AC

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

    Your code is failing on following test : 1

    2

    10 2

    1 9

    output should be 2 -1 whereas your code gives -1 -1 . Infact i had very silly implementation mistake due to which i was failing in same test . I Fixed that error during contest .

    Also Ozymandias_Orz please don't spam comment section by being rude to others (especially to those who are asking genuine help)

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

      Appreciate this. I see what my bug is — I should've rotated my height and width in cases where height > width, and then sorted. I believe the rest of my implementation is likely ok, so this was my oversight.

      [Edit] Yup, that was it. Passed sys tests with this change.

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

Problem D reminded me of Leetcode — Stone Game VI

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

I am kind of a noob to this so go easy, and this was my first legit competition, but for the time limit it says 2s and when I submitted I got a time limit error and it said it took 2000ms? Does Codeforces record your time if it goes over the limit?

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

    No, it shows the time as the max allowed time and shows TLE verdict.

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

    No when you exceed the limit program stops and terminates TLE

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

How to solve B?

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

    say you have cnt_1 1s and cnt_2 2s. pick x 1s (out of cnt_1) and pick y 2s (out of cnt_2). If there is some combination such that x + y * 2 == (cnt_1 - x) + (cnt_2 - y) * 2, then you can distribute candies in a way that both Alice and Bob have equal total weight.

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

    Its Subset sum problem(DP). Although , People solved it greedily too.

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

      Dynamic Programming for div3 B?

      It's just two if statements after counting no of one and twos

      103202827

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

Problem E was simple Fenwick Tree implementation

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

Can Someone Explain, How to solve E using Fenwick Tree ????

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

Is rank predictor broken?

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

IMO problem F is really cool, at-least for me, cuz I solved it using $$$DP$$$ and compressing the $$$2 \times n$$$ grid: an even distance between two blocks is equivalent to them being adjacent, and an odd distance is equivalent to them being 1 apart.

103308145

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

https://codeforces.net/contest/1472/submission/103249540 What's wrong in this? Pls look it..

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

    check your code test details. in this case,

    5

    2 1 1 1 1

    is not working properly.

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

Can someone please explain the approach for B (non DP approach)?

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

    Let there be x number of 1's and y number of 2's in the original array. The total sum would then be total = x + 2*y. If total is odd then there is no way of diving the array into two subsets with equal sums.

    Else if total is even there are two cases:

    1. If (total/2 is odd) you definitely need one 1's in both subsets to make their sum odd. So if there are no 1's in the original array, it can't be divided.

    2. If total/2 is even you can always divide it

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

In problem E, can {$$$h_i,w_i$$$} be equal to {$$$h_j,w_j$$$} for two different $$$i$$$ and $$$j$$$?

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

    Yes,it is possible

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

    I think yes, they can be equal. I mean, why not?

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

      Can you please help me with this WA?

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

        Not sure what you are trying to do there, it is hard to understand.

        However, I think you cannot ignore that h and w can be swapped. One simple way to do this is swap all pairs so that h>=w.

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

          But, if the method is correct, it should pass even of I don't swap pairs as you mentioned.

          But that's okay, I will try debugging again. It actually went too late night yesterday, so I was unable to debug `=D.

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

Please take a look at user ImTheBest004. Based on the time the account was created and the submissions made by the user during the contest, it seems to be an alt. Thanks.

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

My solution to E:

Clearly, we can rotate any friend in the input, and the answer remains the same. Suppose we rotated all of them to be wide-and-short. Then we can remove the ability to rotate friends while taking pictures, and the answer remains the same. Proof: if X is narrow-and-tall and can stand in front of Y who is wide-and-short, X can be rotated and still stand in front of Y.

Hence, we rotate all friends to wide-and-short and then remove the ability to rotate them any further. The constraint for X to stand in front of Y becomes: 1) X has width strictly lesser than Y, and 2) X has height strictly lesser than Y.

Consider sorting the friends by width and then answering queries in this order; when considering a certain friend X, define the set of candidates to be the set of other friends which satisfies constraint (1). Note that the set of candidates for X is a subset of friends we've considered before X, and the set of candidates increases as we answer more and more queries. Among the candidates, it suffices to check the one with minimum height.

My solution to F:

If there are any two blocked cells in the same column, we can split the squares at that column, and consider the left and right subproblems. Hence it suffices to solve the case where each cell has distinct columns.

For there to be a solution, the number of blocked has to be even. Also, if you colour each cell black and white like in a chessboard, for there to be a solution, the number of blocked black cells must be equal to the number of blocked white cells. If you sort the blocked cells by column number, it turns out that there is a solution IFF every adjacent pair of cells has opposite colours.

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

I have a question, for question E. At first, I thought the topic was asking how many people can be before the number i, so I searched the Internet for how to get a numerical ranking in the set. Unfortunately, I searched for a long time and only found a function called distance. (I didn't know its complexity was O(n) at the time, I only knew it after the game). Fortunately, the sample data reminds me that I read the wrong question. But I have a question, that is, if the question is to ask for how many people can be before the number i, can it be solved with set? Or must other methods be used? If I have to use other methods, is there any sample code and teach me how to do it? I hope that the kind people will answer this question for me, thanks in advance.

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

    You can sort the people by h, and maintain a multiset of all w values. Then loop throug all people.

    In the loop first remove the current persons w from the multiset. Then find for the current person the number of persons with smaller w by binary search on the multiset. The multiset is sorted by w, so the number of smaller/bigger entries can be calculated once we know the position of the "next" bigger one. see function upper_bound().

    I implemented the problem this way, in spite on not needing the count, but only one random one. 103306560

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

      I don’t quite understand what you mean, there is such a line in your code auto it=f.upper_bound({get<1>(a[i]), n}); It stores only the iterator pointed to by an element. But the distance between it and f.begin() still needs to be obtained through the distance function? But unfortunately, the time complexity of the distance function is O(n). Or do I not fully understand what you mean? In addition, I think this problem does not need to use mulset, a set is enough to solve. Just store the value*1000000+number in the set (you can see the code I submitted during the competition), I don’t like to use mulset very much, so if I don’t need it, I try not to use it^__^

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

        You are right, I assumed distance() would work in O(1).

        However, the principle works. For example we can compress the h and w values, then use a segment- or fenwick tree instead of the multiset.

        The principle is that we maintain the set of elements which are to be considered in one dimension in a structure that allows us to query the other dimension.

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

When I see my rank in the standings table, it is 178 but in friends standing, it is 240. Can anybody explain the reason for this? Thanks in advance!

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

    First tell me Why are u cheating

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

    the lion, the witch, and the audacity of this..

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

      Solution for E :Just for a particular hi, check whether there exists a smaller w among the all h smaller than hi and similarly among the reverse pair, check whether smaller h exists for smaller ws. This can be done storing the minimum among them. I used coordinate compression to achieve this.

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

        Can you point whats wrong in this code?

        It got accepted on "PRETESTS" If we remove if(a.w>A[0]. w)break;

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

Hi. Can you help me find out what my problem is? I get wrong answer on test 2986 My Code:. It is about problem E. Thanks!

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

Testing on hacks completed or not?

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

    done, but the change in ratings will take some time to appear.

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

I'm upset coz of weak pre-tests in problem A however, thank you for the good problems statement,,

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

Can someone explain why 6->2->5->1 isn't a valid path for the first testcase of the sample input for problem G?

→ Reply