Hello Codeforces! We (dqa2021, Xiejiadong, Retired_xryjr233, Z18 and me) are excited to invite you to take part in Codeforces Round 664 (Div. 1) and Codeforces Round 664 (Div. 2), which will happen on Aug/12/2020 17:35 (Moscow time).

Huge thanks to:

- 300iq for coordinating our round.
- triple__a for answering my questions about contest preparation.
- duyiblue, jhdonghj112, jqdai0815 for providing and discussing ideas.
- gamegame, KonaeAkira, gtrhetr, jqdai0815, mayaohua2003, crasysky, aryanc403, RainAir, dqa2021, dingwanren, world_top_1_AD_uzi, Juanzhang, _Aaryan_, GavinZheng, taran_1407, yijan, whuang369, jhdonghj112 for testing and providing feedback.
- MikeMirzayanov for Codeforces and Polygon platforms.

There will be **5 problems** in Div.1 round and **6 problems** in Div.2 round. You'll be given **2 hours** to solve them.

The story of this round is about that man. Instead of displaying his name, I prefer telling one of his legends (or joke):

"I have a 'friend', who makes lots of money every day, earning a billion in the blink of eyes. With a wave of his hand, OIers all over the world will follow him."

You can post your guesses in the comments.

**UPD**: Score Distribution:

- Div.1: 500 — 1000 — 1500 — 1750 — 2500
- Div.2: 500 — 750 — 1000 — 1250 — 1750 — 2250

Good luck!

**UPD**: Congratulations to the winners!

Div.1:

Div.2:

Auto comment: topic has been updated by sshwyR (previous revision, new revision, compare).What's the point of declaring top 5 people in Div.2, after all they are just Div.1 guys who registered with their alternative account, isn't this unfair? for example just look at the person who is placed 3rd in Div.2, this guy was newbie, like seriously? This disrupts entire rating distribution.

I am tester, please upvote for me! :)

( I'M CUTE, GIVE ME CONTRIBUTION )

I am tester too, please upvote for me! :)

(I'M CUTER THAN duyiblue, GIVE ME CONTRIBUTION )

LOOOOOOOOL~~~~~

You are cute too.

haha

I am tester too, please upvote for me! :) (I'M THE MOST KAWAII TESTER IN THE TESTER TEAM QAQ)

How kawaii you are! Would you mind tell me what character she is?

avatar She is warship Queen Elizabeth from a video game called Azur Lane.

I am not tester, please upvote for me :) (I am cute)

i dont think tourist was there in this round.

I am tester tooo,plz upvote for me!:)

(OBVIOUSLY I'M CUTER THAN duyiblue AND jhdonghj112 QAQ)

Actually duyiblue and dingwanren are the same person?

So double contribution!

Actually they are not the same person.

Actually they are

dingwanren is a imitation of diamond_duke (an OIer in Senior 3 in NFLS) by duyiblue.

If you take a good look at duyiblue and dingwanren's programs, you will find that they have the same way of writing programs

Ah,I thought dingwanren was diamond_duke for I only see the profile page. What a mistake!

orz tzc, tzc tql ddw.

orz dy, dy tql ddw.

I'm cuter than duyiblue , I'm his girlfriend () please upvote for me

I think you should test the round next time instead of asking for contribution!

Hey tester, Why ruined the day of so many

cutecontestants with weak pretests?Good job testers very good round, glad nothing went wrong!

Sorry, but As a tester, you don't do a great job! Many solutions failed(even of LGMs)

Is the man is Bill Gates? :D

very close (in their amount of money), but not.

Elon musk ?

Boboniu！

Jeff Bezos ?

is it kanye?

You are thinking it's spam that's why I removed it and going to do some practice otherwise in search of the name I will lose my ratings. XD:)

This shitty name is spamming everywhere.. Please stop that.

Edit: It's not a spam, it's a trend. Do some research.

is that man Jack Ma? just a random guess

We don't want stories please, as they come in the way of easily comprehending the problem statement. :(

Oh don't worry. The statement is not long and we just use the main character to describe it. The story itself is easy to comprehend :)

For me who is afraid of number theory, this is good news to be happy about. If there is a math problem, I am also ready to change to the alternate.

Tester — Planning to participate in the next div 1.

sshwyR — You already tested it.

Tester -

SpoilerIt's the round we tested 3 months ago and didn't knew when it will be scheduled. Many of us found we tested upcoming round (and hence cant participate) by looking at our names in the announcement.

MeToo

This contest was put on hold for a long time due to the difficult Di2A.

difficult Di2AThank you , now excuse me while I go to sleep for 35 hours real quick

Go for 40 , than that would be sacrilegious

Two set violin=small ppBass=pp largeWhat? You bass gang, had some arguments before, but now is just butthurt, VIOLIN > bass. TwoSet responded to all Davie's videos, but Davie just ignored the "bass diss track" (which was asking for a livestream at the end) and the "davie fakes playing the violin". Brett played bass poorly, but it was REAL, but Davie, on the other hand, FAKED playing it. So what side is winning, huh?

Oops, difficult Di2A. So scary....

Is this difficult div2A? Then what about the contest, which was for Russian elementary school students, with a 1700 rating problem A. (it was like 10 contests before) :D

Feeling sad for such testers but they will get contribution.

Well I knew I wont participate in one div1 when I was testing. Anyways I did participated but in unrated mode. Just that I didnt knew I wont be participating on 12 Aug.

SpoilerMost testers vc contests before round.

Another Chinese Round! This round has special and interesting stories.Good luck and have fun for every contestants. Some information in advance:Those stories may all be about one mysterious person.

[O)]-[(O]/

Should i wear mask and senetizer during contest??

You can if you are comfortable

Is the man @MikeMirzayanov ? <3 i have not any guess about his income but i love him and want to see his name in the problem statement ..

no no no

Mukesh Ambani???Boss Cai!!

WoW

boboniu!

Are you talking about me?

Wow!

I am almost sure this man is Jack Ma.

I want to know what is Polygon platform ? Strange word for me

A platform for making problems

https://polygon.codeforces.com/

Polygon in basically the platform for creation of programming contest problems. It also supports problem statement writing, test data preparing, model solutions, judging and automatic validation.

I know! The man is Cai Rui[user:Boboniu]!

Intersting fact: tourist will set a new best rating ever on codeforces if he wins this round!

Legends don't care about rating (¬_¬ )

but we care about legends rating :)

Chinese Round?

Fun fact: seeing MiFaFaOvO can't participate in this round, if he doesn't in the next global round, he will vanish from the live standings xD

And "poof": he is gone xD

Excuse my ignorance, but what is the rule exactly you're talking about?

Only the users which participated in a rated round within $$$6$$$ months will be included in the

`Rating Standing`

.The last rated round for him took place on $$$Feb^{17th}$$$.

Oh. Didn't know that about the 6 months rule. Thanks!

I guess it's CCF

Totally agree!

