Stepavly's blog

By Stepavly, history, 2 weeks 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_244_, 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

»
2 weeks ago, # |
  Vote: I like it +83 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +63 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I literally thought he is a newbie....xD

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      LGM's gonna have hard time solving newbies problem... XD

»
2 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

No Hello 2021 this time?

  • »
    »
    2 weeks 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.

  • »
    »
    2 weeks 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!

    • »
      »
      »
      2 weeks 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...

»
2 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Missing vovuh

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Happy New Year Codeforces! <3

»
2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it -62 Vote: I do not like it

As a LGM, Give me some contribution!!.

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

pog

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Div 3 will flood LGM xDDDD

»
2 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it
meme
»
2 weeks 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

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

If I change my rank to Pupil can I participate?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Coders on "pupil" can also take part in Div 1 !!???

ILLUSION 100

XD

»
2 weeks 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

»
2 weeks 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]..

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    do them

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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.

      • »
        »
        »
        »
        2 weeks 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.

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

    Agreed but if you want to practice more Div 3 like contests you can always go to other platforms such as AtCoder. Easier contests are conducted more frequently there.

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

A VERY GOOD PROBLEM(C) ON CONSTRUCTIVE ALGORITHMS. LINK : https://www.youtube.com/watch?v=lZplaUOpPnk HOPE YOU GUYS WILL ENJOY THIS EXPLANATION VIDEO !!!

»
2 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

As an expert, give me contribution

»
2 weeks 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 !!

»
2 weeks 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 .

»
2 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

is this contest rated for me?

»
2 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

For some time, I thought it's an unofficial announcement.

»
2 weeks 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...

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The first div.3 contest(and also the first contest) of the year! I hope the this contest will have good problems and strong tests. Good luck to everyone in codeforces! XD

»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Hoping for less plagiarism this year cheers!

»
2 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

My first contest as LGM

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope you guys enjoy the first 2021 Codeforces contest. Good luck!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What can be more satisfying than starting 2021 with a Div 3.

Happy New Year Codeforces

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Magic is very good, we can be master for a few days

Thanks to CodeForces

»
2 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

hope to become pupil soon as a Legendary GrandMaster

»
2 weeks 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

»
2 weeks 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 :)

»
2 weeks 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 ;)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

div.3 is more comfortable contest.

»
2 weeks 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)

»
2 weeks 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?

»
2 weeks 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!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think that codeforces will arrange happy new year contest but starting by div 3!!!

»
2 weeks 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.

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

    Hey man! Any reason for choosing Twitch over YouTube?

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

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

        I do watch them on YouTube! You have great content. Twitch has this reward system that does not allow everyone to request problems. Maybe YouTube has it too? Anyway, overtime I will gather points to ask. All the best!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it -33 Vote: I do not like it

What does it mean by this? IMG-20210104-125657
anonymous pictures website

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

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

2021 be like: Newbie makes div3 for Legendary Grossmaster. 

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

Newbie has made div3 for Legendary Grandmaster. lol ;)

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

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

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

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

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

can anyone explain the algorithm of how this rank masquerade thing is working ? is it assigning lower positions to people higher than the position rating or vice versa as well? just asking . xD

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

    I guess everyone is chosing a colour that they have never got/think they can't achieve unless they perform abnormally :P

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

I'm an expert coder!

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

everyone has dream to become Legendary Grandmaster

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

Anyone from react-native background here?

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

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


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

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

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

What happened to Hello 2021?

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

One Piece touched 1000 I want to too. (All hail future pirate king)

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

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

Enjoyed it

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

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

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

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

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

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

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

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

          ya that might be the case as well. but on submitting it showed WA on test 2

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

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

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

      You can solve E with 1 Fenwick Tree easily

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

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

    sorting + one variable to hold current minima

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

What is test 2 of Problem E?

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

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

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

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

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

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

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

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

Problem D reminded me of Leetcode — Stone Game VI

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

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

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

    No when you exceed the limit program stops and terminates TLE

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

