Добрый день!
23-го декабря в 17:05 по московскому времени состоится Отборочный Раунд 4 олимпиады для школьников Технокубок 2018. Раунд будет длиться два часа, участникам будут предложены 6 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация (с 17:15 до 17:35).
Зарегистрироваться на Отборочный Раунд 4 →
Соревнование открыто для всех в виде отдельных раундов для первого и второго дивизионов.
Для всех участников всех трех редакций этого соревнования будет пересчитан рейтинг.
Параллельно с Отборочным Раундом будут проведены открытые раунды для обоих дивизионов, в них могут принять участие все желающие.
Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:
Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:
Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!
В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).
Спасибо veschii_nevstrui, adamant и DPR-pavlin за подготовку задач Технокубка. Также спасибо ifsmirnov, Kostroma, winger, AlexFetisov и 300iq за тестирование раунда.
Желаем удачи на олимпиаде,
команда Технокубка.
Поздравляем победителей!
Технокубок:
Div. 1:
Div. 2:
UPD: Разбор
Mike during the contest ... "The round is declared semi-rated because 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 Hasan with Contest 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!
Дароу друг)
I'll do it for you. Thanks to MikeMirzayanov for the great Codeforces and Polygon platform.
Технокубок от адаманта, да, это будет весело.
Всем удачи!
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 ____/_____
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 hell lot confusing more than normal CF rounds? :(
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 :( :(
worst contest ever -_-
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 106.
Неправильная разбалловка для D1B, D1C...
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(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:
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 S and only push new edges to the queue if the current vertex is in S. 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 and S will be empty.
And can you please elaborate your algorithm? How will it run on graph like this : N = 5, M = 4
Edges :
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 S
Queue 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.
what is problem A mean?
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://mirror.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 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
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 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://mirror.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 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.
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 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.
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) = wlquery(l + 1, r, φ(m)), and φk(m) = 1 for some k = O(log(m)).
http://mirror.codeforces.com/contest/907/submission/33570787 Why is this code giving wa?
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.
Doesn't that work only when a and m are 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 ??
Сегодня в маршрутке девчушка лет 4-х спросила маму: «А если всем попросить Бога, он выключит систесты?». С мамой плакала половина маршрутки… Боже, выключи систесты!!!
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.
Большое спасибо организаторам за интересные задачи!
У меня вопрос по правилам форматирования выводам и взломам. В правилах вывода в условии задачи Б сказано:
Если же она существует, то в первой строке выведите «YES» (без кавычек), а в следующих n строках выведите по m целых чисел — искомую таблицу.
Я заметил что участник выводит в некоторых случаях матрицу в транспонированном виде, что противоречит условию о n строках и m столбцах, но взлом не прошел. Жюри ответило, что формат вывода не важен:
Можно ли узнать подробнее, в каких случаях не важен формат вывода? Хотелось бы больше не попадаться и оградить себя от подобных потерь очков на взломах :)
Обычно игнорируются пробельные символы, ведущие нули и различия вроде
1.05и105e-2в вещественных числах. Иногда игнорируется регистр букв.То есть чекер вряд ли проверил и такую матрицу, и транспонированную. Он просто прочитал nm чисел из входа, как если бы они были выведены с правильными переводами, и расставил. Если бы тест был посложнее, вполне возможно, что участник бы получил с точки зрения чекера совсем не тот ответ.
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.
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, not the size of the cars.
just bruteforce it.
вот у меня в городе если вы знакомы, то это не значит, что вы друзья
это по условию, а по задаче: как решать div1C?
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 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".
Yeah that's a very nice solution, thanks for explaining it :D
Could you explain how to calculate these probability?
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 
It 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:
The 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
Помогите, пожалуйста!
Я не могу понять, что не так с моей программой?
Похоже, на 2 тесте происходит только ввод N, функция Evolution() не запускается...
Помогите, пожалуйста, выяснить, что не так. 33571490
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
Как можно было дать такую ущербную таску А дать??? (Див 2)
Как можно три фора не написать?
Как можно условие не прочитать?
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?
Is that (mod m) over the whole power or on just b?
a^(phi(m) + (b mod phi(m)))
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),
For modulo q, because b > φ(m) so the remainder always is 0
Can 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 
?
The rest is quite clear. ab ≡ aφ(m) + b%φ(m) modulo p, q. Because gcd(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
mulvoid in the code.Ah yes, thanks!
Auto comment: topic has been updated by vintage_Vlad_Makeev (previous revision, new revision, compare).
Что за прикол с победителем отбора?
Может, он зашёл гостем?
У пацана был ник GasTheKikes (Жидов в газовые камеры). Может повязали.
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:
https://en.wikipedia.org/wiki/Goldilocks_and_the_Three_Bears
interesting but i don't think this problem was a good idea to introduce your culture to others! maybe an easier one:)
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?
Сколько человек из основного раунда проходят в финал?
Ну блин. Валялся аккаунт полтора года, никого не трогал, решил поучаствовать в одном-единственном контесте — и вот те на. Как поменять хэндл? Я не антисемит, просто "GasTheKikes" — это первое, что мне в голову пришло, когда я ник придумывал.
Думать головой надо прежде чем что-то делать
??? Думать головой? Зачем?
11/10
Thanks to MikeMirzayanov for such a great platform and all the red coders who create such nice problems which i feel are great to improve not only our basic and fundamental skills of core CS but also thinking skills to great extent. but it seems that quality of the problems is decreasing now-a-days .
is there any editorial?
Is there any editorial?
oh thanks;)
What's wrong with codeforces again? Why nobody is on first place?
austrian_artist his page
Why did you disqualify GasTheKikes?
Why did you remove GasTheKikes , the winner?
Look up "kikes" on urban dictionary. And if you still not understand it, read about WW2 and the holocaust.
For Div2 E (or Div1 C) "Party", is there anyone that has passed it by using the following algorithm?
Lemma: A group of guests is available iff I. their friends cover all people II. without other people, they are still connected
So just use a bit-dp, generating all states and check that if each of them satisfies the lemma above, and choose one with the minimum number of people.
Total Complexity is O(2^n*n)
Of course one can do some pruning in the dp-process, and it'll be much quicker.
In particular, for each state(that is a bit-representation of people) I, maintain 2 data, one is whether it is connected (a bool), the other is their friend (using a int to represent it by bit-representation)
and just check every friend J of them who is not among them, and update the state I|(1<<J), set its "connected" to true, and set its "friend" to (friend of I)|(friend of 1<<J)
and when a state K, its friend covers all, then it is an available group of people, and one should use it to update the answer.
and it can be proven that the answer will have nothing to do with the order of the guests.
So it's O(2^n*n) in total.
Is it easy to prove the order is not important?
I think it's pretty easy though, don't know how is it to other people.
consider 2 series, representing the same people but in different orders, let's call it A and B,obviously A and B are permutations to each other.
consider an operation in a series, which is swapping 2 neighbouring person, and we can do some finite steps of such operations to transform series A into series B(like bubble sort).
so we just have to prove that in one such operation, their is no difference between the final outcome, and then, because A can transform to B by some finite steps of those operations, and in each steps, the outcome won't change, so in the end, A and B are equivalent in outcome.
and I'll prove that such operation won't make difference to the outcome. consider two series, satisfying series 2 is transformed by series 1 after doing one such operation. they'll have the formations as below: series 1: ab..zXYa'b'...z' series 2: ab..zYXa'b'...z' (swapping X,Y) when we have performed the common prefix ab..z, their outcomes are same. when a person P have introduced all of his friends to each other, the friends of only P's friend maybe changed, but the friends of any person who's not P's friend will stay unchanged. so if X and Y aren't connected currently, performing X will not change Y's friend, and what Y do next will be have no difference, so as performing Y first and X next,so there's no difference between ab..zXY and ab..zYX and if X and Y are connected currently, performing X will let all X's friends know each other including Y, and then performing Y will let all Y's new friends(from X) and Y's old friends(not from X) and X and Y, all know each other, the outcome is all of X or Y's friends including themselves knowing each other, and the friends of people who aren't X or Y's friends stay unchanged, so if we performing Y first and X next, it's the same outcome. so no matter whether X and Y is connected currenty, performing X then Y, is equivalent to performing Y then X, so ab..zXY is the same to ab..zYX after doing the common suffix a'b'..z', ab..zXYa'b'..z' is equivalent to ab..zYXa'b'..z' so it's proved that such operation won't make difference to the outcome.
Thank you! I had the intuition of your proof but I couldn't formalize it.
Could you, please, elaborate what do you mean by available?
And this.
I think he means that if you use that group then all people will be connected
a group guests that satisfied the constraints: after one by one they come to introduce their friends to each other, all people will be familiar with each other.
that's what I mean.
I've used google translation to translate the Russian version of editorial, and found the idea for this problem is just the same as I posted.
Where can i find the editorial?
enter the contest interface, and the link "Tutorial" is at the right-bottom corner.
When i click tutorial, it says "You are not allowed to view the requested page" What can I do?
oh I've just found what you said. the link is available earlier when I enter from it.
Is the editorial up?
System test for problem B (div 1) is too weak. For example, 33583372 this code will surely get TLE with
3 33333, in custom test it ran for ~6s.А почему у топ 1 нету хэндла?
Good contest, the problemset was perfect, We want more contests like this. but please use better problem statements.
You didn't even participate
and you did? by the way i read the problems.
LOL I didn't say I participated. You said this contest was good but you didn't solve problems in contest environment.
ok.
Why do you use "we" instead of "I"?How do you make sure it's everyone's feeling about the contest but not only yours?
Why everyone always complaint about Codeforces. But it is not only happening with you others are also facing it. I think it is due to you are not able to perform well in the contest and same is happening with me but complaining according to me will not solve that problem. Try to perform well in the contest. See people like KAN and other more who are red and even purple also. The difference b/w them and us is that they try to not commit the mistakes that they have committed earlier. I hope my message is clear to all and if u don't wanna give a shit to this then u are different :(
vintage_Vlad_Makeev Please upload the editorial.
div2e My approach is greedily pick the node that can create as many as possible edges among friends. Got Wrong answer on test 51 :'( Code: http://mirror.codeforces.com/contest/907/submission/33589732
a concise counter-example to the greedy algorithm you said above is like this: 9 13 7 8 8 9 9 7 7 1 7 2 7 3 9 4 9 5 9 6 8 2 8 3 8 4 8 5
(the answer will be: 2 7 9 ) that's because of the person 1 and 6, the person 1 just know 7 in the beginning, and 6 just know 9, so (7 or 1) and (6 or 9) must be chosen, and if you just choose 7 and 9, they will be an answer to problem, without 8(although initially he knows the most number of people comparing to 7 or 9)
When will we get the editorial ?
Where can I find the editorial of this contest?
Any plans of publishing the editorial in near future? :)
In div2 E what if m=0 then even if do operations in any order then also we can't make all of them know each other??
It's guaranteed that each pair of friends is described not more than once and the graph of friendship is connected.
please upload the editorial :/
For question 1 of div. 2 test 4 is input "99 50 25 49" my output is 99 50 25
which I think is correct because mama bear fits and likes her car, just like papa bear and Masha can fit into son bear's car because son bear's car-size limit is 50, and Masha is size 49.
The correct output is apparently 100 99 49 which is also correct as all bears and people can fit into their cars, but this is not the only solution and in the question, it is stated that "multiple answers are allowed" if you want the source code for my solution the link is https://pastebin.com/AK8yXQPN . Thank you for posting any solutions/ answers to my question.
Think about it: the problem asks you to output the size of the cars of the three bears. The condition is that Masha should be able to fit into all three cars (which means that Masha's size should be <= all three bears sizes), but only like the small car (which means that Masha's size *2 >= only the small bear's car's size). In your output, neither condition is met, since Masha (size 49) cannot fit into the small car (size 25) and Masha likes both the small car and mother bear's car (since 49*2=98 which is >= both the small and medium car)
Where exactly did the problem state that Masha should fit into all cars? It is implied that Masha HAS TO fit into all cars larger than her (including mama and papa's) and she does like the son's car.
Overall the question was very confusing in both languages (I read it in Russian and it made no sense at all) and it was the reason I was stuck on this one question for the whole round.
The same issue all of us are complaining about: badly written statements. I read the problem in English and it stated in the problem description.
"Masha came to test these cars. She could climb into all cars, but she liked only the smallest car"
I also got stuck in this one for the first 50 minutes of the contest.
so...random_shuffle works for D-Seating of Students, this is interesting.
Just random_shuffle doesnt work as I explained above and indeed I tried it after contest and it is too slow, as expected.
I have a question.
I send this 33572495 for problem A dive2 in problemset and got AC.
and output for this testcase is:
input : 100 10 9 15
output : 200 10 15
but answer is -1.
why this code got AC! :)
mabye the testcases are not strong enough
Yes I think too. :)
What is the answer to this test case of DIV 2 C
6
! codeforces
! hello
? e
! e
? o
? e
Why don't run on a AC Code!
Шото сложна
i think you should never publish an editorial if you want to keep this contest as the worst contest ever !!
I cannot wait to see the editorial!
Hope it will be published soon.
Can you Please publish the editorials?
Came for the tutorial again. Found nothing again.
Please upload the tutorial :( Thanks a lot
http://mirror.codeforces.com/blog/entry/56601?locale=en
Auto comment: topic has been updated by vintage_Vlad_Makeev (previous revision, new revision, compare).