Hi all!

This weekend, at 14:05 UTC on December 23rd we will hold Codeforces Round 454. It is based on problems of Technocup 2018 Elimination Round 4 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup 2018 website and take part in the Elimination Round.

I would like to thank veschii_nevstrui, adamant and DPR-pavlin who authored and prepared problems for Technocup and ifsmirnov, Kostroma, winger, AlexFetisov, 300iq for testing the round.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

Congratulations to the winners!

Technocup:

Div. 1:

Div. 2:

**UPD:** Editorial

Mike during the contest ... "The round is declared

semi-ratedbecause no one thanked me for the platforms".if codeforces had emojis like facebook's, i would give you "haha" instead of upvote

Where does that semi-rated meme came from?

from your smart head, bro

There was a 1/2 rated contest because queue.

Sorry for off-topic but...

why your nick is displayed in grey?

Newbie HasanwithContest rating: 1638?How is it possible?

Is it just me? Or others are also seeing this?

You can change your color from 1 Jan to 10 Jan ... see it in your profile, a tab called magic.

wow... it's great!

Tomorrow we'll have 2 El Clasicos: -> Real Madrid — Barça * -> Codeforces — AtCoder *

Barca(DIV1)-Real Madrid(Div2) :p

Both of them are good.

Today its Real Madrid's Bad Luck nothing else.

Real Madrid is shit.

I'm concerned about one thing... How many problems were made by adamant, you say?

Why would you want to know that?!

Because we div2 candidates cannot can not expect much from the problems of red :p

I think he is asking because of the recent contest set by adamant.

I, personally, really liked them, cheers!

It is rated.

It is not rated.

It is semi-rated.

Help Post, Why my solution was getting WA? Problem My Solution.

there is auth

what?

To see problem and submission, login & password are required

hmm.so what?

so me (and most other CF users) can't see your submission and review your code

:'(. what can I do? bro?

gist.github.com

pastebin.com

etc

are you retard

Why does the tourist not attend?

Because he is busy traveling

Hoping short problem statement

Don't be racist bro.

I know that most probably I will not be able to solve D and higher in Div2, though I will try to solve.So if these problem statements will be huge I will never mind :D

Maybe the translator translated the problem by its

pronunciation, like translate names.High ratings to everybody! What a sad story...)

the truth is, i'm not getting out neither from the gray zone nor the friend zone -_-

getting out from the grey is easier =)

Watch fifty shades of grey.

Think twice code once, you could have been red.

Any scoring distribution?

The English translation for problem A needs some work.

I can assure you its wording in Russian isn't better as you would suppose.

Why so long, man?

This round is impossible, I can't understand half of the english.

good job author !!!these nerds who are complaining about the tasks are just mad!!!

Problems are interesting bro, but half of my time is used to understand the statements.

Your original comment complains about tasks, and then when you realize that is a popular opinion you change it lmfao.

yeah so i get dislikes

Looks like you failed

reading the statements I feel like I must work on learning this type of English rather than coding ..really sucks!!

The same in Russian...

RIP for problem statement __________/_____________

In problem 1, the statement is not clear. May be add another example or make the explanation clear. Bad English translation.

I never met a contest like this. Such a large code work???

Comprehending the questions seems harder than solving them :/

English :p Your text to link here...

After reading problem A's statement, I'm not sure what I've actually learnt in 10+ years studying English...

Can't understand a thing.

Please, clarify major mistakes in English in the problem A.

I believe problem statement is enough clear for A. Though I haven't participated but read out the statement.

I was over-reacting a bit while commenting this. My apology (if it upsets you).

In general, this problem statement is kind of... confusing.

