Codeforces Round #758 (Div.1 + Div. 2)

Hello, Codeforces community!

I'm glad to invite you to Codeforces Round #758 (Div.1 + Div. 2), which will be held on Saturday, December 11, 2021 at 10:05UTC. 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 Bugman, additional tasks brought to you by Um_nik and gen. We are very thankful to the testers: 1-gon, 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 cat998__ for cooperation, Bytedance instructors Retired_MiFaFaOvO, 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

• 5 days ago, # ^ |

  ← Rev. 3 →  

  +25

  There is also an Innopolis Open Olympiad, and Moscow Workshops Online Contest(which is what this round will be based on). So 5 contests in total, what a wild Saturday.

  UPD: and Advent of Code! That's fascinating.

  • 4 days ago, # ^ |

    And me being in the bus during all of rated contests for me on that day

    • 4 days ago, # ^ |

      I hope there is a wifi connection in the bus :)

  • 4 days ago, # ^ |

    Add Leetcode Biweekly Contest #67 to that list too !

  • 4 days ago, # ^ |

    There is also Croatian Open

• 3 days ago, # ^ |

  Also leetcode Biweekly , hackerearth easy :)

• 3 days ago, # ^ |

  Where is the registration link?

• 4 days ago, # ^ |

  Unusual Timings are becoming usual these days :|

• 4 days ago, # ^ |

  After 10 days of break, finally

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

  • 4 days ago, # ^ |

    ← Rev. 2 →  

    +5

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

    • 4 days ago, # ^ |

      long long long long

      I believe the technical term is __int128 :)

      • 3 days ago, # ^ |

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

  • 4 days ago, # ^ |

    The comment is hidden because of too negative feedback, click here to view it

    • • 4 days ago, # ^ |

        The comment is hidden because of too negative feedback, click here to view it

        • 4 days ago, # ^ |

          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.

    • 4 days ago, # ^ |

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

      • 4 days ago, # ^ |

        The comment is hidden because of too negative feedback, click here to view it

        • 4 days ago, # ^ |

          ← Rev. 2 →  

          +30

          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

• 4 days ago, # ^ |

  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?

  • 4 days ago, # ^ |

    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.

    • 4 days ago, # ^ |

      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.

    • 4 days ago, # ^ |

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

    • 3 days ago, # ^ |

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

    • 2 days ago, # ^ |

      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.

  • 4 days ago, # ^ |

    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...

• 4 days ago, # ^ |

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

  • 4 days ago, # ^ |

    ← Rev. 2 →  

    -36

    The comment is hidden because of too negative feedback, click here to view it

• 4 days ago, # ^ |

  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.

  • 4 days ago, # ^ |

    ← Rev. 2 →  

    0

    Hope it only sounds that way..

  • 4 days ago, # ^ |

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

    • 4 days ago, # ^ |

      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 days ago, # ^ |

  ← Rev. 4 →  

  +3

  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 days ago, # ^ |

    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.

• 4 days ago, # ^ |

  the reason newbies are bloody scared lol..

• 3 days ago, # ^ |

  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 days ago, # ^ |

    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

• 4 days ago, # ^ |

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

• 4 days ago, # ^ |

  ← Rev. 4 →  

  -24

  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 :_:

  • 4 days ago, # ^ |

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

  • 4 days ago, # ^ |

    Thanks buddy.

• 4 days ago, # ^ |

  If you have this mentality, you will never improve

  • 4 days ago, # ^ |

    Thanks for suggestions. Got it.

• 3 days ago, # ^ |

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

• 3 days ago, # ^ |

  I guess they wanted people to switch to ABC 231 xD

• 3 days ago, # ^ |

  The difficulty gap between C and B...