Coin Collecting Federation (

I do CP for fun.. What about you guys?

I do CP for codeforces, and codeforces for the memes.

For practice.

BINOD !

Please don't spam Codeforces at least. There are many who don't know the context and it gets annoying after a while.

Alright . Apologies!. Will be careful next time.

It's Mr-Cai!!! Hahahaha

When I see Chinese round, I think of Mathforces.

hhh... don't worry, I promise it'll not gonna be Mathforces.

This round will not be math round, so please feel free to compete.

Mathforces confirmed

I love mathforces

Nope! Just FST Forces!

so... Yet another maximizing profit problems ... or Yet another guessing name problems :v

Ronan Ryan?

interestingLSY Time for your picture about boboniu!

Ah-oh, jqdai0815 as a tester, which means we can't see his competition with tourist this time. A huge pity!

Either way ,he will never compete against tourist ,after the time he gained 1st spot . He just prays for some bad luck for tourist ,so that he can remain on top.

Before that ,i Never thought ,such legendary grandmaster would ever fear to directly compete against someone. But anyway that someone tourist is not ordinary guy.

Don't comment others at will.

？？？？？

Don't comment on Lagendary Grandmaster subjectively!!!

No one would like to be commented like this

But It's still an interesting and exciting contest

Yeah

He must be Zide Du(杜子德) from the CCF.

China Computer Federation or China Collecting-money Federation?

Is him, right ?

Please provide short statements for problems and understandable english,I am learning english .Thanks

Copy to baidu translate (

Website: fanyi.baidu.com

[Deleted]

You take slander as freedom?

You should know it's not polite to comment others like that

Freedom is not your excuse for slandering.

Although it is your right to express your own ideas,but your last comment was unsuitable indeed in some way.And codeforces delete your comment for a great many people downvote you.I think it is reasonable.

See this 89567737

What's happening to "timeanddate.com"? :|

The website works well for me, probably it's because of your network problem.

And I don't think these sorts of comments are meaningful here

as#holes

Excuse me is there anything wrong?

Boss Cai -- boboniu

Orz.

Makes lots of money everyday. That must be dzd from CCF(China Collecting-money Foundation)!

I became psychopath because of the little pony, please make sure that the problems have short statements. with appreciation to your great story.

The little pony turned you psychopath?

..

I really hope that the problems are not as hard as the quiz.....

How many number of common problems ?

Richie Rich?

It could be suneo's dad from doraemon xD

is it jeff bezos ?

Olers?

Realy, what is an Olers?

Olympic of Information ers

It's what Chinese called people who participate in Olympic in Informatics contests.

Is that man Mark Zuckerberg??

The Man is:Rick Sanchez with Jerryboree Idea

Is the man Mike Mirzayanov ?

JPow?

Money printer goes brrrrrhhhhhh

If there are unnecessary stories, please, do mark them in Italic or any other way. I've faced a lot of issues about bad storytelling in Codeforces. :)

What are "Olers"?

The people like us. Take part in OI. OI, Olympics Information. OIer, the people learn OI. OIers is plural form of OIer. Understand? :)

I'm not good at English. I hope you can understand xD

OIers are coders who participate in programming competitions (mostly used in China I guess). OI = Olympiad Informatics

It's what Chinese called people who participate in Olympic in Informatics contests.

The goalkeeper of RCD Espanyol, click the link for more details.

https://www.transfermarkt.de/oier-olazabal/profil/spieler/8176

Since Wu Lei (the best football player in China) is also in this team, we use the word "Oier" to show our respect to RCD Espanyol so that they pay Wu Lei on time.

i guess Jack Ma .

I guess he's kkksc03, head of Luogu(an oj in China). For every monthly contest in Luogu, if you want to watch the video tutorial, you must pay 10￥ first. And what's more there's lots of OI online lesson made by Luogu in every summer and they're not free! So he can make lots of money in this way.

Actually, according to himself, the money is not paid to him directly and a lot of money is spent in maintaining Luogu's website. And the lessons' money will be given to the teachers. So I'm very sure that it's not him.

Any hint about no of common problems or score distribution ?

Score Distribution?

Obviously,the man is DUZIDE:P

Score Distribution?

Sorry for the late publishment of score distribution :)

I have a request for MikeMirzayanov.. can we have TEAM contest at codeforces.

Team contests are a nice idea, CodeChef already have it though, it's called "LONG challenge"

Long challenge isn't a team challenge

I agree. XD

It's €€£

sshwyR how many problems will be common in both divisions?

I guess there are 4.

D2A->D2B->D1A/D2C->D1B/D2D->D1C/D2E->D1D/D2F->D1E

upd: When I saw the scoreboard I knew there are only 3 but I forgot to update QAQ

3 D1A=D2D,D1B=D2E,D1C=D2F

3

Thank you!

Auto comment: topic has been updated by sshwyR (previous revision, new revision, compare).Today's tester busy with increasing their contribution .

Div2 Problem E with 1750 (^_^)...it should be solvable

obviously rating < 1900, i guess.

E was a bit difficult :/

iam not a tester, but please upvote for my pp :).......