At first, as my expectation (like 95% of the Div2A problems I've come across), I go straight into the examples and criteria, and I was like "3 cars? wait then 4 variables... what is the last bear doing?"

Then I looked up a little bit.

`Masha came to test these cars. She could climb into all cars, but she liked only the smallest car.`

"Alright, so the cars are there in a way that only the smallest one satisfy Masha, others either can't be climbed or Masha doesn't like them..."

`A family consisting of father bear, mother bear and son bear owns three cars. Father bear can climb into the largest car and he likes it. Also, mother bear can climb into the middle car and she likes it. Moreover, son bear can climb into the smallest car and he likes it. It's known that the largest car is strictly larger than the middle car, and the middle car is strictly larger than the smallest car.`

Three similar sentences, consecutively. I don't know what others may think, but its repetitive state made my head almost freeze.

A few thoughts clouded my head, such as "wait can papa bear climb on mama bear's car?", "can mama bear climb on papa's?", etc.

This is not what most of us expect in the easiest problem for Div2. I know my point may be biased, but it's mostly intended to be solvable for almost everyone in quick succession, so one should not make the statement open up a whole possibility for confusion and needs for clarification like this.

Then I made it to the conditions for liking/being able to climb a car:

`It's known that a character with size a can climb into some car with size b if and only if a ≤ b, he or she likes it if and only if he can climb into this car and 2a ≥ b.`

Took me about 3-4 more minutes to understand (at first glance it seemed like the two inequalities contradicted each other).

To be fair, it was not some critical errors in spelling, or grammar. The problem lies in the expressions — to me (or at least it is me during bad mood, but I won't think other people share this coincidence with me) it is somewhat unnatural and it may jam contestants' comprehending speed.

Lastly, thanks for directly responding to my comment. I was a bit astonished when seeing the notification.

I also found this problem statement complex, I think many contestant did

I've spent the same amount of time for reading Problem A statement and solving Problem C completely.

I agree. I delayed more than 20 minutes to understand the statement and it is pretty simple. I don't know why exactly but It is made in a way it makes it hard to understand.

Last week in usaco I didn't solve any problem but read and understand all of them in less than 10-20 minutes that was the time I delayed to read this problem in this case.

Maybe the problem is that it's too clear xD

Third pretest is not correct by the game rules because players cant make such moves (in the middle square) without touching middle positions of all squares, but the output of this pretest shows that the right code doesn't give a f*ck to such errors, so WHAT THIS TASK WANTS?

Read the line about the hare. It doesn't matter if the current structure is possible or not, you just have to tell the next possible move

Is anyone else finding the problem statements a hell lot more confusing than normal CF rounds? :( :(

The Problem A definition really grinds my gears

I made 6 WAs this time in A itself :( :(

Please tutorial good some provide links to lean English :/

worst contest ever

This contest should at least be semi-rated. RIP English!

My first Div.1 contest!

Couldn't even solve A :(

masha as**** should not like fathers and mother car but like only child car.

S/H/I/T

This problem from a Korean judge seems quite similar to Div2F/Div1D, but the value of modulo in this problem is at most 10

^{6}.How to solve C?

dp[mask] = minimum number of steps to get clique consisting of vertices in mask.

Now iterate through each member of mask (provided mask is reachable state) and try to get him to the next step. It is profitable only if vertex has some neighbour outside of mask — it also means that he could have not been selected yet.

I had the same idea, but how to prove it's always optimal to chose an adjacent vertex of the clique at each step?

You choose any of the vertices already in mask and you compare dp[mask + neighbours] with dp[mask]+1.

In every optimal solution for mask, one of it's vertices had to have been chosen as the last one. We take the optimal vertex and it's neighbours out and the state for the remaining subset is already optimal.

Edit: You can't select a vertex wchich have set of neighbours (and itself) disjoint with the rest, as it could not construct a clique. dp[mask] is the minimum number of steps to make masks a clique. If you select some 2 disjoint sets there is no way of connecting them, so mask will not be a clique, hence you always have to choose a vertex which is part of the existing clique.

Your DP solution is amazingly crazy. I can't believe it works

C can be solved in

O(2^{n}*n) with brute force. There is no need for DP. We can use the following observations to test whether a subsetSof chosen vertices is valid:Sdoesn't matter.Sis valid iff for every pair (u,v) there is a path fromutovthat uses only vertices inSas intermediate vertices.Didn't notice that the order doesn't matter. Thanks.

How to verify that path requirement in O(n)?

I used BFS. Start from any vertex in

Sand only push new edges to the queue if the current vertex is inS. Then check if every vertex was visited.What if every person is friend to every other person ( Like when

m=n* (n- 1) / 2 ) Then the answer is 0 andSwill be empty.And can you please elaborate your algorithm? How will it run on graph like this :

N= 5,M= 4Edges :

1 — 2

2 — 3

3 — 4

4 — 5

Thanks.

I had a separate check at the beginning of the program

For the your example case, it would look something like this:

- While trying all subsets, we currently have

S= {2, 3, 4}- Start BFS from 2, add 1 and 3 to queue

- Visit 1

- Visit 3, add 4 to queue (not 2 as it's already visited)

- Visit 4, add 5 to queue

- Visit 5

- Now that the BFS is finished, check that all vertices are visited. They are, so update the best subset to be

S.What if

S= {2, 4}?Then you will be visiting all the nodes although 1 and 5 cannot be friends.

Correct me if I have mistaken something.

Steps would be as shown:

- Visit 2, push 1 and 3

- Visit 1, nothing pushed as it's not in

S- Visit 3, nothing pushed as it's not in

SQueue is now empty and not all nodes have been visited

Oh. Thanks.

Why is it linear in nodes, not edges?

Yes, BFS runs in O(V+E) == O(E), however this is still fits quite comfortably into the time limit, with my solution running in ~300ms. 33578496

it's so hard to see ur color...how did ppl make out u were askin div1/2 :P

I quit

Seriously, what in the world is pretest #7 for C? I can't think of any corner cases...

Did you unmark letters on

`?`

operation?If I currently don't know the letter, and it gives me "? x", How will I know if he is shocked or not? I decided to make it the former and only then it passed pretests but I am not convinced that this is right.

Lot's of ambiguity in this round.

Statement said he only say correct letter at the end. So other '?' are shocked

Because you're guaranteed to know the answer at the end only.

`It is guaranteed that last action is a guess about the selected letter. Also, it is guaranteed that Valentin didn't make correct guesses about the selected letter before the last action.`

if something like this occurs

". 25 unique characters"

then you can find the required character.

Yes I took care of that case. Or at least I tried to.

If the query is of third type and it is not the last one, then the guess is wrong.

So we need to eliminate that character too from the set of possible characters.

I also considered that case :\ Maybe my implementation went wrong somewhere. Thanks.

WTF like seriously he always guesses wrong -_-

yes, until the last query.

`It is guaranteed that last action is a guess about the selected letter. Also, it is guaranteed that Valentin didn't make correct guesses about the selected letter before the last action.`

It's not that he always guesses wrong. It is only that if he guesses right, the game is over. So every guess before the last one will be wrong

27 . a . b . c . d ... . y ! z ? z

there is no edge case in it . just make two set one of which contain all the character that can't be hidden character and another contain all the possible values of hidden character.and at any time if size of possible values set become 1 or size of impossible set become 25 , then we can uniquely determine the hidden character.

I was using two boolean arrays and simulating something like that, but perhaps it didn't work like I thought it did.

some n

. b

! ab

.... ?a

Did you initially believed all characters to be a possible special character candidates. Only those mentioned in the strings are possible candidates.

yes initially i considered all char possible then at each time when a string comes with '!' then i remove all the char which are in only one of them (string and possible set ) and put them in impossible.

I think it was when wrong letters are repeated in a word, or at least that was my case!

How to solve B? (And if possible, please tell me how did you find that solution).

I thought about looking at all permutations

O(n!) for small values.For bigger tables there should be some way to distribute values that always works.

I used chess coloring, then put all the white numbers to the left part of the table, and black to the right. Numbers with the same color obviosly aren't neighbors, so we just have to find n pairs of numbers with the different color, which aren't neighbors. For m > 4 that is easy ( for example, choose white numbers with j = 1 or 2, and black with j = m or m — 1). For m <= 4... some hardcoding.

So, the point is, if I see problem about cells that aren't neighbors, I use chess coloring.

Yup, I did the same thing, but I failed to account for the case of a tall and skinny matrix, because I was initially doing it row-by-row.

From what I understand, suppose n =5 , m =5 ;

so, white cells = {1, 3, 5, 7, 9, ...., 25}, and black cells = {2, 4, 6, ... , 24} ;

Putting the white numbers to the left part of the table means, filling the matrix column by column, i.e. filling in this order -> {a[1][1] ,a[2][1],... , a[5][1], a[2][1], a[2][2],...), until we have exhausted all the whites.

Have I understood it correctly?

Where are you filling the black cells? Do you just fill them right where the white cells end? Also, what do you mean by this -> "so we just have to find n pairs of numbers with the different color, which aren't neighbors" ?

Thanks.

Yeap, i fill them right where the white cells end. But there is a problem: in a new table there is n neighbors (or n+1, depending on n and m) of numbers with the different color, so they could be neighbors in the first table, so we have to fill these cells so this numbers won't be neighbors in the first table.

Got it. So, basically, when you were saying that we have to check n pairs of numbers, you were talking about the worst case scenario. Isn't it?

One other doubt. Why do we need to hard code the solution for lower values of m and n.

if (n *m == 1) { return "NO"; }

else {

We will do what you said above. If it is not possible to fill the array(i.e. we run out of possible black values to fill in the current matrix cell), we shall declare that there is no solution. Else, we have a solution.

}

Correct me, if I am wrong here.

if n < 4 or m < 4, Just checked for 1000 random permutations, if the answer existed or not .

For all other cases the answer will exist :

I found the smallest prime which did not divide m(which will be among the first 10 primes) and started placing the numbers at this gap.

Solution

Any proof/intuition why that works?

The intuition behind this was that if I am placing numbers at the gap which is a prime factor of m, I will get a smaller number around a smaller number. But I want it to be the other way round.

Suppose n = 4 m = 6 Placing at gap 2 — >

1.2.3.

4.5.6.

Placing at gap 3 — >

1..2..

3..4..

As you can see, that numbers are appearing below each other. To avoid this the gap shouldn't be a factor of m.

gap 5 — >

1....2

....3.

...4..

As you can see Numbers are not appearing below each other. But there's another case in which the gap may be a factor of n which is pointed below by Omar_Elawady. So we will place the number at a gap of the first prime which does not divide n*m.

Fot the test "5 36", Your code prints 1 next to 37!

Yes, you are right. I didn't think that through. The case you pointed out was that I haven't excluded the prime factors of n. In this case I am placing a numbers at a gap of 5, which is a prime factor of n.

So instead of placing numbers at the gap of first prime which does not divide m, we will have to place the numbers at the the gap of the first prime which does not divide n*m.

Does randomize algorithm work in problem B (and maybe C)?

And what are the deterministic solutions for these problems?

I got pretest passed with a random solution on problem B, but I do have a lot of pragmas. Without them it took at least 6 seconds in some cases. I tried to submit C but I had a bug in the implementation.

Can you share some cases that your program need 6 seconds to run in problem B?

Thanks a lot!

315 315, 315 316, 1000 100

Edit: I got TL on test 19 Edit2: div1 C AC with random

Remarkable. I should've thought of randomness.

I came up with the following deterministic solution: for n & m less than 3, the answers are hard coded, otherwise;

- for general case, initialize the original grid then rotate even rows 2 positions to the right and even columns 1 position to the bottom.

- Else if m <= 3, then rotate the even columns 2 positions to the bottom, and the even rows 1 position to the right.

- For cases where m = 1 or n = 1, I did a special handling by rotating each 3 consecutive elements, with step = 2

Unfortunately, I couldn't get it AC during contest, and this is harder than the randomized one.

http://codeforces.com/contest/907/submission/33573025

The gaming experience is very disappointing.

I've decided to capture this historic moment. Never been so high in my life :)

All the best for the sys tests :)

Thank you!

I see that there could be 2 possible pitfalls:

1. Failed system tests

2. Too many angry users that force the contest to be unrated ;)

I don't think the contest should be unrated. Even worse(server issue) contests like previous ed #34 and 450 were rated.

I feel your pain if it's the 2nd one :|

But great job!!

What's your solution to E btw?

I've greedily added new vertices. If the vertex

vintroduces 10 new edges and vertexuintroduces 9 new edges, I choose the vertexvinstead ofu.This solution doesn't work by the way ;)

33565564

oh wow! A greedy passed all pretests. Very weak pretests.

I wrote a dp solution but unnecessarily resubmit. I had the following error — I initialized my dp state to be 1 for the mask consisting of the vertex and all of its neighbours.

It is incorrect in case of isolated vertex and vertex with 1 neighbour — it should be 0 in this case as we don't add any new edges when we select such guy to the next step.

However the case with 1 isolated vertex or an edge are special cases handled by if and the rest of dp seems to ignore such states in an optimal solution. Is there a test, where initialising such values to 1 instead of 0 could provide WA?

Here is accepted submission.

yeah ... at least you got the chance to get a AC on E pretests . good for you !! and keep it up

Actually, I feel good about this systest failure, because there was nothing clever in my solution and it was just a leap of faith :)

I'd have been sceptical about my rating otherwise ))

Worst contest I have ever had :(

Yet.

Did anyone solve div1B/div2D using random? I was thinkin about it but didn't dare to code it.

I submitted solution that uses random, but I had a bug in my code and got hacked. I think it should work.

I generated solutions for n<=8&m<=8 using random, and solved for other cases :)

I did it without any if's

how do you ensure that this will pass in the given time limit?

Horrible problem statements. The worst contest ever. I wonder how some people understood Div 2 A correctly and got it accepted in first attempt.

the statement was correct, that's why.

I believe almost noone likes problems like this but it is good to get people who do not read the statement properly and assume things just to be some minutes ahead (this works lots of times for div2A)

I didn't get AC but my idea for div2 E was something like binary search on the ans, generate all combinations of size mid and check.

My idea was to use bitmask of friends.

Nice idea!

Although this approach is correct but it should TLE in my opinion (

however,it does not). I am quite skeptical about the time complexity of the approach. According to me, it should beO(2^{n}*n^{2}*log(22)) wheren^{2}is for checking if the generated subset is feasible and the log factor is obviously from binary search.Here is the AC code : http://codeforces.com/contest/907/submission/33579509

Have I done anything wrong in my estimation of time complexity?

The number of subsets of size k is not 2

^{n}, but . So even if you generated these subsets for all the possible sizes, your amortized time-complexity would still be . And because of the binary search, it becomes faster.Yeah. Thanks.

For D, key idea is query(l, r) = query(l, min(l + magic, r)).

How to do Div2 E?

Looks nice, but why so?

In order to know what is you need to know what is and whether

b≥ φ(m). Iterating φ(m) pretty quickly becomes 1.I forgot what is phi(m) called can someone tell.

Euler's totient function

D is bullshit

Problem A's english was very unclear. Masha needs to be able to ride all three cars but she has to dislike the first 2 cars and like the smallest car.

Problem B's english was awful. Though they gave me some clarifications in the end, but it was too late for me. After the clarification, I was like "This problem is nothing but the english killed it". This ain't the first time in CF that english has caused major upset in the contest. Please after this, let some normal (knows basic english) people view the statements before posting it for a live contest.

Sorry, but this contest sucked only because of poor english.

I found problem C interesting and passed the pretests but problem B made me suffer and could not complete it in time.

Don't know the situation with problem B, but I have no idea what is it that everyone dislikes about A. To me it seems like the problem is not English, but the fact that it requires a bit more thinking than the usual div2 A. In fact, English in this problem is absolutely fine.

Let's take a look at your complaint.

Here's your wording: "Masha needs to be able to ride all three cars but she has to dislike the first 2 cars and like the smallest car."

Here's problem statement: "She could climb into all cars, but she liked only the smallest car."

What new information does your wording provide? Why is it better?

Your problem statement says that Masha may not dislike those 2 cars. She does not like it and she does not dislike it. Yes, in some senses, you can say she likes only the smallest car which means she hates/dislikes rest of them. But it is not true always. It could be that she likes the smallest car and she doesn't like the rest ( not necessarily dislike those). This caused the ambiguity. If you ask other people they will say that they made their solution thinking that Masha has to like the smallest car and for the rest she may or may not like it. "She has to dislike the two big ones" is not mentioned explicitly.

did you get it?

"he or she likes it if and only if he can climb into this car and 2a ≥ b."

Pay attention to "if and only if" here. This means that when 2a >= b and a <= b, then she

hasto like it. And since it is written that she likedonlythe smallest one, it follows that the rest do not satisfy these constraints.If it's any consolation to you, the Russian statement uses exactly the same wording.

I would rearrange the problem statement in the following way.

First, define "climbing" and "liking" as in the problem, in order to give the problem statement a more logical ordering. (This isn't an English exclusive issue, this is an issue in the structure of the writing)

Then, explain problem statement with first and second paragraphs.

Second paragraph being in the past tense is very confusing, especially since what came before is in the present (Father bear can..., Mother bear can...).

Rephrase it as: "Misha needs to be able to climb into all cars, but only like the smallest car. Given sizes of the bear and Misha, determine if finding a set of car sizes is possible. If it is, print them."

I don't think the error in this problem was that it was intentionally misleading (certain problems do this very well). The problem statement was not misleading, but it was structured in such an illogical way that made it really confusing and tricky to understand.

How to solve Div1D?

Using Euler's theorem : (a^b) mod m = a^(phi(m) + (b mod phi(m)) mod m when b > phi(m), where phi(m) is Euler's totient function.

And so? Exponentiation is not associative at all.

phi(phi(n)) <= phi(n) / 2

Why would associativity be needed ?

We have (roughly)

query(l,r,m) =w_{l}^{query(l + 1, r, φ(m))}, and φ^{k}(m) = 1 for somek=O(log(m)).http://codeforces.com/contest/907/submission/33570787 Why is this code giving wa?

That's what I've hidden in "roughly". Because

a^{phi(m) + b}is not always equal toa^{b}, you should remember if numbers are larger thanmor not, and normalize them to some number in the range [0;2m[In particular, you should return 1 and not 0 when

m= 1.Doesn't that work only when

aandmare coprime?(a^b) mod m = a^(b mod phi(m)) mod m only holds when m and a are coprimes, but (a^b) mod m = a^(phi(m) + (b mod phi(m)) mod m always holds.

Can you please prove the second equation?

Don't know the proof, but read a hint somewhere. Refer Pg 49 of this

Is the first equation easy to prove?

See Euler's Theorem.

So I had everything ready including the fact that phi drops fast. Only didn't know this fact. :'(

Is there any other solution which is not related to this "magical" property? I believe that it is not really intuitive for ones who do not know about the property.

isn't b = 0 a preety strange scenario?

Let's say a = 2,b = 0 and m = 20 => phi(m) = 8

then 2 ^ 0 mod 20 = 1

but 2 ^ (8 + (0 mod 8)) mod 20 = 16

Seriously though, why isn't this better known? The only place I found this equation was in a question on SO: https://stackoverflow.com/questions/21367824/how-to-evalute-an-exponential-tower-modulo-a-prime/21368784#21368784

But, is that not only true when

b > phi(m) and likewise b < 2phi(m) ???

How will we maintain this ??

Time limit for Div.1 C was pretty good, really fast n^2*2^n(just the OR(|) operations) did not pass. How to solve it in n*2^n?

O(n) to check if each integer(representing each friend) has value 1<<n — 1. I think the order of making friends do not matter.

yeah but to simulate new friendships you need to do M operation for each case. That's (n^2)*(2^n)

I just ORed the current friend with all friends. That's the O(n). I mean... If the current friend is 2, and he's friends with 3,4,5 then OR 2's friendships on top of 3,4,5 person's friendships

I had 2^n*n^2 lol. Try using bitset.

I don't think those problem should appear in codeforces round(And problem A,B,C are all

horrible problem statements), because we have only 2 hours to solve them.Practice our idea instead of

Reading comprehensionplz.Too large statement just make us feel awful.

I couldn't agree more

I think problem A div2 needs to highlight some points, such as how Masha dislikes the first 2 cars.

Of course it was my fault for not reading the statements clearly, but it should give more of a "competitive programming" rather than "competitive problem reading".

How to avoid MLE in E? I took a matrix of size int[1<<22][22].

Worst descriptions ever; Ambiguity everywhere.

Was there a way to solve div1B without case bashing? There seemed to be so many cases I needed to take into account (1,1), (3,3), (N, M <= 3), (N=2,M>3), (M=2,N>3), (N=2, M=3), (N=3, M=2), (N,M >= 3)

try this. 4 cases: case 1: n > 3 || m>3 case 2 : n==3 && m==3 case 3 n==1 && m==1 case 4: none of above

How would your algorithm handle the cases (6,2) and (2,6)?

How to solve Div2/A :c

masha should dislike first 2 cars .

Read A. Understand it has many test cases and I will probably fail systest anyway. Skip A.

Bare (pun intended) in mind that you are given the size of the bears,

notthe size of the cars.just bruteforce it.

I have no interest in solving these problems.

If you don't have good idea then solving this problem is an ugly process, but once you realize that it can be done by random then it is completely fine.

I didn't know there is a random solution, all the ones I've seen are case bashes :P. While it's much better, it's still pretty ugly. What's the point of a problem where the solution is just hoping that random passes and implementing?

It's not that simple here. You need to have a good understanding whether random can pass or not. Here if I'm not mistaken probability that random permutation is fine is something like which is too small and trying random permutations will

notgive you AC. However number of bad pairs will be very small (~8), so you can get those bad guys and put them in random place and this process should end very quickly. In my opinion that's an interesting solution far from "let's write naive random and hope it passes".Yeah that's a very nice solution, thanks for explaining it :D

Could you explain how to calculate these probability?

There are ~

m^{2}n^{2}/ 2 pairs of people in total and ~2mnare neighbours in every arrangement. For a particular pair of neighbours in new arrangement prob that they were not neighbours in previous arrangement is ~. Of course these events are not independent, but their independence is so little that prob that new arrangement is fine can be estimated as roughlyIt was a huge hint to see first two ACed solutions both working in 1.9 seconds :)

You are a funny guy!

Being libertarian? :D

It's from the original :p

REALITY

You only need to handle 3 case:

m> 4n> 4m,n≤ 4The first two has deterministic solution, the last one can be done using randomization.

I think this round is Reading comprehension-Dead do(loop without any algorithms)

for problem A, i wanted to hack this solution 33555103, but i could not because contest ended. i think this solution will get TLE on this test case: 100 49 20 5, ironically it got AC on system test ???

I tried your test case and it should've been a TLE.

overflow haha, i didn't think about it

Shiiit this B and A

Thanks, for the fastest system test.

there weren't that much of solutions to test and that is why it was fast,so you should thank for the shitty problems set

I kindly recommend that you should rename Codeforces "Readforces."

In comparison to other judges Codeforces has the simplest language.

At least for this contest, I wonder it's the "simplest."

This guy used multiple accounts. { ethereum, yerkimbekov }

Have a look MikeMirzayanov

He should be banned. sub1 sub2

++lolkek :P

look at this KAN

In Div2 Question A In 6th pretest i.e [v1 v2 v3 v4]=[100 99 98 100] why is the answer -1 ? and why is [200,198,100] wrong answer?

Well, it's wrong answer because Masha can't get into the son bear's car.

But, the size of masha is 100, it can easily get into son bear's car according to the question. As, 100<=100

Ohh...Sorry...

Maybe, the answer is wrong because Masha likes not only the smallest car?

100 * 2 >= 198.

Yeah, you are right,

The thing is masha only likes the smallest car.

But, here it likes the second car and the first one too.

Thank you for this.

This is wrong because masha liked only the smallest car. But in your case, she also likes the medium and large car.

Because the max size of mama bear's car is 198 and hence Masha will like mama bear's car. However, Masha can only like son bear's car. So answer is -1

Masha also likes the cars of father and mother bear as 200<=200 and 198<=200. He only has to like the son's car.

Oh My bad did not see only in the question.Thanks Guys

Help me, please!

I really can't understand, what's wrong with my program.

It seems like only getting N is happening in test 2, Evolution() is doing nothing...

Help me, please, to find out what's wrong. 33571490

Привет, Всеволод)

NumbHits++ нужно делать не всегда, а только если он уже мог угадать

Рад тебя видеть!

Но... Я ведь вывожу не NumbHits, a NumbHits — NumbNeed. Как только в массиве Litter[] остаётся ровно одна буква, я кладу NumbHits в NumbNeed и больше не меняю...

Тут в другом проблема...Функция Evolution() на тесте 2 вообще не запускается. Если добавить вывод в её начало, на экране ничего не появляется.

И массив себя на тесте 1 странно ведёт... В нём либо все ноли, либо все единицы.

Функция evolution() во втором тесте запускается прекрасно, но есть пара недочётов. Первый баг, который я поправил, чтобы пройти второй тест, состоит в том, что, когда чувак неправильно угадывает букву, ты просто увеличиваешь количество ударов, а надо этот символ прочитать (без сина идёт дальнейший сбой) и в массиве Litter обнулить. Сравни свою посылку и мою 33576279

Спасибо огромное!

Если тебе интересно, то вот 33576931 полностью исправленное решение

Sometimes poor problem statement, sometimes bad problem-set, sometimes not maintaining expected difficulty of certain problems, sometimes 20 minutes long queue, unrated, semi-rated contests — Codeforces is frequently failing to maintain its quality contests.

You just don't know the original version of the conditions))

you mean [original version of the] statement, right?

rated . ?

Auto comment: topic has been updated by vintage_Vlad_Makeev (previous revision, new revision, compare).Why my output is wrong? (Div2A)

input: 99 50 25 49

My Output: 99 99 49

Judge Output: 100 99 49

The largest car should be strictly larger than middle one

Thanks.. :)

It's known that the largest car is strictly larger than the middle car, and the middle car is strictly larger than the smallest car.

Thanks.. :)

father bear car should strictly larger then mother bear.

Thanks.. :)

Want to see some cheaters? Here are they: Edgration. and Anoxiacxy. Submissions for Div2 D: xlj's:33566367 and Zero_cxy's: 33564264. You can see that xlj replaced some parts of Zero_cxy like dfs -> asfkolasnhf, mt -> map_asfknas..., and Zero_cxy added a tree struct at the beginning but didn't use it to cheat. Those guys should be disquallified from this contest.

I think Codeforces server is having a few issues.

I've just received this announcement recently (one of my friends received it about 5 minutes before me).

In my opinion, this announcement must be presented long before, but for some reasons it won't pop-up in some users' browsers. Perhaps you should have a look.

Me too

div2e

I don't understand why this output -testcase 1- is wrong?!

2 2 4

after 2 introduces all of his friends to each other, all of 1 , 2 , 3 , 5 become friends. Then choose node 4 so all nodes are friends. Someone help me understand this please.

This is the initial graph (ignore the numbers outside of the circles, they were my drafts actually xD) After you choose guest 2, the link between 1 and 5 will be made. The similar applies to 3 and 5. (as 1, 3, 5 are guest 2's friends).

When you choose guest 4 afterwards, since he only has 3 and 5 as his friends, and they are friended already, no more links will be made.

2 and 4 are still not friended yet, so your solution is wrong.

I was screwed up at the testcase n=1,m=1 (Div.2 D)

Worst Contest ever!

Don't cry

now due to problem E, am trying to learn bm + dp. How to start it. i.e as of normal dp is concerned, first thing a brute force solution and then memoize it. But as for bm + dp, i looked into TSP. But there the brute force way is just factorial and it has nothing to do with the subset construction. I also looked into tutorials of hackerrank (Assignment problem). But i could not understand it. So can someone give a detailed explanation of how to approach bm+dp and how to solve it? TIA

My rating has been 1900.. I do not know should I be sad or happy :-)(

if in next contest (<1900).i think you will change your dp color.

I had 1900 two times and it was ideally for perfectionist, but i am not a perfectionist, haha

1899 is "more perfect" for me. With 1899, you are the best of experts. You know, Expert.

In problem A

TEST Case : 100 99 98 100 Output should be : 200 198 196

Because They can climb 100 < 200 AND 99 < 198 ANS 100 < 196

They can like also 100*2 >= 200 true 99*2 >= 198 true 98*2 >= 196 true

Masha can clim all of them and he can like the smallest one 100*2 >= 196 true

So why the system give WA and give -1 instead of this solution ?

In your example, Masha will love the car of mama-bear, but it should not be

But she can't like the middle one and the largest one

I spent all the contest time in one problem because the statement is unclear :/

It's clear as hell!

AshishYadav are true now :)

Congratulations! :)

Div2A: For input 100, 99, 98, 100 can someone tell me why 200, 198, 196 is not a correct answer?

Masha can't like the middle one and the larger one

Jeez! Thanks.

Finally got an AC on this with some neat code, but it's too late :(

33575063

DIV2 people(Pupil) who don't understand problem A and getting low rating :p Your text to link here...

Auto comment: topic has been updated by vintage_Vlad_Makeev (previous revision, new revision, compare).Can anyone explain why the following formula is true, and how to use it to solve D?

when

b>phi(m)Is that (mod m) over the whole power or on just b?

a^(phi(m) + (b mod phi(m)))

Assumption,

m=p*q, Wherepis as large as possible such thatgcd(a,p) = 1. Applying Euler's theorem for modulop. For moduloq, becauseb> φ(m) so the remainder always is 0. That is the purpose of plusing φ(m) in φ(m) +bmod φ(m),For modulo q, because b > φ(m) so the remainder always is 0Can you elaborate on this? What remainder that is "always 0"?

PS: Got it. Since

ais divisible by all the prime factor ofb,a^{x}will be divisible bybwhenxis large enough. (φ(m) is just a possible lower-bound, the actual lower-bound can be lower). Is that correct?PS2: Also, how to prove that if and , then ?

The rest is quite clear.

a^{b}≡a^{φ(m) + b%φ(m)}modulop,q. Becausegcd(p,q) = 1) so done?Got it. Turned out the last piece of proof that I'm missing is Chinese Remainder Theorem.

Thanks for your help. (I spent the entire morning just trying to prove this formula)

Only one clarification, when b>phi(m) may be exchanged for when b>log(m) I have an empirical not bounded proof, means that I can only prove that in some point that formula works. I unable to give a full proof of one of the two lower bounds, but the boths works nicely.

This solution doesn't seem to be using the property you mention but still gets AC. :/

It actually used the property. Check the

`mul`

void in the code.Ah yes, thanks!

Auto comment: topic has been updated by vintage_Vlad_Makeev (previous revision, new revision, compare).Actually, Problem A refers to the famous Russian folk tale about Masha and three Bears, that's why we have such a long statement. So, by solving this problem you can look at the part of out culture. Here is the original text: