Нам придется хранить два массива — для игроков хозяев и гостей. В каждом из них мы должны сохранять статусы игроков "чист", "желтая карточка" или статус "игрок удален". И с каждом вводом просто проверить — если игрок удален, то ничего не предпринимать, иначе менять его статус в зависимости от того какую карточку он получает и от его статуса. При получении красной карточки в любом статусе, или желтой, находясь в статусе "желтая карточка" игрок удаляется с поля, и печатается строка в стандартный вывод.
Надо делать то, что сказано в условии. Хранить двe vector-ы, в одном из них очки первого борца, а во втором — очки второго. Еще две переменные — в первом сумма всех очков, что дано в вводе, а во втором — кто выполнил последний прием. Если Sum всех не 0, то выводить номер борца, иначе пройти над векторами и проверить — имеются ли неравные элементы. При равенстве выводить ответ зависимо от того, кто выполнял последний прием.
Храним один большой массив pair-ов — дистанция бросков и кто это выполнил. Сортируем весь этот массив, потом предлагаем, что все броски — трехочковые. Потом пройдем над массивом, и зависимо от второго элемента на одно уменьшаем наши очки на единицу и сравниваем с наилучшим ответом и при необходимости меняем. В самом конце выводим ответ.
Заметим, что если n — нечетное, то черные могут сделать симметричные шаги относительно центральной линии — победив таким образом. А если n — четное, то белые могут ставить ферзь на поле (1;2) (что лексикографически наименьший возможный ход), никогда не входить в первую строку, и победить.
Рассмотрим две случая. 1) t!=1 и 2) t=1.
1) Если наша функция — разная от константа, то а больше всех коэффициентов, и в ответ может быть только представление числа b в а-ичной системе счисления. Еще и надо проверить — является ли константа решением?
2) при t=1 надо быть осторожнее:
при 1 1 1: ответ inf,
при 1 1 n: ответ 0
при 1 а, а^x(x-натуральное): ответ 1
при других случаях P(1) больше всех коэффициентов.
Super short editorial :)
Not necessarily a bad thing!
А я думал не надо... Вот почему упала...
HTML в помощь.
Надо, Федя, надо... А то будут вечно на первом тесте падать
Can anyone explain the case 2 in E when input is of the form: 1 a b and b!=a^x , then how should we proceed , i couldnt get a short and general answer for this one...
like the first case.
can barely understand what you are saying. "reduce our glasses" what is glasses??
It's points, may be score, something like that.
Can anyone explain the 2nd case in E when input is of the form: 1 a b, and b!=a^x ie a and b are some random numbers, how do we proceed in such a case. I couldnt derive a short and nice solution for this case.
Why u send this message 2 times?
By mistake i sent the first one in russian that didnt get posted..
No problems then)
Can you please explain D in little detail. Thank you in advance
Just do yourself for n = 2, 3, 4 ,5 ,6 and try to make white the winner. At the same time consider the fact that black is not dumb.
Thanks for posting editorial so fast!
97 minutes ago? What? Contest didn't even end by the time. Apparently that's a new feature to hide blogs, or you messed up.
Edit: Whoops, I messed up, sorry people.
*That's an old feature to hide blogs.
Is it contest too??? Why, problem D very simple, than A,B,C?
Because dynamic scoring...
Я один, кто задачу D решил вот так: "ой, как-то её быстро все решают, ну давайте вот такой иф зашлём. Если не зайдёт, подумаем ещё"?
Ну, там доказательство придумывается за 5 минут, все равно слишком просто
Tests that I used to hack problem B:
4 1000000000 1000000000 1000000000 -1
2 1 -1
2 -1 1
6 1 2 1 -1 -1 -2
There were many testcases that can be used to hack B and C. Unfortunately, no one hacked my obviously wrong solution. :(
Таких трололо задач я и не видел нигде, разве что на первое апреля
can somebody explain C, I cant understand what the editorial is saying
Lets have a massive of pairs — distance and team. Sort this, then suggest that all shots are 3pt — shots. Lets go from first to last element of massive, and using information about second element of pair we can decrease our answer by one and compare our answer with answer founded before.
P.S. Sorry for mistakes at this text :(
thanks but that explanation is no better than the editorial. Sort on what?, decrease 'score', what score, or d? using 'information' how do we use it?
You may have 3 arrays and all must be sortet by number. 1 array — the distances first comand throws. 2 array — the distances second command throws. 3 array — 1 array + 2 array.
So, the better distance is 0 or one of the number in 3 array.
You may go along 3 array, and calculate the number of elements in 1 and 2 array, wich are greater than current 3 array element. (All greater elements will give command 3 points, other — 2 points)
Sorry for my English=)
оказывается, в Д надо было лекс. мин. ход выводить xD
russian translation needs to be edited. for A:
` ~~~~~
Нам придется хранить два массива — для игроков хозяев и гостей. В каждом из них мы должны сохранять статусы игроков "чист", "желтая карточка" или статус "игрок удален". И с каждом вводом просто проверить — если игрок удален, то ничего не предпринимать, иначе менять его статус в зависимости от того какую карточку он получает и от его статуса. При получении красной карточки в любом статусе, или желтой, находясь в статусе "желтая карточка" игрок удаляется с поля, и печатается строка в стандартный вывод.
~~~~~
`
thank you ... I have edited it.
Is contest rated?
Why not?
I can't understand anything about problem E.
The editorial is awfully short and hardly understandable :(
For t!=1, P(P(t)) = b is just P(a) = b. Also recall that a polynomial looks like the base conversion formula, so we just convert b to base a (each digit in base a gives you the coefficient) and make sure the conversion works. Similarly, convert a to base t and make sure it works.
This breaks down for t=1 because you can't convert a to base 1, but when t=1, you can reduce it to a few cases and handle these individually. The case for t=1 is explained in more detail here: http://www.johndcook.com/blog/2012/03/27/polynomial-trick/
Polynomial need not always be a base conversion formula right ? P(a) can have coefficients >= a but base conversion has coefficients < a UPD : It can't. Because of the fact that P(t)=a :)
Ничего не понятно. Если вы действительно хотите помочь людям понять ваши задачи, а не отделаться от них, не могли бы вы хотя бы чуть-чуть поподробнее объяснить решения?
Автор не из России — поэтому у него проблемы с русским языком.
I submitted a correct solution at 37min for problem A. After that I submitted another correct solution at 1hour-20min for problem A. However the system skipped my first submission and accepted the second submission for testing. This affected the points earned. Is it possible to consider my first submision?
no read the rules
http://mirror.codeforces.com/blog/entry/456
Thanks. I resubmitted almost the same solution for the problem A after the announcement was made that:**You should output red cards in a chronological order. The statement will be updated soon**.
No.
if your solution gets hacked does that mean it would def. fail system tests?
Generally yes, but not always
hello, I need help, please.
I my submission of problem C. I get WA in test 11:
wrong answer 1st words differ - expected: '6:8', found: '0:0'But in my computer I get:
6:8Someone can explain me what happened?, pleaseTypo:
Which I only noticed when I tried compiling with -Wall -O and got a warning about BB being uninitialized.
aaaaaaaaaaaaaaaaaaaaaaa...
I corrected that and AC. :'-(
merolish thanks for your help.
I have submission on C with WA 3 8972083. Statements: "Print two numbers in the format a:b — the score that is possible considering the problem conditions where the result of subtraction a - b is maximum. If there are several such scores, find the one in which number a is maximum." Why on test:
answer is 15:10, but on test:
answer is 15:15. Why? Tests are similar.
a - b is maximum, not |a - b|.
Oh, I'm stupid and careless, thanks :)
Thank you for this interesting contest, statment of the problem A was a little bit fuzzy, I got it wrong answer twice during the contest, actually if a player got a red card, they would be sent off, and they properly won't continue playing, now I saw the test case which breaks my solution and it was
the same player is getting a red card twice, and that couldn't be true at all. It should be mentioned in the statment that, the player may receive multiple red cards
The player isn't receiving a red card twice. He committed a foul worth receiving a red card twice.
You're right, even though I read the problem statment many times, I couldn't get it . I wish the problem statment was more understandable, anyway it was my fault, I had to read the statment too carefully when I got it wrong.
If ever a foul can worth two red cards, they should be given at the same time.
My 'twice' refers to committing a foul.
Oh sorry, you are right.
This was a hint in problem statement:
Come on, people, are you really so silly?
Vasya is watching a recorded football match now and makes notes of all the fouls that he would give a card for. Help Vasya determine all the moments in time when players would be given red cards if Vasya were the judge. For each player, Vasya wants to know only the first moment of time when he would receive a red card from Vasya.
And it does make sense. Firstly he categorizes all fouls to yellow and red cards independently. And then he wants to know the time each player would be removed from the field if he would be a judge and give such cards sequence. And if a player was given a red card, he wouldn't get another card again from Vasya.
He should say it is not our known football. In football when a player takes red card he leaves match doesn't take red card again and again. Why didn't you say anything ?! Actually it is NOT football albertg.
He said if Vasya were the judge, the judge is not giving a red card, only Vasya believes that that foul is worth a red card, and so the player is not leaving the game, only Vasya believes that the player should leave.
Can anyone explain the solution for E ???
I believe this blog post will be helpful to many that are trying to understand the solution to E.
http://jeremykun.com/2014/11/18/learning-a-single-variable-polynomial-or-the-power-of-adaptive-queries/
What about adaptive queries for guessing real valued coefficient polynomials?
Лаконично однако :)
for the explanation for problem C, what does "and one of our numbers we decrease on 1" mean?? kindly elaborate..
I can't understand the solution to problem C can anyone re explain it to me?
Well, I can explain my solution.
Basically, if you can try all values of D, and simulate the scores, you can find the answer, no?
And then you notice that only changing the value of D to a value in team A or team B will change the result. For example, if there are no shots taken between the distances of 10-15, a D of 12 will have the exact same result as a D of 13.
Thus, there are only 2*200000=4*10^5 possible values of D. Now, to simulate the number of points faster than linear time, you only need to search for the number of shots that are below D, and the number of shots that are above D for both teams. This can either be done through binary search, or keeping track of a pointer.
I hope this helps. I didn't solve this problem during the contest due to not realizing that the shot distances didn't need to be unique.
thank you for the explanation :)
Thanks Chili,
I look at your submitted solution (8973140) and found two things: 1) complexity of the solution is O(nlog(n) +mlog(m)) because of sorting of both arrays, so it in this sense, it doesn't really matter whether is the rest linear or binary search; 2) I didn't find binary search, instead there are two for loops up to n and m, making the remaining part is linear — so either I missed something in your code, or you didn't implement binary search.
"This can either be done through binary search, or keeping track of a pointer."
You can notice that the value of the binary search will never decrease, so you can simply keep track of the last index that works, and increment it until it works again.
My solution ends up being O(N) complexity.
I am sorry, but it cannot be O(N) complexity if you are talking about whole solution which uses sort procedures for input arrays. It is proven that lower bound for any deterministic comparison-based sort (which, I believe, is used in most libraries, and in your case as well) for arbitrary input is O(N log (N)): http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0130.pdf
Sorry, I messed up.
I forgot about the sorting portion of the problem.
I was simply meaning to explain that the pointer solution does not require any log N factor, so that other than the sort function, the solution is O(N).
Was trying to illustrate that I wasn't using binary search.
i too cant understand the logic behind C. please help. Atleast give a solution which implements the logic. You may post the code along with the tutorial. It will be helpful for beginners like me.
http://mirror.codeforces.com/contest/493/submission/8986100
Key observation is what chili mention, that we we only have to consider values of d in the space of the union of a and b's shot distances, not [0,upper(d)].
but in 1st test case, we have to take 0 as d and it is not in {A U B} space.
Is there an english version of the editorial?
I missed a case in problem E :'(
I wrote an editorial about problem E in Chinese. http://hzwer.com/5390.html
How did one arrive at the observation for problem D? It is too short.
How did one arrive at the observation for problem D? Editorial is too short.
I arrived at it through induction. Basically, if white moves first on a board of size N to (1, 2), the resulting board is basically a board of size N-1, with the positions of black and white reversed.
So, a board of size 3 is black win if white goes first, but for a board of size 4, white can basically turn it into a board of size 3 with black going first.
I'll admit, my proof during the contest was watertight, but I wasn't quite sure how to proceed, so I tried my solution, and it ended up working.
I don't know whether to expect a reply or not, but can you extend this proof for n = 5 ? Or maybe can anyone else have a shot at trying to extend it for this case ?
Using the above method(of induction) ,it will be difficult to prove when n is ODD. I think that this method of induction works only for n =EVEN number and not for ODD number.For odd number ,some other method would be required.
Блин, а как может игрок получить две красных карточки,6 тест?
Дело в том, что игрок не может получить 2 красные карточки, но Вася думает, что он сделал 2 фола, которые заслуживают красной карточке.
Разбор хреновый. Если n — нечетное, то черные могут симметрично относительно центральной линии — победив таким образов. Это русский человек писал? Я тоже так могу: ввиду того, что уже не есть, получается всегда опять как будто потому. Но только ежели затем и потому что.
Не совсем, так что простительно.
What is wrong with my solution?I was trying to maximize the value of y-x, where y and x is number of shots lesser than chosen d value for the second and first team respectively.8989966 Thanks in advance.
There can be a situation in which there are 2 throws form the same distance. You must be careful in that case!
Мне кажется, в Е забыли написать про вариант 1, a, ay + a - 1, в котором тоже будет ответ 1, в таком случае функция P(x) = xy + a - 1, P(1) = a, P(a) = ay + a - 1
Не забыл. Я сказал, если если t=1, то либо эти случая которые были написаны, либо P(1) больше всех коэффициентов, и этот случай разбирается как первый случай.
-1<0, поэтому это не подходит.
My submission for problem C ( 9005400 ) get Time Limit Exceeded as verdict in test case 1, but when I tested it in ideone ( here ), it passed with normal run time. Could somebody help me?
can anyone please why my solution(9017211) for A is being wrong on test 1 though it is showing correct answer in my compiler :\
Probably, the problem is with initialization of array "flag". You use falg[i][1] and flag[i][2], thus you need them to be initialized. But according to your code, you initialize only flag[i][0] and flag[i][1], so flag[i][2] is undefined.
Try to replace
for(j = 0; j < 2; j++)withfor(j = 0; j <= 2; j++)and I believe it'll be AC.Can some one explain solution to question E please.
When you look at this short editorials, you really see that the ideas which stands behind each problem, can be formulated in a few lines and it shows that it's simple.
Can C be solved using ternary search(on value of d)+binary search(to find the scores of teams a and b) ? I am getting WA, but I am curious to know if it is possible to do it this way.
Not but it can be done by binary search.
It is always optimal for the choice of d to be:
Let distances of the first team be array1, and the second team array2.
1) A value that is present in the first array. 2) A value that is present in the first array -1. 3) A value that is present in the second array. 4) A value that is present in the second array -1.
Sort array1 and array2.
Put all of these in a vector. Iterate on each value, and binary search on array1 to get the first value bigger than it. Multiply what is before it by 2 and what is after it by 3. Same goes for array2. ( Can easily be done by upper bound in C++ ).
Then just keep comparing and keep the optimal answer.
Runs in O((N+M)*(Log(N)+Log(M))) apart from sorting.
Hi All,
For the problem 493D — Vasya and Chess (Div2D/Div1B). I am a little confused with the explanation of the second sample input/output. The explanation goes like this (the part in bold is confusing me)-
In the second test from the statement if the white queen captures the green pawn located on the central vertical line, then it will be captured by the black queen during the next move. So the only move for the white player is to capture the green pawn located at (2, 1).
Similarly, the black queen doesn't have any other options but to capture the green pawn located at (2, 3), otherwise, if it goes to the middle vertical line, it will be captured by the white queen.
During the next move, the same thing happens — neither the white nor the black queen has other options rather than to capture green pawns situated above them. Thus, the white queen ends up on the square (3, 1), and the black queen ends up on the square (3, 3).
In this situation, the white queen has to capture any of the green pawns located on the middle vertical line, after that it will be captured by the black queen. Thus, the player who plays for the black queen wins
Now if I have understood it right, then it is possible for White Queen to win as well. Please can you help me understand why the answer provided by the author is the only possible solution?
I know it may be late, but check it out:
Help Vasya determine who wins if both players play with an optimal strategy on the board n × n.
It happens that, if the black plays optimally, he will "foresee" the white moves and won't do the move that leads the game to the alternative timeline you described.
A simpler solution for C(in my opinion) would be this:
https://mirror.codeforces.com/contest/493/submission/355054091
It can be proven that for two numbers a and b, where there is no number c such that a <= c <= b, then it is always optimal to either choose a, or b.