TadijaSebez's blog

By TadijaSebez, 3 years ago, In English

Hello, Codeforces community!

I'm glad to invite you to Codeforces Round #758 (Div.1 + Div. 2), which will be held on Dec/11/2021 13:05 (Moscow time). The round will be rated for both divisions. Note the unusual start time.

The problems were taken (mostly) from the ByteDance — Moscow Workshops Online Contest, which is happening at the same time. Tasks from the Online Contest are prepared by TadijaSebez and oversolver, additional tasks brought to you by Um_nik and gen. We are very thankful to the testers: Monogon, 74TrAkToR, AmShZ, DeadlyCritic, errorgorn, oolimry and icypiggy for their time and great feedback. Also big thanks to authors of other problems of the Online Contest snarknews and teraqqq for cooperation, Bytedance instructors jqdai0815, Syloviaely, Gromah, Claris for testing and reviewing the Bytedance online contest, the contest coordinator antontrygubO_o for the great help in setting up that round and MikeMirzayanov for testlib.h, Polygon and Codeforces.

ByteDance is a global technology company operating a range of platforms that allow people across languages, cultures, and geographies to create, discover and connect. ByteDance has partnered with Moscow Workshops and Codeforces to organize a top-tier and exclusive training camp for the International Collegiate Programming Contest. The upcoming Programming Camp will be held in Beijing from February 17th to 23th, 2022.

ByteDance — Moscow Workshops Online Contest is an opportunity to participate as teams onsite in this camp. Due to COVID-19 restrictions, mainly teams from China can participate onsite this year. For the international teams, the opportunity of online participation is considered.

You can find more information about this training camp at https://programcamp.bytedance.com/.

UPD: The scoring distribution is 250 — 750 — 1000 — 1500 — 2000 — 2500 — 2750.

UPD 2: Editorial

  • Vote: I like it
  • -219
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

3 contests in a day! CF, atcoder ABC, then CC starters.

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

I loved the problems.

»
3 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Note The Unusual Timings

:')
»
3 years ago, # |
  Vote: I like it -29 Vote: I do not like it

Will it be based on ICPC style scoring or problems will have separate points like in normal div 1+2 rounds?

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

I think div.1 + div.2 always be a big challenge and it means large rating increasing or decresing. Hope everyone can gain more rating!

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

After 10 days of break, finally a codeforces round. Hope this round will be good.

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

    After 10 days of break, finally

    Wait until you get to Div. 1 if you think 10 days is long.

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

      For div 1 coder, like you, the word should be "long long long long".

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

        long long long long

        I believe the technical term is __int128 :)

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

          No no no it is __int256. You've counted wrong, long long long is __int128.

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

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

      Nothing prevents you from doing unrated participation in Div.2 rounds. That is if you want to have fun solving problems together with the others and then discuss interesting solutions after the contest is over. Also in an unrated round you are free to start solving problems in reverse order if wasting time on Div.2 A/B/C/D is not enjoyable.

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

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

          I participated in an unrated Div.3 contest on Codeforces when I briefly became expert. And I participated in a few unrated Div.3 / Div.2+3 CodeChef contests too. Not to mention AtCoder AGC contests (unrated for a different reason). All of these contests were fun and challenging, even though they didn't affect my rating. So what exactly would I not get?

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

            Rating is the motivation and that's the fact.

            Participating in the first unrated contest (because one is an outside the rated range) is wholly different from consistently doing it.
            Judging from your comments (related to different languages and compilers) that may not be the case with you. But it's the case with the majority of people here.

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

        Then the original commenter still shouldn't complain because nothing prevents them from doing HackerEarth contests and geography homework.

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

          I have nothing to say about your "geography homework" claim, because it's a total nonsense. I'm putting the rest of my reply under a spoiler, because it's a bit too long:

          Spoiler
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            Rev. 2   Vote: I like it +30 Vote: I do not like it

            You are overthinking it.

            • The meaning of my first comment: Div. 1 contests are more sparse than Div. 2 and it is kinda funny to see Div. 2 people complaining.
            • The meaning of my second comment: A Div. 2 contest is not the same as a Div. 1 contest, just as a Div. 2 contest is not the same as a HackerEarth contest.

            That's it. That's the meaning of these two comments. Extracting anything else from there is a bit silly.

            Here is my reply to your essay
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why is the round combined division?