i see ,no feature to upvote pp ? that's why you can't upvote it :( leel

I upvote

The man must be, President of IOI: Richard Forster

Zhengru IOI will be internationalized.

Karuna! :D

An off-topic question: how can I view the past contests right before contests?

Change the url. It will by default have contestId of the present contest, just remove that and you will be good to go.

When I access to https://codeforces.com/contests/ , it automatically redirects to https://codeforces.com/contests/1394,1395 .

There is an asterisk sign below the upcoming contest tab that states , that to view the complete list click here.

Ah, that was the link I didn't know! Thanks a lot.

But when you are already on https://codeforces.com/contests/1394,1395, you can just delete from the link 1394,1395. For me it works. And of course you can use method mentioned by absr007.

its boboniu

Too much if else... :(

Normal Div1:

Try to solve more problems

Horrible Round #664 Div1:

Try to solve the first problem faster

No,you should try to avoid FST instead of solving problems faster. It's my final standing:

(I was rk128 before the system test...)

If I accept no question am i still rated?

why they set so hard

Was this the "Single Test Case" Contest?

Really nice problems and clear statements. Enjoyed taking this contest :D

Codeforces rounds are great, they teach us how to look at a problem in a simple manner, without overcomplicating it. orz Great contest.

Well well well, once again someone posted solutions on youtube during the contest, you can even see his username in the video, i wonder if these guys are shameless or what Video link Username: Khayrulmithu

I don't know why but that video sounds exactly like an airline pilot's announcement.

And he got it wrong on test 10 :D

I really liked d1 B, but...

Starting fromanyvertex uThis would be much more understandable if it said from

allvertices. Wasted lots of time solving the wrong problem.That could confuse people into thinking that it's possible to start from multiple vertices simultaneously, I think the clearest is "for all vertices u, starting from u, ..."

I'm pretty sure that "any" was actually used correctly here

What was the point of swapping X and Y in Div2B?

I got -4 because of that

Same thing bro, same thing.

Ikr, I got 2 WAs cause of that, had to rewrite it all.

Does this works for Div-2 E — Make a graph $$$g[i][j][k]$$$ = how many edges exist such that its head is on node with $$$i$$$ outgoing edges and tail is in node with $$$j$$$ outgoing edges and it is $$$k'th$$$ smallest one. Then we brute force every $$$c_i$$$. That will be $$$O(k!k^2)$$$

The whole round is like an ingenuous play of

MiFaFaOvOto get back his first place in the rating (though unsuccessful). Chinese people are really good at the art of war. My respect.(please don't take this very seriously)

"There are two ways to go higher, self improvement, and sabotaging literally the entire community"

He has made his choice.

(Jk no offense pls :)

Seems his plan worked

Why the "non-empty" in C? I guess it has to do with printing the output but it reduced problem quality by like 30%.

could u plz xplain how to solve todays div2 C problem

You do realize that I haven't read Div 2C?

ok..if someone other can help..bcz..i am very curious about it..that why my logic was wrong..even on sample test cases ..i know i was completely wrong.can not wait till editorial..xD

rank 1 guys code is very clean to understand.

Might as well allow output of negative length to boost problem quality?

Empty strings make sense, strings of negative length don't.

OH SHIT I missed it. Even my starting answer is an empty string. Luckily my code goes for large strings first when improving the cost in binsearch, so I got AC.

Is C checking if a cube like shape fits all of the given points by binary search / math?

Yes!But I am too weak at geometry,I come up with this idea quickly but don't know how to compute the area covered by several polygon...

Maintain the minimum and maximum values of $$$N$$$, $$$B$$$, and $$$N - B$$$.

Yes,but does it turn into a geometry problem??

Depends on your definition of "geometry" I guess. I didn't really use any "geometric" techniques. But yeah, you can visualize the things as hexagons.

No need to compute the area. Just find a point inside it.

Yes,But how to compute the point inside it?

Several polygons? I think it reduces to finding the minimum side length of the square in a shape like this that can fit all the points, which should be fairly easy. But I spent most of the contest thinking I had to minimize the sum of distances instead of the maximum, so I couldn't implement it in time.

Rather diamond-like (with top-left and bottom-right edges cut). Math seems awful there.

How to solve Div2C? Also, where does the N^2 check all pairs approach go incorrect?

Final Answer can be at most $$$2 ^ {9}$$$, so just brute force for every possible value, and pick the smallest.

Thanks.

Do you think there a polynomial-time solution in case final answer is large?

I have O(n^2 log m), where m is the size of the largest input integer.

Figure out how many leading zeroes we can get by picking greedily the pairs where the bitwise-and has the most leading zeroes, using O(n^2) time. The next bit has to be a 1 in any solution, so we can add that bit the the answer. Since the bit will be a 1 in any case, we can ignore is from now on: we set it to zero and find out again how many leading zeroes we can now get. Repeat until we can get all zeroes.

https://codeforces.com/contest/1395/submission/89696109

Your implementation is too elegant :)

I solve this wayNow I feel like an idiot,spend half an hour in implementing an dp solution..:/

Hey can we solve problem C it using Dp??

I tried some approach but its giving wrong ans.

Can you explain this approach?

My english is so bad.sorry.if you understand its my pleasure <3Very clean aproach, fix the answer and check there are N pairs a[i]&b[j] that has the same bit positions. I spend 1 hour until I reach my dp aproach...

Is 1C a geometry problem? I thought it just need to binary_search and compute the area covered by several polygon..

I passed the pretests in Div2B with a backtracking solution, how is that a thing?

Hints for $$$Div 2 E$$$ Please?

Assume you have selected a tuple. Of course, you can now reduce the initial graph to one such that each node has out-degree of 1. Realise that for each node to be in a cycle in this resulting graph (and thus be possible to reach back to it in finite time), each node must also have an in-degree of 1.

For each node (let it be Q), traverse over all nodes that point to it, let's call these set of nodes P. You can easily determine that for which value in the tuple will these nodes in P be pointing to Q. Also, this means that these values can not co exist in the tuple, since that would mean that multiple nodes point to Q in the resulting graph. Thus, you make a list of all these invalid combinations.

Iterate over all K! tuples, and for each check if they consist of an invalid combination. If not, then it is valid.

Sadly, was a bit late while implementing in contest :(

Here's my AC code: https://codeforces.com/contest/1395/submission/89731507

What's the upper bound of the number of those invalid combinations?

By an invalid combination, I mean pairs $$$((i, j), (k, l))$$$ such that value $$$j$$$ at index $$$i$$$ in the tuple, and value $$$k$$$ at index $$$l$$$ in the tuple, are incompatible. So the maximum number of such invalid combinations are $$$K!(K!+1) / 2$$$.

You just have to store all these pairs in a $$$K*K*K*K$$$ matrix.

Thanks a lot.

1250 not enough points for Div.2D

Long Long in problem A just ruined my whole contest.I almost wasted 50min behind it.

In Div2C, Sample test 3, what combinations get the final result as 147? The minimum I could get was 177.

I think you applied the dp approach. I did the same thing at first and waste a lot of time. just brute force the answer

I think this was the combination

Spoilera b

0 2

1 2

2 2

3 2

4 3

5 4

6 1

7 2

these are indices of the element from array a and b

I also got the same error during the contest but now I understand. Well, let's say our solution consists of two parts, 1 and 2. I am not going to explain the second part assuming you already know it.

But in the first part, u must be choosing a minimum c1 among all possible c1 and then doing part 2 of the solution but we are doing a mistake here. Actually, part 1 of the solution has n possibilities. Choosing minimum c1 is just one of the possibilities. A second possibility, for example, can be choosing a minimum c2 and then doing part 2 of the solution. Similarily choosing a minimum c3 among all possible c3 can be the third possibility and so on. So there are n possibilities.

So the solution is O(n^3) and not O(n^2). wicardobeth

i will fst in d,One detail was not considered,shit.

That was implementationforces, I like that. Should be enough to become blue again :)

What was the solution to D?

Greedy.

Edit, more understandable: We devide $$$a[]$$$ into set $$$a[]$$$ and $$$b[]$$$, where all $$$b[i]<=m$$$ and all $$$a[i]>m$$$

Sort both sets biggest element first.

Then choose consecutevly to use i elements from a[]. Foreach i we can calculate how much elements from b[] can be used then, and using prefix-sum calc in O(1) the funfactor of that i.

If only I had two more minutes to fix my implementation

Figured that, but couldn't implement. Thanks, will wait till I can see your submission.

I am used to see you in blue ;)

How to solve div2 D?

1) Make 2 lists: one of all greater than m (let us call it gr), second all less than m(let us call it sm). 2) Sort gr reverse and sm normally. 3) Now compare highest unused of gr with sum of d consecutive of sm. If gr highest is greater than simply add that to ans(in other words muzzle d smallest elements of sm). Take care of these things: 1) Do the above only till you have atleast 1 element left in gr, cause you can add it in the end. 2) If you encounter condition like less than d elements remaining in sm, then dont compare with gr greatest element as you can add all remaining along with greatest, if greatest goes in the end. 3) In the end try to put all remaining elements of gr in the end of the permutation seperated by d elements each. For details see the code: 89725326 If I fail system test ignore this comment :D

