By vintage_Vlad_Makeev, history, 5 years ago, translation,

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

• +57

| Write comment?
 » 5 years ago, # |   +332 Mike during the contest ... "The round is declared semi-rated because no one thanked me for the platforms".
•  » » 5 years ago, # ^ | ← Rev. 3 →   -8 if codeforces had emojis like facebook's, i would give you "haha" instead of upvote
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Where does that semi-rated meme came from?
•  » » » 5 years ago, # ^ |   -63 from your smart head, bro
•  » » » 5 years ago, # ^ |   +4 There was a 1/2 rated contest because queue.
•  » » 5 years ago, # ^ |   +3 Sorry for off-topic but...why your nick is displayed in grey?Newbie Hasan with Contest rating: 1638?How is it possible?Is it just me? Or others are also seeing this?
•  » » » 5 years ago, # ^ |   0 You can change your color from 1 Jan to 10 Jan ... see it in your profile, a tab called magic.
•  » » » » 5 years ago, # ^ |   +3 wow... it's great!
 » 5 years ago, # | ← Rev. 2 →   +72 Tomorrow we'll have 2 El Clasicos: -> Real Madrid — Barça * -> Codeforces — AtCoder *
•  » » 5 years ago, # ^ |   -15 Barca(DIV1)-Real Madrid(Div2) :p
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Both of them are good.
•  » » » » 5 years ago, # ^ |   -10 Today its Real Madrid's Bad Luck nothing else.
•  » » » » » 5 years ago, # ^ |   -33 Real Madrid is shit.
 » 5 years ago, # |   +114 I'm concerned about one thing... How many problems were made by adamant, you say?
•  » » 5 years ago, # ^ |   +86 Why would you want to know that?!
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +8 Because we div2 candidates cannot can not expect much from the problems of red :p
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +19 I think he is asking because of the recent contest set by adamant. I, personally, really liked them, cheers!
 » 5 years ago, # |   -27 It is rated.
•  » » 5 years ago, # ^ |   0 It is not rated.
•  » » » 5 years ago, # ^ |   0 It is semi-rated.
 » 5 years ago, # |   -95 Help Post, Why my solution was getting WA? Problem My Solution.
•  » » 5 years ago, # ^ |   +7 there is auth
•  » » » 5 years ago, # ^ |   -17 what?
•  » » » » 5 years ago, # ^ |   +6 To see problem and submission, login & password are required
•  » » » » » 5 years ago, # ^ |   -35 hmm.so what?
•  » » » » » » 5 years ago, # ^ |   0 so me (and most other CF users) can't see your submission and review your code
•  » » » » » » » 5 years ago, # ^ |   -16 :'(. what can I do? bro?
•  » » » » » » » » 5 years ago, # ^ |   0 gist.github.compastebin.cometc
•  » » » » » » » » 5 years ago, # ^ |   +20 are you retard
 » 5 years ago, # | ← Rev. 6 →   +8 Why does the tourist not attend?
•  » » 5 years ago, # ^ |   +83 Because he is busy traveling
 » 5 years ago, # |   +7 Hoping short problem statement
•  » » 5 years ago, # ^ |   +28 Don't be racist bro.
•  » » 5 years ago, # ^ |   -33 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
•  » » 5 years ago, # ^ |   +5 Maybe the translator translated the problem by its pronunciation, like translate names.
 » 5 years ago, # |   +22 High ratings to everybody! What a sad story...)
 » 5 years ago, # |   +56 the truth is, i'm not getting out neither from the gray zone nor the friend zone -_-
•  » » 5 years ago, # ^ |   +23 getting out from the grey is easier =)
•  » » 5 years ago, # ^ |   +12 Watch fifty shades of grey.
•  » » 5 years ago, # ^ |   +5 Think twice code once, you could have been red.
 » 5 years ago, # |   +5 Any scoring distribution?
 » 5 years ago, # |   +23 The English translation for problem A needs some work.
•  » » 5 years ago, # ^ |   +6 I can assure you its wording in Russian isn't better as you would suppose.
 » 5 years ago, # |   +5 Why so long, man?
 » 5 years ago, # |   +11 This round is impossible, I can't understand half of the english.
 » 5 years ago, # | ← Rev. 3 →   +39 good job author !!!these nerds who are complaining about the tasks are just mad!!!
•  » » 5 years ago, # ^ |   0 Problems are interesting bro, but half of my time is used to understand the statements.
•  » » 5 years ago, # ^ |   +8 Your original comment complains about tasks, and then when you realize that is a popular opinion you change it lmfao.
•  » » » 5 years ago, # ^ |   0 yeah so i get dislikes
•  » » » » 5 years ago, # ^ |   +3 Looks like you failed
 » 5 years ago, # |   +7 reading the statements I feel like I must work on learning this type of English rather than coding ..really sucks!!
•  » » 5 years ago, # ^ |   +3 The same in Russian...
 » 5 years ago, # |   +9 RIP for problem statement __________/_____________
 » 5 years ago, # |   +16 In problem 1, the statement is not clear. May be add another example or make the explanation clear. Bad English translation.
 » 5 years ago, # |   0 I never met a contest like this. Such a large code work???
 » 5 years ago, # |   +11 Comprehending the questions seems harder than solving them :/
 » 5 years ago, # |   +7 English :p Your text to link here...
 » 5 years ago, # |   +58 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.
•  » » 5 years ago, # ^ |   +7 Please, clarify major mistakes in English in the problem A.
•  » » » 5 years ago, # ^ |   +4 I believe problem statement is enough clear for A. Though I haven't participated but read out the statement.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +54 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.
•  » » » » 5 years ago, # ^ |   +13 I also found this problem statement complex, I think many contestant did
•  » » » » 5 years ago, # ^ |   +3 I've spent the same amount of time for reading Problem A statement and solving Problem C completely.
•  » » » » 5 years ago, # ^ |   +1 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.
•  » » » 5 years ago, # ^ |   0 Maybe the problem is that it's too clear xD
 » 5 years ago, # |   0 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?
•  » » 5 years ago, # ^ |   0 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
 » 5 years ago, # |   +27 Is anyone else finding the problem statements a hell lot more confusing than normal CF rounds? :( :(
•  » » 5 years ago, # ^ |   +3 The Problem A definition really grinds my gears
•  » » » 5 years ago, # ^ |   0 I made 6 WAs this time in A itself :( :(
 » 5 years ago, # |   +12 Please tutorial good some provide links to lean English :/
 » 5 years ago, # |   0 worst contest ever
 » 5 years ago, # |   +7 This contest should at least be semi-rated. RIP English!
 » 5 years ago, # |   0 My first Div.1 contest!
 » 5 years ago, # |   0 Couldn't even solve A :(