• 3 days ago, # ^ |

  same :( , i don't know why TLE

• 3 days ago, # ^ |

  how to solve it?

  • 3 days ago, # ^ |

    ← Rev. 2 →  

    +8

    please I dont want to talk about this problem anymore.

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

    • 3 days ago, # ^ |

      ← Rev. 2 →  

      +3

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

      • 3 days ago, # ^ |

        ← Rev. 2 →  

        +5

        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 days ago, # ^ |

          I meant > of course, changed previous message

    • 3 days ago, # ^ |

      Only this idea I have for problem B.

  • 3 days ago, # ^ |

    ← Rev. 2 →  

    0

    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 days ago, # ^ |

  ← Rev. 2 →  

  0

  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 days ago, # ^ |

  With , 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 days ago, # ^ |

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

  • 3 days ago, # ^ |

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

    • 3 days ago, # ^ |

      Then what's the intended complexity?

      • 3 days ago, # ^ |

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

    • 3 days ago, # ^ |

      138774185

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

      • 3 days ago, # ^ |

        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 days ago, # ^ |

  cancer

• • 3 days ago, # ^ |

    yeah that was evident.. what I was doing was take an array 1,2,3,4,5,6... now swap 1,2 to get minima and swap last two ele to get maxima and I noted x number of maxima will contribute to x-1 no. of minima and vice versa ,still failed on pretest 3

• 3 days ago, # ^ |

  ← Rev. 2 →  

  0

  Spoiler

  • 3 days ago, # ^ |

    we can use two pointer approach to avoid lenghi implementation

    • 3 days ago, # ^ |

      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 days ago, # ^ |

        we dont have to worry about that case check this if you want

• 3 days ago, # ^ |

  I got some idea of constructing hills and valleys , But it was a tedious job for implementing my idea . After 2 attempt i got AC (: Here is my submission 138751882

• 3 days ago, # ^ |

  Asides the condition that SouLPegasuS pointed out, the basic idea is that swapping any two numbers in the range (2,n — 1) increases a and b by one. Swapping the first and second increases b by 1. Swapping n and n — 1 increases a by one. Then you can build the array from there.

• 3 days ago, # ^ |

  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 days ago, # ^ |

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

• 3 days ago, # ^ |

  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 days ago, # ^ |

    ← Rev. 2 →  

    0

    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 days ago, # ^ |

  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: ) The second case is quite trivial, then the complexity is just or if you calculate the reciprocal using quickpow.

• 3 days ago, # ^ |

  ← Rev. 2 →  

  +8

  Spoiler

• 3 days ago, # ^ |

  ← Rev. 2 →  

  +16

  Spoiler

  • 3 days ago, # ^ |

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

    Spoiler

    • 3 days ago, # ^ |

      Sure there isn't any invalid case.

      • 3 days ago, # ^ |

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

  • 3 days ago, # ^ |

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

• 3 days ago, # ^ |

  How did you find them ?

  • 3 days ago, # ^ |

    they were mentioned as cheaters in the previous round.

    but they were never caught even with the same codes.

• 3 days ago, # ^ |

  Well, you are convuluting terms of . It clearly becomes a single binomial coefficient.

  • 3 days ago, # ^ |

    ← Rev. 3 →  

    0

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

    • 3 days ago, # ^ |

      Yes that was my idea too.

      We want the ogf where BB is and WW . So after convolution we find the coefficient of .

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

      • ?B/B?:
      • ?W/W?:

      We want to multiply all these terms but actually it they are all of the form .

      Now, we want to find . But this just

      • 3 days ago, # ^ |

        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 days ago, # ^ |

          ← Rev. 2 →  

          0

          Why can't we use NTT

          We can just convolute everything in using NTT and it passes in half the TL (which I submitted during testing because lol). 138776423

          Alternatively, we can do it in . We convert all 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 by taking the logarithms of the polynomial.

          • 3 days ago, # ^ |

            ← Rev. 3 →  

            +10

            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 days ago, # ^ |

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

      • 3 days ago, # ^ |

        Lovely, thanks for explaining it.

• 3 days ago, # ^ |

  ← Rev. 2 →  

  +5

  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 days ago, # ^ |

    how are you going to handle strings equal to .

    • 3 days ago, # ^ |

      Replace by , then it'll be

    • 3 days ago, # ^ |

      Sorry if I wasn't clear- instead of pairs, we view it as characters (and then adjust for the corner case).

      Code: https://codeforces.com/contest/1608/submission/138771080

    • 3 days ago, # ^ |

      Also, you can see that the condition is equivalent to # of = # of , so consider each character individually.

• 3 days ago, # ^ |

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

• 3 days ago, # ^ |

  ← Rev. 2 →  

  +67

  I think C is a good problem but with weak pretests

  • 15 hours ago, # ^ |

    it's not a intersting problem, and most people solve it by guess(which cause many FST , I don't think it's a good problem. And some people use algorithms relative to graph,which isn't expected to be in div2C.stupid problem and stupid you

• 3 days ago, # ^ |

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

  • 3 days ago, # ^ |

    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 days ago, # ^ |

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

• 3 days ago, # ^ |

  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 days ago, # ^ |

    How does a genuine solution fail?

    Tests being generated today would certainly explain something.

    • 3 days ago, # ^ |

      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 days ago, # ^ |

      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 days ago, # ^ |

  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 days ago, # ^ |

    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 days ago, # ^ |

  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 days ago, # ^ |

    That's fair.

  • 3 days ago, # ^ |

    that's true

• 3 days ago, # ^ |

  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 days ago, # ^ |

  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 days ago, # ^ |

  ← Rev. 2 →  

  +8

  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 days ago, # ^ |

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

• 3 days ago, # ^ |

  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.

• 43 hours ago, # ^ |

  same...

• 3 days ago, # ^ |

  I can understand your pain bro,You got two FST. :(

• 3 days ago, # ^ |

  first judge if a > b or a < b

  set maxx = n, minx = 1

  if a > b then fill a[1] (the array start with 1) with minx, then minx++

  else then fill a[1] with maxx, then maxx--;

  then i from 2 to a + b + 1, fill a[i] with minx or maxx

  and from a + b + 2 to n, fill a[i] with the rest numbers in ascending or descending order

  depending on the a[a + b + 1] is max or min

  #include <bits/stdc++.h>
  
  using namespace std;
  
  int t, n, a, b, q, minq, maxq, a1, b1;
  int x[100010];
  
  int main() {
  	cin >> t;
  	while (t--) {
  		memset(x, 0, sizeof(x));
  		cin >> n >> a >> b;
  		a1 = a, b1 = b;
  		if (abs(a - b) > 1 || a + b > n - 2) {
  			cout << "-1" << endl;
  			continue;
  		}
  		if (a > b)
  			q = 1;
  		else
  			q = 0;
  		minq = 1, maxq = n;
  		if (q == 1)
  			x[1] = minq++;
  		else
  			x[1] = maxq--;
  		for (int i = 2; i <= n; i++) {
  			if (a == 0 && b == 0) {
  				//if (q == 0)
  				//	x[i] = minq++;
  				//else
  				//	x[i] = maxq--;
  				break;
  			}
  			if (q == 1)
  				x[i] = maxq--, a--;
  			else
  				x[i] = minq++, b--;
  			q ^= 1;
  		}
  		if (q == 0) {
  			for (int i = a1 + b1 + 2; i <= n; i++)
  				x[i] = maxq--;
  		}
  		else {
  			for (int i = a1 + b1 + 2; i <= n; i++)
  				x[i] = minq++;
  		}
  		for (int i = 1; i <= n; i++)
  			printf("%d ", x[i]);
  		printf("\n");
  	}
  	return 0;
  }

• 3 days ago, # ^ |

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

  • 3 days ago, # ^ |

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

    • 2 days ago, # ^ |

      looks like I got rejudged and hit grandmaster

• 3 days ago, # ^ |

  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 days ago, # ^ |

  Why weak pretest of problem C is not mentioned?

  • 3 days ago, # ^ |

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

• 3 days ago, # ^ |

  In B was at least and samples had and and some case. There could've been more cases covered, but I thinks that's good enough

• 3 days ago, # ^ |

  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 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 so we can multiply it with . Other cases are similar, and finally we get , the answer is the coef of the term . It turns out to be . 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 and check if all strings can be one of WB or BW.
  Total time complexity: .

  • 3 days ago, # ^ |

    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 days ago, # ^ |

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

• 3 days ago, # ^ |

  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 days ago, # ^ |

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

• 3 days ago, # ^ |

  Because, testers not did there job well. They just used their big names.

• 3 days ago, # ^ |

  why won't you remove cheaters from previous rounds?

  137247368 137234971 137232569

• 3 days ago, # ^ |

  ← Rev. 3 →  

  0

  Code

• 3 days ago, # ^ |

  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 days ago, # ^ |

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

  • 3 days ago, # ^ |

    Don't you think very weak pretest is rubbish?

• 3 days ago, # ^ |

  [1, 1, 0], [1, 2, 0], [1, 3, 0].

  • 3 days ago, # ^ |

    Very thanks.