thanks!

https://codeforces.com/contest/1395/submission/89731791 I also came up with similar approach but got WA on test 16. Seems like there is something we are missing.

Can anyone please tell me what's wrong in my code? Problem A https://ide.codingblocks.com/s/308173

try 0 0 2 2

Thanx a lot

Can someone tell me why this solution to 1C is wrong?89722745

I can't find the mistake :(

Oh now I find it

I forgot one line

`if(zmin>zmax) return 0;`

:(Boboniu stands nowhere in front of Binod

Any Idea of Test 16, Div1 B ?

How to solve Div-1 B??

Need help, why did my solution for Div2B did not pass ? I have used dfs- https://codeforces.com/contest/1395/submission/89714645

.

Problem A: What is the

problemwith my thispythoncode?I decremented min(r, g, b) from

r,g,b.Then count how many of them areoddfrom r, g, b, w. If number of odds > 1 the answer is "No", else "Yes".Sorry for bad English.

What if input is 2 5 7 3. Now if u decrement r g b by 2, then r b g will be 0 3 5 and w will be 9.

No.of odds will be 3 (0 3 5 9)..so it return "No"

But if I remove only 1 from r g b then r g b will be 1 4 6 and w will be 6. (1 4 6 6), we can form a palindrome.

Decrementing min(r,g,b) is wrong step.

Can someone give a small hint for 'B'?

As far as I understand:

1) The requirement "should be able to return back" is equivalent to:

= edges that satisfy Ci-rules should form loops

= every vertex should be a part of a loop

= every vertex should have an active edge coming in — this is what we need to check

2) k <= 9 so 1*2*3*4*5*6*7*8*9 = 362880 total sequences of Ci.

If we were able to somehow check whether a specific sequence is good fast, than we could just enumerate all sequences and count the good ones.

Am I correct with (1) and (2)? If no, a small hint would be appreciated.

Isn't the total number of sequences = k^9?

No, since c_i <= i, not c_i <= k

No, because 1 <= C[i] <= i

Remember, C[i] — is the index of the edge you would take if there are 'i' outcoming edges. This index can't be say 7 if there are only 3 outbound edges.

Sufficient and necessary condition is that each vertex has exactly one incoming edge. Everything else in your

`(1)`

follows.I build a bruteforce on top of that withprecomputation which pairs of (i, c_i) are incompatible, because they lead to some vertex having two incoming edges

P.S. It's pretty standard Markdown, so use two spaces before newline

like this

How do you prove that?

Necessary is obvious — no incoming edge, no cycle for that vertex.

Sufficient: start from vertex and start moving. At some point you will have to return to starting vertex.

If a node $$$x$$$ has no incoming edge, it's impossible to reach $$$x$$$ starting from $$$x$$$.