•  » » 5 years ago, # ^ |   +24 masha as**** should not like fathers and mother car but like only child car.
•  » » » 5 years ago, # ^ |   0 S/H/I/T
 » 5 years ago, # | ← Rev. 2 →   0 This problem from a Korean judge seems quite similar to Div2F/Div1D, but the value of modulo in this problem is at most 106.
 » 5 years ago, # |   +5 How to solve C?
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   +10 I had the same idea, but how to prove it's always optimal to chose an adjacent vertex of the clique at each step?
•  » » » » 5 years ago, # ^ | ← Rev. 4 →   +5 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.
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Your DP solution is amazingly crazy. I can't believe it works
•  » » 5 years ago, # ^ | ← Rev. 5 →   +15 C can be solved in O(2n * n) with brute force. There is no need for DP. We can use the following observations to test whether a subset S of chosen vertices is valid: The order of choosing vertices in S doesn't matter. S is valid iff for every pair (u, v) there is a path from u to v that uses only vertices in S as intermediate vertices.
•  » » » 5 years ago, # ^ |   0 Didn't notice that the order doesn't matter. Thanks.
•  » » » 5 years ago, # ^ |   +1 How to verify that path requirement in O(n)?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 I used BFS. Start from any vertex in S and only push new edges to the queue if the current vertex is in S. Then check if every vertex was visited.
•  » » » » » 5 years ago, # ^ |   0 What if every person is friend to every other person ( Like when m = n * (n - 1) / 2 ) Then the answer is 0 and S will be empty. And can you please elaborate your algorithm? How will it run on graph like this : N = 5, M = 4Edges :1 — 22 — 33 — 44 — 5Thanks.
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 I had a separate check at the beginning of the program if(n==0 || m == (n*(n-1))/2) { cout << 0 << endl; return 0; } 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.
•  » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » » » » » 5 years ago, # ^ |   0 Oh. Thanks.
•  » » » » » 5 years ago, # ^ |   +5 Why is it linear in nodes, not edges?
•  » » » » » » 5 years ago, # ^ |   +3 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
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 it's so hard to see ur color...how did ppl make out u were askin div1/2 :P
 » 5 years ago, # |   +12 I quit
 » 5 years ago, # |   +7 Seriously, what in the world is pretest #7 for C? I can't think of any corner cases...
•  » » 5 years ago, # ^ |   0 Did you unmark letters on ? operation?
•  » » » 5 years ago, # ^ |   +1 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.
•  » » » » 5 years ago, # ^ |   +3 Statement said he only say correct letter at the end. So other '?' are shocked
•  » » » » 5 years ago, # ^ |   +3 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.
•  » » 5 years ago, # ^ |   +4 if something like this occurs". 25 unique characters"then you can find the required character.
•  » » » 5 years ago, # ^ |   0 Yes I took care of that case. Or at least I tried to.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 years ago, # ^ |   0 I also considered that case :\ Maybe my implementation went wrong somewhere. Thanks.
•  » » » 5 years ago, # ^ |   0 WTF like seriously he always guesses wrong -_-
•  » » » » 5 years ago, # ^ |   0 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.
•  » » » » 5 years ago, # ^ |   +4 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
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 27 . a . b . c . d ... . y ! z ? z
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 I was using two boolean arrays and simulating something like that, but perhaps it didn't work like I thought it did.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 some n. b! ab.... ?a
•  » » 5 years ago, # ^ |   0 Did you initially believed all characters to be a possible special character candidates. Only those mentioned in the strings are possible candidates.
•  » » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ |   0 I think it was when wrong letters are repeated in a word, or at least that was my case!
 » 5 years ago, # |   +1 How to solve B? (And if possible, please tell me how did you find that solution).
•  » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +6 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.
•  » » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 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.
•  » » » » 5 years ago, # ^ |   0 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.
•  » » » » » 5 years ago, # ^ |   0 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?
•  » » » » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ |   0 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
•  » » » 5 years ago, # ^ |   0 Any proof/intuition why that works?
•  » » » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 Fot the test "5 36", Your code prints 1 next to 37!
•  » » » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # | ← Rev. 2 →   0 Does randomize algorithm work in problem B (and maybe C)?And what are the deterministic solutions for these problems?
•  » » 5 years ago, # ^ |   +5 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.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Can you share some cases that your program need 6 seconds to run in problem B?Thanks a lot!
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   +8 315 315, 315 316, 1000 100Edit: I got TL on test 19 Edit2: div1 C AC with random
•  » » » » » 5 years ago, # ^ |   0 Remarkable. I should've thought of randomness.
•  » » 5 years ago, # ^ | ← Rev. 6 →   +5 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 = 2Unfortunately, I couldn't get it AC during contest, and this is harder than the randomized one. http://codeforces.com/contest/907/submission/33573025
 » 5 years ago, # |   +14 The gaming experience is very disappointing.
 » 5 years ago, # |   +13 I've decided to capture this historic moment. Never been so high in my life :)