Personally, I hate combined division rounds with a passion. Even if they are very nice, I find that adding two easy problems to Div. 1 makes the round less enjoyable, at least for me. What is more, I find it horrifying that every scheduled, rated for Div. 1 contest until the end of the year is combined division. I can sort of understand why Global round is combined division, and I suppose that it is somehow traditional that the Good Bye round is combined division (especially if it is sponsored and therefore may have prizes) but what is the reason for this round? Just that it is a copy of some other contest?

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

    Why though?
    From what I understand (admittedly having never been in div 1), shouldn't combined rounds ideally be, for div 1 participants, a 30 mins or so speedtyping contest and after that a normal div 1 round?

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

      Do you find a 30 min speedtyping contest fun?

      Further, getting stuck on one of the easy problems is the worst feeling in the world and is a major tilting factor for me.

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

        Yeah, understandable. Separate div 1 and div 2 rounds seem much better then for div 1 participants, since they take away the speed-typing part of it.

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

        Agree, when I solved A,B and saw over 1000+ people have passed,the feeling is really bad :(

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

        Good thing this contest was just a regular div1 with an extra easier problem :clown:

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

        This is a tangent. If I face trouble solving a problem, I don't call it easy. Actually I try to refrain from labeling problems "easy" and observations "obvious". I don't like people doing that either, NGL. By calling something "easy" we undermine the observations which were required to solve it whether we meant it that way or not. Not at all saying its right or wrong, just felt this viewpoint should be out there.

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

      Normally, I wouldn't worry too much about 30 mins of speedtyping, but the fact that this combined round is just 2 hours long makes me nervous, since it leaves only 1.5 hours for Div 1 problems. That is, if we do not fuck up and waste more time on the easy ones...

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

    Combined rounds and easy problems are the reason why I'm at 2800 and not 2500 and I'm not very proud of this

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

    A 2 hour combined round sounds really scary to me. Div 2 people tend to like combined rounds because they can gain a lot of ratings with a good performance. It sucks for us but we are the minority after all.

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

      is it true div2 people can gain more rating in combined rounds? based on my experience the gains are exactly same as div2 rounds

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

        If you over performs and beats some Div 1 participants you're not supposed to, you will gain more than you do in a normal Div 2 round (because you won't get a chance to beat them under this circumstance). This of course only applies to very few people each round but it does generate a mental effect for a lot of people.

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

    There is a benefit to combined rounds, though. In many Div 1 only contests, if people don’t like the look of problem A they just bail out to stay unrated, which means that those who actually try are penalised for it. There was a very recent example of this in round 745 Div 1 — problem A was hard so over half the registered competitors submitted nothing. I think having a problem A and B doable very quickly kind of forces your hand — you’re either in or you’re out, you don’t have time to play the system.

    This is not to say that you don’t make many valid points; just to point out one benefit which I actually consider quite significant.

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

      Frankly I think that in every contest the problem A should be easy for all intended participants, partly because of what you said but also for other (mostly, psychological) reasons.

»
3 years ago, # |
  Vote: I like it -34 Vote: I do not like it

Imagine not upvoting this blog.

»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Nice

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

lol

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

So, my plan is to solve as many problems till 13:00 and then instead of despairing at the last 3-4 problems, I'll switch towards ABC contest to keep up that sense of achievement. #ICheatMyself

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

the best round because it's written by the best programmer

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

No testers are begging for contributions (specially 1-gon) XD.

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

    Idk maybe ill just rant about testers commenting in blogs here since the round is over. Why is it normal that testers are commenting things such as "I loved problems", "Problems are beautiful". Why is everyone fine with people saying that? Would people be fine if I commented "I didn't enjoy the problems, they were boring"? Should we normalize testers saying "I hated the problems" in future contests now?

    I honestly find it hard to believe that the guy who only solved ABC in VC and didnt upsolve anything else commented "I loved problems" because he genuinely loved the problems. You really looked at ABC and went "I love these problems"?

    Can we as a community just stop pandering these types of testers, please. Make testing be a job of ensuring contest quality, not a contribution farmer for those with the right connections.

    Thank you for listening to my TED talk.

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

      There really is nothing wrong with testers saying "I loved problems", "Problems are beautiful" as a tester if you really enjoyed the contest. In fact, I think its a good way to encourage others to take part in a round that you believe they will enjoy, as well as a public compliment to the setters

      But of course if you recommend the contest and people didn't like it otherwise, then you're at fault for misleading the participants who hoped for a good contest, and also making future "I loved problems" recommendations by testers less credible for actually good rounds. If they're an outlier who thinks it's good while others thinks it's bad then whatever, but outliers are rare (and should know when their opinions aren't aligned with what others think)

      Anyways, if no tester comments anything, it probably says more about the round than if testers are commenting if they enjoy testing

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

if any of you are interested in cheating, send a message to nitin_05 or ashokesen02. they both became experts in codeforces by buying solutions and adding many comments in the codes.

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

    Don't increase the interest. The situation already sucks as it is.

»
3 years ago, # |
  Vote: I like it -34 Vote: I do not like it

What may be the difficulty level for the problems?? If I could know, I could decide whether to participate or not as I only can solve up to 1200 difficulty level, anyone please have idea??

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it -24 Vote: I do not like it
    A - [800,900] (Greedy or some basic maths)
    
    B - [1000,1200] (Implementation or Greedy)
    
    C - [1300,1400] (Bs, prefix sum Greedy, two-pointers)
    
    D - [1500- 1700] (some data strcture, dp, maths ,even greedy
    

    Beyond This i dont know Clearly coz i havent solve any :_:

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

      I think even C will be about maths, not to mention any further problems

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

    If you have this mentality, you will never improve

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

I have a gut feeling we are going to face problems of Byteland

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

contestfull day it is...

»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Give me some delta ...

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

    Looks like I forgot to mention "positive". So much of negativity out here (:

»
3 years ago, # |
Rev. 3   Vote: I like it -32 Vote: I do not like it

Hope to gain some non-negative delta!

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

The difficulty gap between C and D

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

    I guess they wanted people to switch to ABC 231 xD

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

    The difficulty gap between C and B...

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

Before starting of the round : "I am gonna try to get to 1100 this time" After implementing problem B : "Ahh !! Shit, Here we go again"

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

Thank you very much for a disgusting round.

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

Me after rating changes.

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

Hmm this is weird my solution for C is n*Log(n) but it's TLE I can't see what did I do wrong

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

It was so difficult that I sat down in two minutes

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

I'm gonna have nightmares about B. Daaamn it took me so long to to get it.

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

    how to solve it?

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

      please I dont want to talk about this problem anymore.

      But basically if abs(a — b) > 1 then you can't construct it.

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

        also you can't construct it if a + b > n — 2

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

          If a + b = n - 2, you actually can in some cases construct a valid solution.

          Example: n = 4, a = 1, b = 1

          Answer (one of): 4 1 3 2

          Edit: the previous commenter changed >= to >

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

            I meant > of course, changed previous message

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

      You can take the starting value to be (a+b+1). Then, store the remaining values in a deque in increasing order. If you have to put a minima, take the least value from the deque and put it in the array. If you to put a maxima, take the greatest value from the deque and put it in the array. When you run out of the required maximas and minimas, you can put the remaining values in increasing order (if the previous value was a minima) or decreasing order (if the previous value was a maxima).

      And, do not forget about the edge case when a = 0 and b = 0.

      I hope this helps.

»
3 years ago, # |
Rev. 2   Vote: I like it +111 Vote: I do not like it

thank you for the worst contest i've ever seen , and f**k problem B

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

    We should vote down this contest. B isn't the only reason why I felt awful. Otherwise there will be more contests like this contest.

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

My solution to E is nlogn*24, was it intended to fail? I have used ordered_sets which could have been avoided using fenwick but didn't have time to implement.

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

    With $$$n = 10^5$$$, it should be very hard to fail on CF machines. My solution also uses those super slow multisets and runs in 1.2s on the worst of these 60 pretests.

    Speaking of which, 60 pretests is excessive. This isn't some kind of wild random problem where no solution is guaranteed to be 100% AC.

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

      I saw other submissions too and they have used ordered sets and seem identical to my approach, but why I failed T-T.

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

      Actually, I submitted > 30 times, spent > 5 hours to optimize it, couldn't...

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

        Then what's the intended complexity?

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

          It's the same, and is indeed way faster than mine.

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

        138774185

        As straightforward as it gets for time complexity, 2*2*2*3*2*2 times we sort and gradually insert/remove $$$N/3$$$ elements. Multiset gives 1400 ms, heap 700 ms.

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

          Yeah, but still there are many reasonable ways to implement it which has way worse multiplier. Mine had > 500 I guess. However it could barely pass TL with the new constraints.

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

Why did problem C have 1sec time limit instead of 2?

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

What the fuck was problem B

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

Hint for B?:(

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

      we can use two pointer approach to avoid lenghi implementation

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

        I constructed it using a deque. I thought about 2 pointers but I didn't want to have to deal with the case when n is odd and the left and right pointer meet at the same point.

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

Why only 2 hours???

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

What an unbalanced problemset!

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

worst contest I've ever competed in

»
3 years ago, # |
Rev. 2   Vote: I like it +75 Vote: I do not like it

Fst'd C because I didn't clear the adj2(graph) in each test.Pretests are very weak

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

    In C's pretest the answer is always everyone wins or exactly 1 person wins.A code in my room only had these cases and it passed.

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

      Were pretests generated completely randomly?I am not sure how the above linked code passed pretests

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

Why would that TLE in C I'm not looking at any number twice right ?

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

    When using sets you appear to use (correctly) set::lower_bound, but with maps you use std::lower_bound instead of std::map::lower_bound. If you fix this does it solve your problem?

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

      i called them mp1,mp2 as a reference that they represent the two maps in problem C but they're vectors I should write the code clearly there're several stupid things but i didn't waste time during contest to make the code better but that's not the TLE reason though or can i use that sort on vectors ? Or you mean i should use maps I'm confused

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

lots of people getting wrong on test case 21 on problem C. :( me also

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Ideas for problem D?

I think it might be Qpow+NTT, but 10^5 seems to be a bit big for that...

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

    It's easy to see that the coloring is valid only when the number of 'BB' and 'WW' is the same,except for when there is only 'BW' and 'WB'. The first case can be calculated by using generating functions.(Hint: $$$[x^k](1+x)^n=\dbinom{n}{k}$$$ ) The second case is quite trivial, then the complexity is just $$$O(n)$$$ or $$$O(n\log n)$$$ if you calculate the reciprocal using quickpow.

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

Any hints for Problem D?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it
    Spoiler
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it
    Spoiler
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Here's another one, which might contain more important spoiler.

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

        Sure there isn't any invalid case.

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

          Ok That's it. I think you almost reached to the answer. Count all the cases and subtract the number of invalid cases.

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

      Spoiler's spoiler: Don't prove it, just submit.

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

look at their submissions.

nexoxogoc ouhtek robot_bobot ybgbsydvh

»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

.

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

What is the non-convolution solution for D?

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

    Well, you are convuluting terms of $$$x^a (1+x)^b$$$. It clearly becomes a single binomial coefficient.

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

      Can you elaborate? my idea is that the number of $$$WW$$$ should equal the number of $$$BB$$$, But I think your approach is different.

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

        Yes that was my idea too.

        We want the ogf where BB is $$$x^{-1}$$$ and WW $$$x^1$$$. So after convolution we find the coefficient of $$$x^0$$$.

        Now we state the polynomials for each string (i will ignore BW and WB for obvious reasons).

        • BB: $$$x^{-1}$$$
        • WW: $$$x^1$$$
        • ?B/B?: $$$x^{-1}+1$$$
        • ?W/W?: $$$1+x^1$$$
        • ??: $$$x^{-1}+2+x^1$$$

        We want to multiply all these terms but actually it they are all of the form $$$x^a (1+x)^b$$$.

        Now, we want to find $$$[x^0] x^a (1+x)^b$$$. But this just $$$\binom{b}{-a}$$$

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

          Aww I didn't realize (1+2x+x^2)=(1+x)^2 and was thinking to use NTT... How stupid!

          Thanks for the explanation!

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

            Why can't we use NTT

            We can just convolute everything in $$$O(N \log^2 N)$$$ using NTT and it passes in half the TL (which I submitted during testing because $$$N=10^5$$$ lol). 138776423

            Alternatively, we can do it in $$$O(N \log N)$$$. We convert all $$$5$$$ polynomials to their point coordinate form using NTT then do the multiplication there and do the inverse NTT. 138777576

            There is an alternate way to do it in $$$O(N \log N)$$$ by taking the logarithms of the polynomial.

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

              Yes we definitely can, and that's what I attempted during the contest.

              I'm just feeling idiotic for not realizing the trivial simplification.

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

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

          lol, that was my initial idea which I brushed off? good to know how idiotic I was.

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

          Lovely, thanks for explaining it.

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

    The necessary and sufficient condition is #[WW] = #[BB] (except for if there's none, you must have all WB or BW). If you naively assign B's and W's to ?'s so there's an equal count of each, this forces the above condition. The only invalid assignments we may have counted are sequences with only WB and BW's, and a nonzero amount of each. We can easily subtract this overcounted value.

»
3 years ago, # |
  Vote: I like it -29 Vote: I do not like it

Even this code could pass the pretests of C:

#include<bits/stdc++.h>
//#define int ll
#define pb push_back
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define piii pair<int,pair<int,int> >
using namespace std;
typedef long long ll;
const int N=300005;
const int inf=1<<30;
const ll inff=1ll<<60;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
int n,o[N];
pair<int,pii>a[N];
int main(){int tests=1;tests=read();
while(tests--){
	n=read();
	for(int i=1;i<=n;i++)a[i].fir=read();
	for(int i=1;i<=n;i++)a[i].sec.fir=read(),a[i].sec.sec=i;
	sort(a+1,a+n+1);int mx=0;
	for(int i=1;i<n;i++){
		if(a[i].sec.fir > a[n].sec.fir) mx=1;
	}
	if(mx)for(int i=1;i<=n;i++)printf("%d",1);
	else for(int i=1;i<=n;i++){
		if(i == a[n].sec.sec) printf("1");
		else putchar('0');
	} puts("");
}	return 0;
}


So crazy. I cannot understand.

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

Main Test 21 on C killed a lot of us :(

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

    In fact it's the first test that the answer isn't all '1' or only one '1'.

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

Didn't expect problems like B and E in an anton contest.

»
3 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

wow I can't believe it!

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

C is the worst problem I've ever seen.Weak sample,weak pretest and stupid problem

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

Why is there no obvious corner cases in D's pretests?

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

~700 system test fail on C. Nice pretests you got there.

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

C has a lot of failed system tests because of weak pretests.

This actually made me realize something. It is for sure an unpopular opinion, but I think weak pretests can be a good thing.

C is exactly the type of problem that a lot of people solve by guessing: there are a lot of feasible-looking greedy-strategies, people implement one of them without knowing whether it actually works, get AC and move on to the next problem.

Weak pretests disincentivize guessing and make contestants more careful. It puts more weight to mathematical thinking and less to just quickly implementing something that might be correct.

The bad thing is that people expect "pretests passed" to mean "accepted" and get frustrated when they fail the system test. But if weak pretests were more common, people wouldn't have such an expectation and would be more careful from the start.

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

    If you value the 'proving' of solutions more, why not just increase the penalty?

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

      That's also an option.

      However in my ideal world that I made up just now, pretests should include edge cases but not necessarily counterexamples to typical guesses. In that case:

      • not noticing edge cases gets a small penalty;
      • guessing and submitting an unproven idea gets a big penalty.
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        However the edge cases are different for different (wrong) solutions, which makes it difficult to decide which should get a small penalty.

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

    Well I think in C many genuine solutions also failed.The pretests were so weak that the number of winning contestants was always 1 or n.I heard from a tester that the testcases were generated today

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

      How does a genuine solution fail?

      Tests being generated today would certainly explain something.

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

        In my solution I cleared adjacency list of original graph but missed doing that for the reverse graph and it failed.By genuine I meant correct idea of solution.my solution was to add an edge from index of the (i+1)smallest number to the index of the ith smallest number in the both the arrays.The winning set is the 1st SCC.

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

        Well my solution was correct but only because I by mistake took sorted indices instead of original indices, it FSTed.
        WA
        AC
        Just think how weak were pretests, that it passed with even wrong indices marked as '1' & '0'
        Even a trivial test case where sorted indices and original indices didn't match should be added in the pretests (or even sample).

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

    I very much disagree. If pretests were made weaker in problems where people just guess, people would still guess and now get FST instead of WA on pretests, which makes the results of the contest way more random and less skill-based, and the contest less fun for everyone.

    I think the only way to fix this would be to require a proof of your solution in your submissions, which is obviously infeasible (but would be fun).

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

      If you guess wrong, you should get FST instead of WA on pretests. I guessed and got lucky to get WA on pretests, that shouldn't happen.

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

    Pretests is too weak, i sorted the array and forgot to put the answers back to those correct indexes, and that solution still passed pretests. If pretests were made to avoid guessing, it still need to be stronger to keep the genuine solution/idea AC.

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

    It would also make hacking a bigger part of contests. I don't know if that is a desirable outcome. On the one hand it might make contests more interesting. On the other hand it makes your performance more dependent on the other contestants assigned to the same room.

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

    however when I see this problem I immediately use strongly connected components to solve the problem instead of guessing conclusions although it took me a lot of time :(

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

In problem D, how to calculate $$$\sum_{x = 0}^{t} \binom{a}{t-x}\cdot \binom{b}{x}\cdot 2^{b-x}$$$ for every $$$t$$$ from 1 to 1e5 ($$$a$$$ and $$$b$$$ are constants) in $$$O(n)$$$?.

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

    I realised it only 1-2mins before the contest end that you do not need to do that, you just need to make sure that the number of W cells = number of B cells. Forcing number of BB = number of WW while not caring the number of WB and BW, it is actually the same as the constraint number of B cell = number of W cells. Of course, you have to deal with the case where there is no BB or WW.

    Figuring that out too late and having my C fail systest means I will be back to candidate master :(

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

      My bad, I flipped all the right colors thinking that it would make things easy and ended up missing this observation. Thank you.

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

    You don't need to. The final answer is a single binomial coefficient if you ignore the edge case, which you can subtract out separately.

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

What the hell, just mistake cell for grid point in E :(

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

Very weak pretests on D

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

How to unregister after contest ends?

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

Codeforces round #745(Div.1)+Codeforces round #745(Div.2)=Codeforces round #758(Div.1+Div.2)

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

»
3 years ago, # |
Rev. 2   Vote: I like it +33 Vote: I do not like it

Problem A was too easy.

Problem B was too weird for B level.

Problem C and D had too much FSTs and I didn't like C a lot(personal opinion).

Did not enjoy the contest that much.

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

Weak pretests and there are cheaters from byte-camp. Nice problems but bad round.

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

How to solve B cleanly? I have a monstrous 100 line casework solution but I seriously doubt its the intended:

  • $$$abs(a - b) > 1$$$ or $$$a + b + 2 > n$$$ $$$\longrightarrow$$$ $$$-1$$$

  • $$$(a = 0, b = 0)$$$ $$$\longrightarrow$$$ $$$1, 2, ..., n$$$

  • $$$(a = 1, b = 0)$$$ $$$\longrightarrow$$$ $$$1, n, n - 1, ..., 2$$$

  • $$$(a = 0, b = 1)$$$ $$$\longrightarrow$$$ $$$n, 1, 2, ..., n - 1$$$

  • otherwise $$$\longrightarrow$$$ split into $$$(a + 1)$$$ low segments (elements from $$$[1, n / 2]$$$) and $$$(b + 1)$$$ high segments (elements from $$$[n - n / 2, n]$$$) which alternate (Starting segment type and which segment $$$\frac{n + 1}{2}$$$ goes to for odd $$$n$$$ depend on whether $$$a \gt b$$$ or not). Sort each segment internally to ensure only one endpoint is a local maxima / minima (careful about sorting order for endpoints)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it
    code
»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

For E, is it possible that every single submission that passed pretests get rejudged to AC? I recall only seeing 61 pretests, and after system testing, there are only still 61 tests, so I don't believe any new tests were added. My submission received TLE after system testing, but I submitted the same code after contest, and it received AC. Also with this AC, I would become grandmaster for the first time, instead of going back to International Master.

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

    You can ask MikeMirzayanov , I remember it happened in previous rounds and the submission were rejudged .

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

      You can't and you shouldn't. That one time was a mistake.

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

        looks like I got rejudged and hit grandmaster

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

Is there any approach for solving C using C++ policy based data structures (PBDS)?

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

    If you mean for finding at least one element smaller/larger, which is what I tried, you can just use lower_bound on sets, but my code fails. I guess this greedy won't work, could someone show me a counterexample?

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

Share my solution to D:

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

Here is some feedback on the contest:

A: This is the easiest problem I remember having solved on codeforces. Ok problem.

B: Ok problem. Since it is a problem B and there are various cases to consider (as the infamous 1 0 0), I would have liked to have samples covering all possible cases.

C: Very nice problem. During the contest I did not prove the correctness of my solution.

D: Very nice problem. The first part of the solution (understanding which colorings are valid) is interesting and clean, the second part (i.e., how not to use FFT) is magical. Could have been better with higher constraints (and another modulo) to prevent FFT solutions from getting accepted.

E: Ok problem. Together with cip999 we proposed a problem very similar to this one for GR14 to antontrygubO_o, but he rejected it. Still, I messed up the implementation badly. I would have appreciated a higher time limit.

Thanks to the authors.

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

    Why weak pretest of problem C is not mentioned?

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

      Because I did not know about the weakness of pretests of problem C.

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

    In B $$$n$$$ was at least $$$2$$$ and samples had $$$a = b$$$ and $$$a + 1 = b$$$ and some $$$-1$$$ case. There could've been more cases covered, but I thinks that's good enough

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

    Actually there is no need of FFT in problem D.

    let a be the number of ?W and W?, b be the number of ?B and B?, c be the number of ??, and k be the number of BB-WW. Then use DP. Let $$$f_{i,j}$$$ to be the answer after the first i strings and the number of "WW"-"BB" is j. Consider the transition, we can use generating function to describe it. ?W or W? means $$$f_{i+1,j+1}\gets f_{i,j}+f_{i,j-1}$$$ so we can multiply it with $$$(x+1)$$$. Other cases are similar, and finally we get $$$(x+1)^a\left(1+\dfrac{1}{x}\right)^b\left(x+2+\dfrac{1}{x}\right)^c$$$, the answer is the coef of the term $$$x^k$$$. It turns out to be $$$\dbinom{a+b+2c}{k+b+c}$$$. And then we need to exclude the cases when only WB and BW exist. It's easy to solve it. We just need to minus $$$2^c$$$ and check if all strings can be one of WB or BW.
    Total time complexity: $$$O(n)$$$.

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

      Yes, I know. I think I wrote pretty clearly in my comment above that the problem is nice exactly because FFT is not necessary.

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

        My mistake. I saw it as how to use FFT XD

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

    The only reason why I solved D was because of upsolving 1450H1 - Multithreading (Easy Version). That is either a sign that I'm too stupid (very possible) or that the problem was in the wrong spot considering the contest is there also for div2.

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

    Case 1 0 0 is so infamous, so coordinator had removed it from original problem.

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it
17 Pages of WA *-*
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Spoiler

I've won, but at what cost? :(

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

The pretests for D were really bad. There were no pretests containing very obvious corner cases like all characters equal to '?'

»
3 years ago, # |
  Vote: I like it +54 Vote: I do not like it
Being really happy to make a successful hacking attempt on Problem C and then failed to pass system tests
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I don't know why this happened.. during the contest prob-C passed all the pretests,,but after the contest was over and after system testing it shows that wrong answer on testcase 23...What is this? why this happened??????????????????????

»
3 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Good contest full of adhoc problem. But I was not in good state..

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

I like F, but it would be better if the TL was more generous (I'm assuming my solution has the expected complexity). If you were afraid of $$$O(KN^2\log N)$$$ solutions with FFT, you could have used modulo $$$10^9+7$$$ to slow down such solutions.

G is a zero-idea implementation task. I really don't like it.

»
3 years ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

Bro bro wai petest so stronk??

int ma=0,mb=0;
forinc(i,1,n) a[i]=in,ma=max(ma,a[i]);
forinc(i,1,n) b[i]=in,mb=max(mb,a[i]);

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

Please can somebody say what's wrong with my approach? 138778827

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

Good contest! Interesting problems!

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

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

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

How to solve problem C greedily

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
    Code
»
3 years ago, # |
Rev. 3   Vote: I like it -37 Vote: I do not like it

[Deleted]

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

    Do you even know how much time it requires to create a problem? I also get fsted on C but its my fault only, not thinking about edge cases is ofc my fault.

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

      He haven't even submitted task C, lol. Then I'm not sure why he thinks that the contest is bad.

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

      Don't you think very weak pretest is rubbish?

»
3 years ago, # |
Rev. 4   Vote: I like it +30 Vote: I do not like it

TadijaSebez , oversolver by convention all cf div. 1 + div. 2 round has "Div. 1 + Div. 2" in the name where there's a space between Div. and the number. In this contest name there's no space between Div. and 1 so can you add a space as it is breaking CFTracker's categories. Thanks!

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

love this contest

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

Why dose the answer of sample #5 of F be 11? I can only find 8 arrays: [1,0,0],[1,0,1],[1,0,2],[1,0,3],[2,0,0],[2,0,1],[3,0,0],[3,0,1]

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

Hint for C.

»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Didn't understood C.