If a node $$$x$$$ has indegree $$$\geq 2$$$, let $$$a, b$$$ be two nodes such that edges $$$(a, x)$$$ and $$$(b, x)$$$ exist. But if you start from $$$x$$$ you can't reach both $$$a$$$ and $$$b$$$ (wlog, if you reach $$$a$$$, you return to $$$x$$$ and you haven't visited $$$b$$$); in this case, if you start from $$$b$$$ you reach $$$x$$$ at the next step and you can't go back to $$$b$$$.

what if there is an edge (a, b) along with (a, x) and (b, x) ? Then can't it be the case such that: x -> ......... -> a -> b -> x. ?

There can't be both (a,b) and (a,x)

Then how to check if some node has no incoming edge?

Each assignment $$$c_i = j$$$ will guarantee incoming edges for some number of vertices. If you sum this up over all assignments you make, just check that it adds up to $$$n$$$.

The issue is that this can double count, however note that each vertex should have

exactlyone incoming edge, not more, so each assignment $$$c_i = j$$$ will exclude some other list of assignments $$${c_{i'} = j'}$$$. Just make sure to never make two conflicting assignments like this.You have

`n`

edges, so it's enough to check that no vertex has two incoming edges. Precompute 'bad' pairs`(i, c_i)`

,`(j, c_j)`

, such that some vertex will have two incoming edges.Simple bruteforce after that.

You are correct with both (1) and (2).

Here's a good hint. Imagine that for a certain tuple of C, we get the edges 1-2,2-1,3-4,4-3. This is equivalent to saying that nodes [1,2,3,4]->[2,1,3,4] which is a permutation! How can you use this insight to solve the problem in general?

Agnimandur kilotaras thanks! Solved!

The core idea is to:check that each vertex has no more than one incoming edge.

This will automatically guarantee that each vertex has exactly one incoming edge.

And I've spent the contest trying to figure out how to check if each vertex has at least one incoming edge. At the end, turns out I needed to check the exact opposite.

Though I looked at other solutions I still try to figure out how other people solved it without using 4d array of pair-incompatibility [9][9][9][9].

I thought the exact same thing and could not determine how to check every possible sequence in an optimized way.

Does anyone know if there is a testcase on Div1B which breaks the hashing solution for the MOD 1e9+7?

Very nice problemset, reminded me to practice.

[deleting this because it came out wrong. I'm referring to Chinas efforts in testing all of Wuhan, which is amazing, not them experimenting and creating the virus (which I think is false).

I can't delete this, so if some CF mod could for me that'd be great.

the use of "muzzle" in problem A felt rather odd.

tourist RIP rating

FAILED TEST 31 IN C? GOING BACK TO DIV4.

I am surprised by the number of high-rated coders who do not realize that in Div1B, the in-degree of each node can be up to O(n), and iterating through pairs of nodes which go into a particular node can take quadratic time in the worst case.

I am also surprised that there was no pretest against such solutions. But I think this is fair. Contestants are responsible for ensuring that their solutions' time complexities are acceptable.

Pretests were way too weak, just look at the amount of failed submissions in Div1 ...

My finish in Div1 went from 556 to 366 because of failed submissions :D

What the hell were you guys thinking. I don't usually get mad, but now I am mad. This contest honestly has made me not want to do cf anymore

lol test 31 is ruining everyone's day ig

Absolutely disappointed

my disappointment is immeasurable and my day is ruined

My only question is why?

Weak Pretests :(

WHYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY

You could've said all of this in 1 comment?

Good point

AYAYAYAYAAYAYAYAYAAAYAYAYAYA AYA AYAY A YA YA YA PSY PSY PSY PSY DUCKDUCKDUCKDUCKKK

So many main tests failing

250+ Submissions failed TEST 31 of DIV2 C FST Forces!

850+

My rank literally jumped from 1700 to 1300

Me from 3200 to 12000+ SO GOOD to know!

Worse pretests ever.

89726386 here is my solution for D, it for some reason gave no output nor any errors. its probably a silly mistake, but i cant find it. could anyone help please?