•  » » 5 years ago, # ^ |   0 All the best for the sys tests :)
•  » » » 5 years ago, # ^ |   +6 Thank you! I see that there could be 2 possible pitfalls:1. Failed system tests2. Too many angry users that force the contest to be unrated ;)
•  » » » » 5 years ago, # ^ |   +3 I don't think the contest should be unrated. Even worse(server issue) contests like previous ed #34 and 450 were rated.
•  » » » » 5 years ago, # ^ |   +3 I feel your pain if it's the 2nd one :|But great job!!
•  » » 5 years ago, # ^ |   0 What's your solution to E btw?
•  » » » 5 years ago, # ^ |   0 I've greedily added new vertices. If the vertex v introduces 10 new edges and vertex u introduces 9 new edges, I choose the vertex v instead of u.This solution doesn't work by the way ;)33565564
•  » » » » 5 years ago, # ^ |   +2 oh wow! A greedy passed all pretests. Very weak pretests.
•  » » » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ |   0 yeah ... at least you got the chance to get a AC on E pretests . good for you !! and keep it up
•  » » » 5 years ago, # ^ |   0 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 ))
 » 5 years ago, # |   +8 Worst contest I have ever had :(
•  » » 5 years ago, # ^ |   +6 Yet.
 » 5 years ago, # |   +4 Did anyone solve div1B/div2D using random? I was thinkin about it but didn't dare to code it.
•  » » 5 years ago, # ^ |   0 I submitted solution that uses random, but I had a bug in my code and got hacked. I think it should work.
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 I generated solutions for n<=8&m<=8 using random, and solved for other cases :)
•  » » 5 years ago, # ^ |   +34 I did it without any if's repeat 10000 times: for every cell of the grid: choose a random not yet used number for this cell. If it can't be neighbours with number from cell above or on the left, choose a different number, and so on at most 10 times. If succeeded, move to the next cell. If not, try from the very beginning. 
•  » » » 5 years ago, # ^ |   0 how do you ensure that this will pass in the given time limit?
 » 5 years ago, # | ← Rev. 2 →   +7 Horrible problem statements. The worst contest ever. I wonder how some people understood Div 2 A correctly and got it accepted in first attempt.
•  » » 5 years ago, # ^ |   +3 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)
 » 5 years ago, # |   0 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.
•  » » 5 years ago, # ^ |   0 My idea was to use bitmask of friends.
•  » » 5 years ago, # ^ |   +1 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 be O(2n * n2 * log(22)) where n2 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/33579509Have I done anything wrong in my estimation of time complexity?
•  » » » 5 years ago, # ^ |   0 The number of subsets of size k is not 2n, 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.
•  » » » » 5 years ago, # ^ |   0 Yeah. Thanks.
 » 5 years ago, # |   0 For D, key idea is query(l, r) = query(l, min(l + magic, r)).
•  » » 5 years ago, # ^ |   0 How to do Div2 E?
•  » » 5 years ago, # ^ |   0 Looks nice, but why so?
•  » » » 5 years ago, # ^ |   0 In order to know what is you need to know what is and whether b ≥ φ(m). Iterating φ(m) pretty quickly becomes 1.
•  » » » » 5 years ago, # ^ |   0 I forgot what is phi(m) called can someone tell.
•  » » » » » 5 years ago, # ^ |   +3 Euler's totient function
 » 5 years ago, # |   +7 D is bullshit
 » 5 years ago, # | ← Rev. 2 →   +6 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.