How to solve Problem C without using DP ?

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

    check out my solution. I used vector dp like a history. It has nothing to deal with dp, I was lazy to rename it after going out of dp So my idea was that if we go from ai to aj so we don't need to calculate situation where we go from ak to aj and k > i. Because we'll get a smaller number anyway. So we put every calculation of aj in dp vector and check if we've already calculated it

    https://codeforces.com/contest/1472/submission/103281636

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

How to solve B?

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

    N^3 worked for me If totalsum is odd its NO Else checked if currsum can be totalsum/2

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

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

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

Problem E was simple Fenwick Tree implementation

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

yet again I couldn't solve any problem and it's div.3. I am amazed by my dumbness. shame on me :(

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

    Don't lose hope. I went through this in 2 contests. So no worries and don't feel bad and pity on yourself.

    Just remember to do these things for sure till next div 3 round. 1. Attend all the contests till next div 3 round. 2. Upsolve all the problems using editorial after contests no matter how advanced the topic is. 3. Devote atleast 4-5 hrs daily on problem solving and aim to solve 2-3 problems within that time that are above your current rating level.

    And today I got A, B, C and D Accepted during the contest and E had some implementation difficulty but I cracked the logic.

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

      So you're telling me to solve(upsolve) A,B,C,D,E,F in all contests? but I don't think I would do that after c.

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

        Well making progress in CP isn't that easy. You gotta put in some more effort to achieve quick results. Also, maybe for now you can skip E and F and instead do some more B and C or even consider virtual contests for practice.

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

I could only solve 3 problems, too bad for a student

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

when the editorial is published

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

I really liked the problem set. Thank you for the contest.

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

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

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

Is rank predictor broken?

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

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

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

»
13 days 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$$$?

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

    Yes,it is possible

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

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

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

      Can you please help me with this WA?

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

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

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

DIV 3 PROBLEM C VIDEO TUTORIAL LINK https://www.youtube.com/watch?v=7FFzXk-brRU I have tried my best to give you guys proper intuition of this dp problem. Hope you guys will enjoy this video !!!

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

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

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

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

    • »
      »
      »
      13 days 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^__^

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

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

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

    First tell me Why are u cheating

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

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

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

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

    Fuck you piece of shit. YOu have no morals & u filthy dickhead should go to fucking hell.

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

    Maybe you checked the "show unofficial" on the top right, and it's showing more people. But in your friends standing the rank that shows up is the official rank

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

I really found the problems really interesting. Thanks for such wonderful problems

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

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

If My submission gets Hacked. How can I check For what input it failed or gave TLE. Is there a way?

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

How is my new user handle?

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

Testing on hacks completed or not?

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

Hey there I just got this message from system saying that those people wrote the same code as I did , now I know that I don't use platforms like ideone I use my favorite editor **VScode ** so all my code is private and local none of it goes public.

I write my code using really standard rules, so the code looks similar to others that might the reason, I would love to get my codes back as well as my participation in the round Codeforces Round #693 (Div. 3)Codeforces Round #693 (Div. 3), I don't care how I did in this round I want my rate to change cause its just a new year and I wanna go back to solving more problems on this platform.

note : I think I did good in this contest. I was hyped to see the ratings don't put me down :)

Thanks alot

Attention! Your solution 103286677 for the problem 1472D significantly coincides with solutions Fumetsu_no_kitsune/103286677, johnJ21450/103289999, vk99/103290163, aditya_pratap1/103290631, fakeaccforcf1/103290725, Kryptoniom/103291794, coder1234/103292576, booliandm/103292787, ikdjfkjnfkjnvjk/103293168, asimmc/103294702, riya.ras144/103296299. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

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

I participated in the contest and even made 3 submissions (2 AC) in the contest time. However, it does not show in my profile under "contests "and my rating too hasn't changed. Why is this so? I am kinda very new here so still tryna figure things out.

Edit: Done! I guess it takes some time tp update.

»
12 days 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,,

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

Hey can someone explain the editorial for e. I did not get how the case when one person is standing and one person is lying has been considered in the editorial solution??

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

Hello, I am a real newbie. Please can someone explain to me question E. I am not able to wrap my head around it.