•  » » 5 years ago, # ^ |   +13 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?
•  » » » 5 years ago, # ^ |   0 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?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +7 "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 has to like it. And since it is written that she liked only the 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.
•  » » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # | ← Rev. 2 →   0 How to solve Div1D?
•  » » 5 years ago, # ^ |   +5 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.
•  » » » 5 years ago, # ^ |   +6 And so? Exponentiation is not associative at all.
•  » » » » 5 years ago, # ^ |   +15 phi(phi(n)) <= phi(n) / 2
•  » » » » 5 years ago, # ^ |   +24 Why would associativity be needed ?We have (roughly) query(l, r, m) = wlquery(l + 1, r, φ(m)), and φk(m) = 1 for some k = O(log(m)).
•  » » » » » 5 years ago, # ^ |   0 http://codeforces.com/contest/907/submission/33570787 Why is this code giving wa?
•  » » » » » » 5 years ago, # ^ |   +3 That's what I've hidden in "roughly". Because aphi(m) + b is not always equal to ab, you should remember if numbers are larger than m or not, and normalize them to some number in the range [0;2m[In particular, you should return 1 and not 0 when m = 1.
•  » » » 5 years ago, # ^ |   +28 Doesn't that work only when a and m are coprime?
•  » » » » 5 years ago, # ^ |   +18 (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.
•  » » » » » 5 years ago, # ^ |   +23 Can you please prove the second equation?
•  » » » » » » 5 years ago, # ^ |   0 Don't know the proof, but read a hint somewhere. Refer Pg 49 of this
•  » » » » » » 5 years ago, # ^ |   0 Is the first equation easy to prove?
•  » » » » » » » 5 years ago, # ^ |   +1 See Euler's Theorem.
•  » » » » » 5 years ago, # ^ |   0 So I had everything ready including the fact that phi drops fast. Only didn't know this fact. :'(
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 5 years ago, # ^ |   0 isn't b = 0 a preety strange scenario?Let's say a = 2,b = 0 and m = 20 => phi(m) = 8then 2 ^ 0 mod 20 = 1but 2 ^ (8 + (0 mod 8)) mod 20 = 16
•  » » » 5 years ago, # ^ |   0 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
•  » » » 5 years ago, # ^ |   +13 But, is that not only true whenb > phi(m) and likewise b < 2phi(m) ???How will we maintain this ??
 » 5 years ago, # |   0 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?
•  » » 5 years ago, # ^ |   0 O(n) to check if each integer(representing each friend) has value 1<
•  » » » 5 years ago, # ^ |   0 yeah but to simulate new friendships you need to do M operation for each case. That's (n^2)*(2^n)
•  » » » » 5 years ago, # ^ |   0 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
•  » » 5 years ago, # ^ |   0 I had 2^n*n^2 lol. Try using bitset.
 » 5 years ago, # |   +11 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 comprehension plz.Too large statement just make us feel awful.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I couldn't agree more
 » 5 years ago, # |   +14 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".
 » 5 years ago, # |   0 How to avoid MLE in E? I took a matrix of size int[1<<22][22].
 » 5 years ago, # |   +8 Worst descriptions ever; Ambiguity everywhere.
 » 5 years ago, # |   0 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)
•  » » 5 years ago, # ^ |   0 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
•  » » » 5 years ago, # ^ |   0 How would your algorithm handle the cases (6,2) and (2,6)?
 » 5 years ago, # |   0 How to solve Div2/A :c
•  » » 5 years ago, # ^ |   +1 masha should dislike first 2 cars .
•  » » 5 years ago, # ^ |   +6 Read A. Understand it has many test cases and I will probably fail systest anyway. Skip A.
•  » » 5 years ago, # ^ |   0 Bare (pun intended) in mind that you are given the size of the bears, not the size of the cars.
•  » » 5 years ago, # ^ |   0 just bruteforce it.
 » 5 years ago, # |   +30 I have no interest in solving these problems.
 » 5 years ago, # |   +180
•  » » 5 years ago, # ^ |   +30 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.
•  » » » 5 years ago, # ^ |   0 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?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +12 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 not give 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".
•  » » » » » 5 years ago, # ^ |   0 Yeah that's a very nice solution, thanks for explaining it :D
•  » » » » » 5 years ago, # ^ |   0 Could you explain how to calculate these probability?
•  » » » » » » 5 years ago, # ^ |   +6 There are ~m2n2 / 2 pairs of people in total and ~2mn are 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 roughly
•  » » » 5 years ago, # ^ |   +31 It was a huge hint to see first two ACed solutions both working in 1.9 seconds :)
•  » » 5 years ago, # ^ |   +6 You are a funny guy!
•  » » 5 years ago, # ^ |   +4 Being libertarian? :D
•  » » » 5 years ago, # ^ |   0 It's from the original :p
•  » » » » 5 years ago, # ^ |   0 REALITY
•  » » 5 years ago, # ^ |   0 You only need to handle 3 case: m > 4 n > 4 m, n ≤ 4 The first two has deterministic solution, the last one can be done using randomization.
 » 5 years ago, # |   0 I think this round is Reading comprehension-Dead do(loop without any algorithms)
 » 5 years ago, # | ← Rev. 2 →   +1 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 ???
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I tried your test case and it should've been a TLE.
•  » » 5 years ago, # ^ |   0 overflow haha, i didn't think about it
 » 5 years ago, # |   -8 Shiiit this B and A
 » 5 years ago, # |   +20 Thanks, for the fastest system test.
•  » » 5 years ago, # ^ |   +2 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
 » 5 years ago, # |   +2 I kindly recommend that you should rename Codeforces "Readforces."
•  » » 5 years ago, # ^ | ← Rev. 2 →   +9 In comparison to other judges Codeforces has the simplest language.
•  » » » 5 years ago, # ^ |   0 At least for this contest, I wonder it's the "simplest."
 » 5 years ago, # |   0 This guy used multiple accounts. { ethereum, yerkimbekov }Have a look MikeMirzayanov
•  » » 5 years ago, # ^ |   +1 He should be banned. sub1 sub2++lolkek :P
•  » » » 5 years ago, # ^ |   +1 look at this KAN
 » 5 years ago, # | ← Rev. 2 →   0 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?
•  » » 5 years ago, # ^ |   +1 Well, it's wrong answer because Masha can't get into the son bear's car.
•  » » » 5 years ago, # ^ |   0 But, the size of masha is 100, it can easily get into son bear's car according to the question. As, 100<=100
•  » » » » 5 years ago, # ^ |   +1 Ohh...Sorry...Maybe, the answer is wrong because Masha likes not only the smallest car?100 * 2 >= 198.
•  » » » » » 5 years ago, # ^ |   +1 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.
•  » » 5 years ago, # ^ |   +1 This is wrong because masha liked only the smallest car. But in your case, she also likes the medium and large car.
•  » » 5 years ago, # ^ |   +1 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
•  » » 5 years ago, # ^ |   +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.
•  » » 5 years ago, # ^ |   0 Oh My bad did not see only in the question.Thanks Guys
 » 5 years ago, # |   0 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
•  » » 5 years ago, # ^ |   -17 Привет, Всеволод)NumbHits++ нужно делать не всегда, а только если он уже мог угадать
•  » » » 5 years ago, # ^ |   -14 Рад тебя видеть!Но... Я ведь вывожу не NumbHits, a NumbHits — NumbNeed. Как только в массиве Litter[] остаётся ровно одна буква, я кладу NumbHits в NumbNeed и больше не меняю...Тут в другом проблема...Функция Evolution() на тесте 2 вообще не запускается. Если добавить вывод в её начало, на экране ничего не появляется.И массив себя на тесте 1 странно ведёт... В нём либо все ноли, либо все единицы.
•  » » » » 5 years ago, # ^ |   -10 Функция evolution() во втором тесте запускается прекрасно, но есть пара недочётов. Первый баг, который я поправил, чтобы пройти второй тест, состоит в том, что, когда чувак неправильно угадывает букву, ты просто увеличиваешь количество ударов, а надо этот символ прочитать (без сина идёт дальнейший сбой) и в массиве Litter обнулить. Сравни свою посылку и мою 33576279
•  » » » » » 5 years ago, # ^ |   -11 Спасибо огромное!
•  » » » » 5 years ago, # ^ |   -15 Если тебе интересно, то вот 33576931 полностью исправленное решение
 » 5 years ago, # |   +17 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.
 » 5 years ago, # | ← Rev. 2 →   +44
•  » » 5 years ago, # ^ |   0 You just don't know the original version of the conditions))
•  » » » 5 years ago, # ^ |   0 you mean [original version of the] statement, right?
 » 5 years ago, # |   -8 rated . ?
 » 5 years ago, # |   0 Auto comment: topic has been updated by vintage_Vlad_Makeev (previous revision, new revision, compare).
 » 5 years ago, # |   0 Why my output is wrong? (Div2A)input: 99 50 25 49My Output: 99 99 49Judge Output: 100 99 49
•  » » 5 years ago, # ^ |   +1 The largest car should be strictly larger than middle one
•  » » » 5 years ago, # ^ |   0 Thanks.. :)
•  » » 5 years ago, # ^ |   +1 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.
•  » » » 5 years ago, # ^ |   +3 Thanks.. :)
•  » » 5 years ago, # ^ |   +1 father bear car should strictly larger then mother bear.
•  » » » 5 years ago, # ^ |   0 Thanks.. :)
 » 5 years ago, # |   +18 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.
 » 5 years ago, # | ← Rev. 3 →   +3 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.
•  » » 5 years ago, # ^ |   0 Me too
 » 5 years ago, # |   0 div2eI don't understand why this output -testcase 1- is wrong?!2 2 4after 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.
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 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.
 » 5 years ago, # |   +16 I was screwed up at the testcase n=1,m=1 (Div.2 D)
 » 5 years ago, # |   -43 Worst Contest ever!
•  » » 5 years ago, # ^ |   +11 Don't cry
 » 5 years ago, # |   0 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
 » 5 years ago, # |   +3 My rating has been 1900.. I do not know should I be sad or happy :-)(
•  » » 5 years ago, # ^ |   0 if in next contest (<1900).i think you will change your dp color.
•  » » 5 years ago, # ^ |   0 I had 1900 two times and it was ideally for perfectionist, but i am not a perfectionist, haha
•  » » » 5 years ago, # ^ |   +8 1899 is "more perfect" for me. With 1899, you are the best of experts. You know, Expert.
 » 5 years ago, # |   0 In problem ATEST Case : 100 99 98 100 Output should be : 200 198 196Because They can climb 100 < 200 AND 99 < 198 ANS 100 < 196They 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 trueSo why the system give WA and give -1 instead of this solution ?
•  » » 5 years ago, # ^ |   0 In your example, Masha will love the car of mama-bear, but it should not be
•  » » 5 years ago, # ^ |   0 But she can't like the middle one and the largest one
•  » » 5 years ago, # ^ |   0 I spent all the contest time in one problem because the statement is unclear :/
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +12 It's clear as hell!
 » 5 years ago, # |   +61 AshishYadav are true now :)
•  » » 5 years ago, # ^ |   +6 Congratulations! :)
 » 5 years ago, # |   +5 Div2A: For input 100, 99, 98, 100 can someone tell me why 200, 198, 196 is not a correct answer?
•  » » 5 years ago, # ^ |   0 Masha can't like the middle one and the larger one
•  » » » 5 years ago, # ^ |   +8 Jeez! Thanks.
•  » » » 5 years ago, # ^ |   +5 Finally got an AC on this with some neat code, but it's too late :(33575063
 » 5 years ago, # |   0 DIV2 people(Pupil) who don't understand problem A and getting low rating :p Your text to link here...
 » 5 years ago, # |   +5 Auto comment: topic has been updated by vintage_Vlad_Makeev (previous revision, new revision, compare).
 » 5 years ago, # |   0 Can anyone explain why the following formula is true, and how to use it to solve D? when b > phi(m)
•  » » 5 years ago, # ^ |   0 Is that (mod m) over the whole power or on just b?
•  » » » 5 years ago, # ^ |   0 a^(phi(m) + (b mod phi(m)))
•  » » 5 years ago, # ^ |   0 Assumption, m = p * q, Where p is as large as possible such that gcd(a, p) = 1. Applying Euler's theorem for modulo p. For modulo q, because b > φ(m) so the remainder always is 0. That is the purpose of plusing φ(m) in φ(m) + b mod φ(m),
•  » » » 5 years ago, # ^ | ← Rev. 4 →   0 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 a is divisible by all the prime factor of b, ax will be divisible by b when x is 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 ?
•  » » » » 5 years ago, # ^ |   0 The rest is quite clear. ab ≡ aφ(m) + b%φ(m) modulo p, q. Because gcd(p, q) = 1) so done?
•  » » » » » 5 years ago, # ^ |   0 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)
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 5 years ago, # ^ |   0 This solution doesn't seem to be using the property you mention but still gets AC. :/
•  » » » 5 years ago, # ^ |   +3 It actually used the property. Check the mul void in the code.
•  » » » » 5 years ago, # ^ |   0 Ah yes, thanks!
 » 5 years ago, # |   +5 Auto comment: topic has been updated by vintage_Vlad_Makeev (previous revision, new revision, compare).
 » 5 years ago, # |   +19 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: Once upon a time, there was a little girl named Masha. Onу day she went for a walk in the forest. Pretty soon, she came upon a house. She knocked and, when no one answered, she decided to walk right in. At the table in the kitchen, there were three bowls of porridge. She tasted the porridge from the first bowl. “This porridge is too hot!” she said. So, she tasted the porridge from the second bowl. “This porridge is too cold,” she said. So, she tasted the last bowl of porridge. “Ahhh, this porridge is just right”. After the meal Masha decided to have some rest and went into the living room. There she saw the three chairs: large, smaller and the smallest. Masha sat in the first chair and fell from it. “This chair is too big!” she exclaimed. So she sat in the second chair. “This chair is too big, too!” So she tried the smallest chair. “Ahh, this chair is just right,” she said. But just as she said this, the chair broke! Then Masha decided to take a nap and went to the bedroom. She lay down in the first bed, but it was too hard. Then she lay in the second bed, but it was too soft. Then she lay down in the third bed and it was just right. Masha fell asleep. As she was sleeping, the three bears came home. “Someone’s been eating my porridge”, – growled the Papa bear. “Someone’s been eating my porridge”, – said the Mama bear. “Someone’s been eating my porridge and they ate it all up!” – cried the Baby bear. “Someone’s been sitting in my chair”, – growled the Papa bear. “Someone’s been sitting in my chair”, – said the Mama bear. “Someone’s been sitting in my chair and they’ve broken it”. – cried the Baby bear. They decided to go to the bedroom. Papa bear growled: “Someone’s been sleeping in my bed”. “Someone’s been sleeping in my bed, too”, – said the Mama bear. “Someone’s been sleeping in my bed and she’s still there!” – exclaimed Baby bear. Masha woke up and saw the three bears. She jumped out of the window and ran away. 
•  » » 5 years ago, # ^ |   +3
•  » » 5 years ago, # ^ |   0 interesting but i don't think this problem was a good idea to introduce your culture to others! maybe an easier one:)
 » 5 years ago, # |   0 In Div2 B, the problem statement says '.' will be found where there is no 'x' or 'o' but if you check your submission you can see they are passing underscore '_' instead of a period. To find this go to your submissions and click on this problem. Anybody face the same problem?
 » 5 years ago, # |