Доброго времени дня, сообщество Codeforces! С радостью объявляю, что 27 ноября в 19:35 по Москве состоится Codeforces Round #382 для участников из обоих дивизионов.
Автор этого раунда — я (albertg). Я из Армении, и пока единственный армянский автор раундов на данный момент. (Прошу прощения у Edvard) Этот раунд для меня является вторым и, надеюсь, не последним :) и последним. Как обычно, хочу сказать спасибо координатору Codeforces Глебу Евстропову (GlebsHP) за помощь при подготовке раунда, Михаилу Мирзаянову (MikeMirzayanov) за отличные платформы Codeforces и Polygon. Еще хочу благодарить super_azbuka за идею задачи.
Как обычно, участникам обоих дивизионов будет предоставлено 5 задач и 2 часа на сдачу решений. В этом раунде мы поможем Остапу Ибрагимовичу Бендеру добраться до Рио-де-Жанейро. Желаю всем удачи и удовольствия. Разбалловка будет объявлена незадолго до начала соревнования!
UPD1: Господа присяжные, заседание начинается! Разбалловка в div1 750-750-1500-2000-2500, в div2 500-1000-1750-1750-2500.
UPD2: Опубликован разбор.
UPD3: Если у кого-то вопросы по решениям задач (хотя это видимо мало кого интересует) пишите, пожалуйста мне лично. Буду отвечать.
UPD4: Прошу читать этот пост
UPD5: Опубликован разбор задачи div2E/div1C.
Clashing with another contest
One of them (HR preferably), please reschedule, so we can participate in both.
If you want HR to reschedule why are you posting it here?
Who is Ostap Ibrahim Bender ?
He is a famous rapper from Odessa.
да.
"В этом раунде мы будем помогать Остапа Ибрагимовича Бендера добраться до Рио-де-Жанейро."Значит нужно ожидать задачку на граф :)
UPD: wasted.
Скорее всего задача на граф во 2 DIV не будет слишком сложной.
normal time again
Is it rated?
yes.
Its fu*king rated..! Dont ask is it rated or not !
see this
Предпоследняя строчка — написано "помогать Остапа Ибрагимовича...", а ведь лучше будет "помогать ОстапУ ИбрагимовичУ ..." Или я что-то не понял?
по-моему ты что-то не понял
5 problems round again! Wish it to be an interesting round~: )
Hey, I'm new to codeforces. Can you please explain me what is Division 1 and division 2? Thanks.
Please
Thanks! Just one more query. Do we have to register separately for the contests (for instance, this one) or if we are on codeforces, we can directly give them? If we have to register separately, how to do so? Thanks again.
Yes, you have. Registration opens about 24 hours prior the contest.
waiting to see your performance in your first round
good luck
Thank you :)
I'm just a rookie. I hope to improve my coding on codeforces.
Названия обычных анонсов:
Анонс Codeforces Round #3XX
Название этого анонса:
Codeforces round #382
Возможно, стоит исправить?
Не думаю, что это так принципиально, хотя Round можно было и с заглавной буквы написать.
менял :)
Again....5 problems!!!
18:35
Perfect time for me
какие книги можно читать по граф c++
e-maxx очень классная книга с примерами её можно скачать ну или читать онлайн
Codeforces always helped me to improve my thinking capability , thank you codeforces :)
Объясните, почему много людей спрашивают "Is it rated?"?
Вероятно, потому что эта фраза выиграла конкурс мотто.
The comment is hidden because of too negative feedback, click here to view it
Lol, let's make it real!)
Petr has register for DIV 1. He must be aiming to get his second spot. Wish it to be exciting round!
EvenImage has registered too. He will try to prevent this.
Actually he can get his second spot without participating :D
Tourist used that trick before, remember?
Is it all? Just a comment? Aren't you gonna write a blog?
Actually you also got second spot without participating :D
Seems like its too difficult to get positive rating change when you are among top rated contestants.
I hope I can help Ostap Ibrahim Bender to not reach Rio de Janeiro.
Life is not the best right now here :P
You don't have to help, by the way, but I warn you, we have a long reach
Ostap Bender is a fictional con man who appeared in the novels The Twelve Chairs and The Little Golden Calf written by Soviet authors Ilya Ilf and Yevgeni Petrov.
А я веган, кстати, приятно познакомиться:)
So we should expect graph theory problems in this contest.
After a long time :D Back to home , codeforces ! The love! <3
Is it rated ?
Man, why? ;D
Nope)But it's rlly rated .
Yes, it is rated !!!
Ohhh....TY man!
Question of the day)
Hello.
This is my first contest.
Wish me good luck.
Also every Punjabi add me.
Jai babe di
Good Luck!
Thank you for your wishes.
I was solved with 4 problems .
I do coding and get a job and a girl friend and a happy life with some naughty time .
Also I am trying to get girlfriends on CodeForces.
Add me.
Score Distribution?? Not declared yet, 17 minutes left
"scoring will be posted just before the contest" might mean 30 seconds before the contest :)
30 secs left, still nothing)
Разбалловка будет объявлена незадолго до начала соревнования!Ну можно по быстрее.Кто-то на неё смотрит до раунда?
Я смотрю.
Where is scoring?
So the contest is gonna be delayed again?
At least I don't have to worry about system test (and can sleep early)
A=B=C=D<E
That sad moment when you're certain of your solution but it won't pass and you can't find where is the error
rip rating :/
Same as you, WA test 5 C and WA test 6 D
RIP rating :(
Plese someone tell me what where those tests so I can go cry myself to sleep
WA 5 C, hacked D ;_;
on D instead of searching for highest prime I searched for any prime P with n - P < = 500 and it passed test 6, the pure greedy solution isnt correct it seems
Check out Goldbach Conjecture
I repeat this 1000 times: while (n > 0) { x = calc(n) // calc(n) = the biggest prime number which is <= n; repeat x = calc(x — 1) 0 -> 3 times if n — x = 1 then x = calc(x — 1); res++; }
No need of searching.
If prime, print 1.
else if even, print 2
else if n-2 is prime, print 2
else print 3
You know, before the contest I knew nothing about Goldbach Conjecture and never used logN prime test. I learnt all of this just during the contest and implemented this: if prime ans = 1, if even ans = 2, if odd ans = 3. But why if n-2 is prime then ans = 2? I understand that this is true, but why namely n-2? Why not n-4? Maybe I just dont know math good enough :(
Because 2 is the only even prime number.
because 4 is not prime. You check for n-2 because 2 is also prime, and then that odd number would be written as a sum of 2 primes. if you checked for n-4, then you would decompose the number in one prime plus 4, which would give 3 instead. The only case that an odd number is a sum of two primes, is when one of them is 2.
Sorry, n-4 is my mistake. Then why not n-3? I see that 2 is somehow more unique in this case, but why namely 2? Is there a theorem or you just logically deduced this?
man, seriously!! are you even thinking? (no offence) this is too trivial.
The comment below explained it good and I really couldnt understand it. What is trivial for you may not always be trivial for every one. P.S. If you say "no offence" it is still an offence.
If an odd number can be split in 2 primes, one of them must be a 2, because in order for 2 numbers to add an odd number, one must be odd and the other one must be even. Then, the only posible split is 2 and n-2, if n-2 is prime.
Because 2 is the only even prime.
Are you talking about D? Cause I'm pretty sure mine is right too lol (unless I just entirely misunderstood the problem).
yeah, just found out it gives WA for 2e9 as input :/ fml
Lol that was my wrong answer too. Guess I should've googled a bit harder to find out about the Goldbach Conjecture.
rank dropped from 11 to 600 , just because of a stupid blunder :/
Overflow?
corner case in D . Dont know why i locked D so early :(
same with me
How to solve Div1 C and D?
Div 1 C:
DP(u, dist, nearest_one)is number of ways to color:nearest_one.Edit: I am mistaken :P
How to solve Div2 C? Every time I see a problem about any kind of paired tournament I become sad.
It should be a Fibonacci Sequence...
https://www.quora.com/What-is-the-best-way-to-solve-SPOJ-problem-code-TENNIS1
Contest quality is going down nowadays :/
Wow, it even has tennis statement as well. I wonder how many people googled this.
Yes they didnt even bother to change the statement :P
and author of this problem is albertg and it is posted in 2014?
Well , even though this problem was googleable.
I reduced this problem to taking out the maximum possible height of an AVL tree for given number of nodes.
Then you can solve it using Cheating
Fibonacci Number relation.
Analyze that minimum number of players required for x number of games at top:
1 — 2 players
2 — 3 players
3 — 5 players (One having played 2 matches and other 1)
4 — 8 players (One having played 3 matches and other 2)
....
The answer is maximum index where fib[i] <= n
Think of it this way. To have a 1-game tournament, you must have 2 players. You can consider 1 player to be a 0-game tournament since there already is a winner. In order to have an n-game tournament, the winner of an n-1 game tournament must play the winner of an n-2 game tournament. This is simply a Fibonacci sequence and can be calculated using dynamic programming. (Extra players beyond the target Fibonacci number cannot make a difference because they cannot reach a high enough game depth to challenge the current champion).
Think recursively. Let the winner has to play x games. Then he has to play at-least x-1 games and the other player has to play at-least x-2 games. Now you can see the pattern. It's Fibonacci. Hope it's help.
Can anyone explain how to Div 2 D? I did it greedily where I took the largest prime less than n where n-x >= 2 and then continued to take the smallest prime under that number until I got to 0.
But it seems that way is wrong. Did I miss the correct way entirely?
Two words: Goldbach Conjecture
Yeah I figured that and that's what I was doing so I guess I just had a bug in implementation.
If even (and not 2) the answer should be 2. If odd, then the answer is 3 unless N-2 is prime, in which case the answer is 2. Of course if prime, answer should be 1.
Yeah the one that breaks my code is 2,000,000,000 (it prints 4). Thanks for the help!
I used Goldbach's conjecture, though my solution was hacked.
Did you take care of case where n-2 is prime? Because in this case you can split in numbers: 2, n-2 and the answer would be 2.
I was "lucky" to get hacked by this case and could correct in time!
No, that is the reason. Unfortunately I was hacked a bit late so I didn't manage to fix the solution in time
why less than n? If n itself is a prime number then the answer would be just 1. I didnt get the solution but this might be your mistake.
I checked for that initially (I should've mentioned that I guess) so I don't think that was it.
I used this. I hope this passes system tests.
Hint: Every number can be written as sum of 3 or less primes. So check if it is possible to write as 1 or 2 primes, if not it must be 3.
So that's what it was. When I input 2,000,000,000 I got 4 but I couldn't find a set of primes that made it sum in 3. Could I ask how you came up with that? Did you already know that you could express the numbers that way or did you just think about it?
That is not true, 2000000000 can be written as a sum of 2 prime numbers. Following is a list (all of them are primes):
My solution (apparently correct) was based on Goldbach's conjecture. The answer was always going to be 1, 2 or 3.
Yeah that turned out to be what was wrong (my code prints 4 for some numbers).
Yeah it's wrong. There is Goldbach's conjecture which says that every even integer can be expressed as the sum of 2 primes and every odd integer can be expressed as the sum of 3 primes. But in some cases we can use less primes, take it as an simple exercise.
Alright good to know. Thanks for the help!
If the number is prime, return 1 (all prime numbers obviously have a tax value of 1, and this is key to the following algorithm). Otherwise, if it's even, then the Goldbach conjecture follows (every even number >2 is the sum of two primes) and you can return 2. If that is not the case, then check if n-2 is prime. If so, then the number is the sum of two primes (2 and another prime) and you can return 2. Otherwise, it is the sum of a prime and an even number (which itself is the sum of two primes), and you can return 3.
Greedy is flawed here. I initially thought it can be solved with greedy. Later, found that it fails if n == p+1, when p is a prime, greedy algo will try to split it as {p,1} but in the description it was given each of split elements should be greater than 1.
Div2 B hack?
Int overflows
Any idea of prestest 5 of C ?
Suppose, it is "n = 13", answer is 5.
Can you please draw tournament tree for n=13 ?
You can get it from comment below about n = 8 by adding subtree of 5 leftmost participants to the right.
Sorry, that tree for 8 contradicts main rule of tournament. Please provide tree where that rule holds independent of outcome of each game.
Thanks. It turned out that grid is not known before tournament starts.
I think pretest 5 would have been 8.
Answer for 8 is 4 and not 3 as the Maximum number of matches increases when the total number of participants is a Fibonacci number.
Can someone actually draw a tournament grid (tree) for n=8 ?
1 2
1 3
4 5
1 4
6 7
6 8
1 6
in order of games played.
If player 8 wins 6 in their match, then in the finals it will be second game for him, but 4th game for player 1. That is contradiction with the main condition of problem statement (difference between played games no more than 1)
behold the power of MS paint
Thanks, but this picture contradicts main rule from the problem statement. If player 8 and player 1 go to the final, they will have number of played games differ more than 1.
We are assuming the best case scenario (maximum number of games played), so we can assume that 6 will win in this case.
Organizers cannot assume that someone will win or lose. By definition of the problem they need to construct a tournament grid to match a rule: "two players can play against each other only if the number of games one of them has already played differs by no more than one from the number of games the other one has already played"
No, it is not the problem statement. By definition you should find a maximal possible number of games. You don't create a tournament grid, you only should take the best from all possible scenarios of grid+games.
I copied this from problem statement. Problem statement says that main rule should be applied for the grid (independent of games). But grid above is not valid for the main rule. It can produce sequence of games which contradicts that rule.
But the grid is not fixed. At that point, it does not exists. And it is not obvious what is grid in that problem.
I think the grid is not completely defined at the beginning. This way it makes perfect sense. Anyway, this is not clear at all.
I might be wrong, but I think the statement is a little bit unclear. This tournament grid is not valid in general, right? I mean, player 1 can't face player 8 according to the rules.I didn't realize that we could consider this kind of grid. :(
Why player 1 need to face a player 8? It is a set of games 1 2 / 4 5 / 6 7 / 1 3 / 1 4 / 6 8 / 1 6 / and some other stuff, when games are valid only if all players won all their games before that. In case that drawn on a picture, we have answer 4.
I get the answer, but why not? The statement says the tournament is being organized. Why would someone organize a possibly invalid tournament? You're right, but it could be a little bit more elaborated.
Is tournament grid known before games are starting? Or organizers can just randomly pick players during the tournament. Problem statement is very clear about "tournament grid", so I assume it should be finalized before tournament starts.
It must be the second option. They can pick players along the tournament.
Problem statement is very misleading than. It describes the different problem.
I think it's ambiguous. The expected interpretation is not invalid, so as ours.
Loved the idea behind problem D div. 2 (B div. 1).
what idea? i couldn't find the idea behind it! i thought it was greedy but did n;t accept it.
Goldbach conjecture
Is it an idea? If you are not familiar with the conjecture, it is highly unlikely that you will solve the problem.
True. This truthfully was the worst contest that I've participated.
steps to perform well on codeforces contest , steps 3 & 4 are enough in this contest i think :/ ....
UPD : you'll need step 2 also , but you should read all the old problems on spoj ..
Товарищи, поделитесь, пожалуйста, мыслями: как в DIV1-A можно было за три минуты догадаться, что там числа Фибоначчи?
Я до сих пор не понимаю, откуда там числа Фибоначчи =)
Пусть dp[x] — минимальное кол-во игр, нужное для того, чтобы один из игроков сыграл x игр. Чтобы достичь минимума для dp[x + 1], нужно, чтобы игрок, сыгравший x игр, сыграл с игроком, сыгравшим x — 1 игру. Таким образом, dp[x + 1] = dp[x] + dp[x — 1].
Нужно найти как можно более глубокое дерево игры с какминимум n листьями, в котором для любой внутренней вершины разность глубин ее двух поддеревьев не больше 1. Понятно как такие деревья строить: чтобы у корня была глубина k к нему нужно подвесить детей глубины k-1 и k-2 (это лучше чем k-1 и k-1 потому что в k-2 меньше листьев). Такие деревья фибоначи получаются. Я, кажется, где-то видел такую конструкцию; кажется, в контексте сбалансированных бинарных деревьев поиска; поэтому сразу было понятно, что числа фибоначи.
Ну если мы выиграли х — 1 партий, то выгоднее всего сыграть с кем-то, кто сыграл х — 2 партию.Тогда для количества раундов х количество человек, нужных для партии, равно с(x) = c(x — 1) + c(x — 2). c(1) = 0, c(2) = 1
One hell of a tricky contest!
How do you solve C? I was so certain my solution was going to pass but it didn't :( I think many others struggled on it as well.
Dp[i] = the minimum number of players needed such that the winner can take part in i games
Wow I didn't think of it as a DP problem. How would you transition between states?
Fibonacci sequence, where dp[0] = 1 and dp[1] = 2.
This was a hacking contest. 1 integer input problems for C,D. "7" and "9" were hack cases for D.
I've attempt to hack div2 A using the following test input, on the codes that did not handle negative indices (for example, 22533346):
However, they output correctly. Is there something I have mistaken?
At first: Thank you for hacking :D.
A few minutes later: Sorry for hacking :(. I don't want to lose my rating (significantly).
Hack-ers aren't cruel at all, what is? Seeing a wrong solution and ignore it! :v
Solved D for the first time! I hope it will pass system test. :)
Dooms Contest :/ GG Rating
I wonder how this guy might be feeling after hacking 5 solutions for D and getting hacked back by one of those users.
awful contest!!! especially for problem div2 D , it needs to know Goldbach's conjecture. Is it related to problem solving skill?!???
I do think that Goldbach's conjecture is a kind of common sense instead of solving skill.
I don't know about him but bvd is very relieved after getting revenge I think.
I'm sorry to tell, but truth should not be concealed : Awful problems on C and D (they don't deserve their intended points) :(
Couldn't agree more.
I agree. Almost no algorithmic skills were needed to solve these two.
Actually contests require problem-solving skill, not only popular algorithms and data structures :D
I think C is ok. It's something you can figure out with a piece of paper, D is just about whether you've encountered the conjecture or are googling during the contest.
What's wrong with C?
I got disappointed with my result in this contest. I am pretty sure I have become better in algorithms as I usually practice in TopCoder. According to the new rating in Codeforces, I got moved to Div2. Then, I decided to participate in this contest to reach div1 here, too. Generally, I have difficulty with these kinds of problems since instead of thinking about algorithms, I am forced to find corner cases. I don't really like these kinds of problems though I have the great respect for the author.
Regarding other comments, I found out that the Problem C has been available on SPOJ. I think albertg does not know anything about Self-plagiarism.
i used this code for problem C i got WA in pretest 7 any idea ?
while(n>1){ if((n%2)==1){ans++;}; ans++;
n>>=1; }
For Problem C I think it's a fibonacci problem.
Could u please explain it ?
Yes I can.
We define f(n) to be the minimum number of players required such that the winner can play n games at most.
So the ideal situation(to make the number of players minimum) is that the last game the winner played is with another player who played n — 2 games already(since the winner played n — 1 games at this point).
So we have: f(n) = f(n — 1) + f(n — 2)
then the final answer is just the maximum number m which satisfied f(m) <= tot_number_of_players.
else A&B(div1) problems were fun.
thanks.
Yes, both A and B are terrible. I wouldn't recommend them to anyone of any level. Maybe if the author used only one of them it would have been suited for Div.1 A
My friend just told me that he solved C and D (Div.2) by finding other peoples' codes on ideone. This is so unfair -_-
If it is matched with some other code that submissions will be skipped :)
If people are smart enough to find codes on ideone, they will definitely modify it as they know about this dirty trick. I was surprised to see the rising submissions for C and D.
Report him.
Since when did this start happening on codeforces? Same author, Same problem.
How is this even possible ? is the author foolish or something ? How can he repost one of his own problems ? Lol
the contest should be made unrated . Div1 A was copied and Div 1B was google-able :(
kingofnumbers was right in his blog for which he faced so much criticism. The author of this round did not even care to change the title of the problem. -_- People cheating from ideone and authors making one problem googleable and one problem exactly same(again googleable). Bye bye albertg. Hope this second round is your last round.
this not convincing reason to make unrated this mean that they have to make all previous contests unrated
there he is ^
lol i'm such a shitty friend
who are you -_- I don't even know you -_-
Bro, if you want people to believe you, at least don't make any more lies that I can easily prove wrong
Come on, you gotta be smarter than this!
LOL :v
So you want to cheat from ideone and then fight for whether the reason is convincing or not to make the round unrated?
I didn't cheated you can confirm from my status -_-
How to solve Div 2 E ?
Did anyone used prime numbers to solve D?
Yeah (D2 D was the same as D1 B). The key insight is the Goldbach conjecture (any even number >2 is the sum of two primes).
Yes, I am
Problem D/B be like:
haha thats funny.
problem D can anybody google it
this is unfair
Yeah, no problem is fare. Or did you mean fair?
in problem C:
"Don't miss the unusual constraint for k."
is just a lie :|
Hope I can jump to div1 for the second time.
Div.1 A I wonder how many people could google this http://www.spoj.com/problems/TENNIS1/ during the round.... -_-
I've actually learned something new from this contest, thanks!
1) Google exactly the problem statement because apparently... you might get lucky (same author, same statement)
2) After #1 is done... you know what to do next
3) If everything fails, try checking other people's code on ideone.com because apparently... well, you got the idea
Go Googleforces!
https://www.quora.com/What-is-the-best-way-to-solve-SPOJ-problem-code-TENNIS1
HELLO FROM 2K15 BOYZ
this contest reminds me of april fools day contest :D :D
Actually April fools day contest is more interesting than this contest.
Is it fair to repeat your already existing problems? albertg
http://www.spoj.com/problems/TENNIS1/
Vah beta :P
Can you please translate?
mdakeklol
I don't want to sound rude or anything, but this contest was very bad and in my opinion should be unrated, and I'm not saying that just because I participated badly. The main reason is that problem C was on SPOJ — link and was posted there by the author of this contest! Anyone could just google it. Also D was an ugly problem, and the only way to solve it was to either somehow already known about Goldbach's conjecture, which is not all that well-known, to search it on google which shouldn't be a way to solve a problem, or to guess it, which would be just luck.
For D, If someone is able to deduce that answer will equal to minimum number of primes whose sum is equal to n then google search will take you to Goldbach's conjecture. So I feel it's ok. BTW it was similar to Dima and Lisa which was blocked during contest.
Deducing that was easy for a D level problem, the hard part of the problem was finding the number of primes, so 90% of the problem was solved through google
Are we supposed to be using Google during contests?
I didn't know about Goldbach's conjecture, so I bruteforced the first few answers and OEISed them. Still bad though
Div 2 D is just the same with #324 div 2 D. (http://mirror.codeforces.com/contest/584/problem/D)
In this round's problem you have to prove that you should only pick primes. Minor difference, but at least something
While it's true that the author may have used one of his own problems and this was a mistake, it's important not to consider the entire contest as bad just because one or two tasks were not optimal. It takes a lot of time to prepare these contests, especially for both divisions, so at the end of the day, we are all in the author's debt, not the other way around.
Although I didn't participate but we aren't talking about optimality here. You were an author before and you know it's not an easy task to come with the problems but you also know that it's a huge responsibility, in case it's a dup problem we can excuse him assuming he didn't know it existed but here he was the author and it had been there for 2 years.
There was no problem solving in Div2 D also just using a well know theorem.
Not really. Authors are paid to create problems for a contest, and if they are reusing one of their older public problems, they are basically cheating.
Не слишком ли боянисто?
Лол, я сдал эту задачу в тимусе но не решил в этом контесте :D
Та не, задача, которая находится в гугле в 3 счета и решается за пару секунд — самое то для D.
Я узнал о гипотезе Гольдбаха (точнее, её формулировке) в шестом классе. С тех пор я всё ждал, когда же удастся её применить (сначала на олимпиадах по математике, позже и на информатике).
НАКОНЕЦ-ТО
make it unrated is the most stupid thing CF can do
I don't participate in one contest and the freaking problem D can be done with the Goldbach Conjecture , fml.. They should make it unrated, this isn't fair!
One of the problems was a straight copy, and the other one was a google search problem. Making this round rated cheapens the value of one's rating.
In Div1-D, is it enough to check for each relation if it is contained in exactly one valid permutation?
I solved using the following:
Let A be such matrix that Ai, j = 1 if permutationi can equal j, and 0 otherwise.
We know that the number of all valid permutation is a permanent of A, and
in 
. So we have to check for some queries (x, y) that Mx, y = 1 (in 
, here Mx, y is the respective minor). It's known that Mx, y = A - 1y, x, so we just calculate A - 1 for n3 / 32 and win.
UPD: and A - 1 exists since
.
Nice solution!
I haven't got the only thing about Mx, y = A - 1y, x. Could you please clarify or give me a link or whatever.
https://en.wikipedia.org/wiki/Minor_(linear_algebra)#Inverse_of_a_matrix
is contest rated?
now it's a good question
Actually, problem D is the direct application of Goldbach's conjecture. I think this is the 'ABC' in the world of math/number theory.
I remembered that I've learned this when I was really really young, maybe the time when I was a primary student or a middle school student.
Even though, I failed to come up with this quickly in the contest and tried several wrong ideas, wasting my time.
From the view of problem setting, I don't think this problem (as well as C) is good. I think people don't want to train their knowledge of commen sense in problems like D in div2. These problems can be better if they engage more thoughts. As for me, I enjoy harder D, even if I can't solve it.
But from the view of a problem solver, I think div2D is still good problem. It reminds us that we should not forget the most fundamental thing when we are solving hard problems. If tourist competed in this round, I think he would solve div2D easily. We as problem solver should think of how we can deal with such problems quickly under adverse condition instead of complaining about it. Life is not always fair, right?
Anyway, thanks for the problem setters. It is not easy to prepare a contest. And somehow, it is not easy to come up with easy problems. Hope the next round will be better and I can become purple. :)
Regarding the repeated problem issue, if I were in charge I would zero out all results from 1A/2C but not unrate the entire contest. The problem lies exclusively in a single question, and yes it is a major problem, but it's not like all of the questions leaked or anything.
Also, some here are saying 1B/2D was "unfair"; I have to say I personally disagree, with the caveat that maybe this wasn't the best problem to have in Div 2 because of this. Yes, 1B/2D relied on some knowledge/research -- but in the end, what harder problem doesn't to some extent? At the ICPC Mid-Central Regionals, one of the hardest problems anyone solved (and, in the end, the one that put my team over the top to go to Worlds) seemed intractable -- until, that is, I realized that the problem of deciding whether a given power level is possible reduces to 2-SAT. Without knowledge of 2-SAT and its reduction to the strongly connected components problem, this problem would be impossible to solve. In addition, most geometry problems have some innate knowledge requirement in order to reach the key insights involved. Maybe this problem was a bit irksome because its knowledge difficulty was above its algorithmic/implementation difficulty, but overall I don't think it was a bad problem (though, again, maybe it should have been replaced with something else for div 2).
But some people spent most of the time thinking about it, wasting the time which they could've spent searching on google D's solution
'some people' doesn't mean only you.
What about someone who had no idea about the repetition of problem C and solved it by himself giving maximum of his contest time? Will it be fair to zero out his accepted code?
Look at the code of winner of div2 round. Who uses DPDPDP as a variable? I wish there was no find and replace option built.
I guess it turns out that KSL who was previously first place cheated. Maybe people downvoted you a little too early, because there definitely was something fishy about that guy.
blokes ya just have butthurt cuz you didnt solve these problems. great contest, well done.
And it doesn't look like you solved anything at all ;)
Hi. Can anyone help me with div.2 B? My code works fine on my computer, including the first test case. But on codeforces the output is -2 on first test. http://mirror.codeforces.com/contest/735/submission/22553933
I think you algorithm is incorrect to begin with. The correct answer is taking the first min(n1,n2) to the smaller set and the next max(n1,n2) to the larger set.
Thank you, but I swap the values if n1 > n2: "if(n1 > n2) n1^=n2^=n1^=n2;"
change long double to double
Thank you very much! But why is it so?
You shouldn't have used long double. Make the sums with long long and then cast to double when printing... Got AC here with it: http://mirror.codeforces.com/contest/735/submission/22558151 :/
Could you also tell me why long double didn't work? edit: I googled it.
I think there is a problem with codeforces and long doubles. I also submitted with long doubles and had WA in test 1. Better use double.
Well I don't know the actual size/range of long double but it seems like some kind of weird overflow (? overflow with sum 6?? lul wut??)
Looked it up and on wikipedia they basically say it's unspecified so I guess it's better not to use it on contests... I recommend always using long long and cast, works well for me :s
The problem is with printf and not long doubles!
In my opinion, tests for problem D are not enought. Some accepted solutions are checked only prime numbers to 1e5. I think there are no complete test cases.
I mean you are right!
Why do people use Google during the contest in the first place? And if one uses the argument "everyone else is doing it" then how different is that person from all the other googlers?
Correct me if I am wrong, but the purpose of these contests is to hone one's skills. Although the problem setter made a mistake posting one of his own problems, take into consideration that the author took his time to put this contest together.
Without using Google, I find Div. 1 A&B very reasonable. It definitely took me more time to come up with Div. 1 A but I came up with that so why should I care that someone looked it up online. I didn't even know about Goldbach's conjecture but managed to solve B with some kind of brute force. It seems that the problems were more or less balanced if not for the googlers. But googlers are googlers, why should one compare himself or herself to them.
Agreed. Your non-Goldbach's conjecture version makes me feel better about that problem.
There's never going to be a way to stop people from cheating anyways.
I spent most of time working on problem D... There seemed to be a fancy conclusion as the solution to problem D, but I hadn't got it. Umm... I should improve the level of knowledge.
why my code got WA in test 11 Div2B
submission
I think overflow in sum1 and sum2 might be the problem here. Try using long instead of int.
yes it was the overflow i wish i did it before :(
Ah well, you won't do it next time :D
How to solve Div 2 E / Div 1 C?
Does anyone know why the problem C of Div.1 use unusual constraint for k?
There is a solution with O (2^k * n).
We iterate over the vertexes, which will be painted (this vertex is removed no more than k from the root), brute over her mask and update dp.
I cannot understand it still. Q_Q
Personally, I don't see why it's considered unusual?
I say it is unusual because the statement say that. And I cannot think out one solution using this constraint. My solution can be done in O(n^3). In order to use the constraint, I take some time in thinking it bug I give up in the final.
There is O(n·k4) solution. Dynamic programming with
dp[2][n][k]— the number of ways to fill a subtree that either the topmost black vertex is at some height or the topmost non-satisfied white vertex is at some height.Just googling round)
thanks the author for ruining my 2 hours:/
i should have participated in HR ICPC contest :(
All problems there were OLD HR problems :) People Googled/Searched HR archive and submitted :) So, by your logic, you would have complained about HR contest too!
So the best solution for you would have been shutting down your system for the time being :D
It's better to stop complaining and learn :)
If you cared about improving you wouldn't say that (unless ofc you have solved all the problems on hr)
waiting for Edtutorial just to give you your deserved downvote
Wow, they actually made it rated.
Did anyone take advantage of a problem div1A being googlable? There is no editorial or any comments under that problem. I've just tried to submit a solution there and got ERROR — so I guess it wasn't possible to test one's solution by submitting a problem there. The only possible issue I see is that someone may have already read that statement. There is a tag "hidden" though and maybe it means that a problem isn't showed in the global list of problems. Still, maybe someone managed to find it in some way before, but it doesn't look like a likely scenario.
Uh the solution is on quora.
Erm... https://www.quora.com/What-is-the-best-way-to-solve-SPOJ-problem-code-TENNIS1
This author should be banned permanently for giving the same problem twice. There should be no reasonable explanation for such behaviour. Giving one more problem on "Goldbach's conjecture" totally sucks as well. This round is ridiculous.
Yeah, also take a look at his other problem on SPOJ. Not an exact copy paste as in Div1-A, but it requires Goldbach's conjecture. I wonder why he would need to copy-paste and/or re-use ideas from his own problems. This is utterly absurd.
I can understand giving a problem which appeared before, you might not know about it, it happens from time to time. But when it's YOUR OWN problem...
I didn't know that a solution is described somewhere. Ok, then it's a bad situation.
Codeforces really wants me in div1 :)
well, the round is rated for both division, same shity problem for the same author and with the same statement
everything is fine , don't you think that at least we own you an apology ?
Cmon, problem C div 2 was nice. The only mistake imo was to copy the exactly same statement.
THIS IS RIDICULOUS!!
Most contestants are complaining that problem A Div.1 is repeated with the same statement and the same author & problem B Div.1 can be googled easily and all we can get is IGNORANCE..
I downvoted the contest, it should be UNRATED!!
I wonder if albertg will write an editorial for Div1/A or he'll just post the Quora link.
Yes, the ratings have been published already mate. It is RATED.
This contest is just terrific!
Wow, another account standing in the "Ban queue"! :D
you didn't do this round, why you are so emotional now? My dear "Trump"
now , i think that Edvard is the only Armenian author in codeforces . :3
Just for fun: problem with (a bit) similar idea to D2-D / D1-B: https://community.topcoder.com/stat?c=problem_statement&pm=11607
I wonder if albertg will write an editorial for Div1/A or he'll just post the Quora link.
Let's make the contest editorial post the most downvoted post on codeforces....
I'm poor in math; Then I got a 75 ratings decreasing..; Horrible math....; However,This is a Nice round; Thank you! (I'm poor in ENGLISH too.TAT)
I thought it would be unrated, maybe I will back to blue when I wake up tomorrow ...
I like mathematics so I think C and D were good problems. Maybe it was too easy to copy them from google but beside that they were interesting and challenging.
albertg Here is a list of "Things to Do":
1. Apologise CF community for your behaviour and laziness to not even change the problem title.
2. Request Mike to make this round unrated.
3. Live with the curses of people affected by this round.
CF should have not make this round rated. I will definitely move to AtCoder, Codechef, Hackerrank and CSAcademy. But now-a-days, frequency of contests has decreased. Can anyone suggest other similar sites that hold frequent contests with their standards maintained and proper and genuine problem setters.
Anyways, here is the link to downvote this guy.
EDIT: Reply to all saying I have only 1 submissions. "This is obviously my secondary account. To all the people ready with questions like, "Why do you need to comment from your fake account? Do u fear to reveal your identity?" I have the answer: "I get downvoted for no reasons from my main account. Plus I need such account to enjoy contests and do not let my div1 rating to go to div2.". Why am I so mad? Because I can't use the coach account and see test cases of gym problems. Plus I am an addictive coder at heart and love my rating. Hope I clear your doubts."
Well if he does 1 and 2, 3 will be invalid since noone will be affected anymore. Also I think CF is good, only that sometimes mess-ups like this happen. We all make mistakes. Although when we make mistakes we shouldn't take this long to make an apology...
"I will definitely move to AtCoder, Codechef, Hackerrank and CSAcademy"
You have exactly one submission on this site. I wouldn't exactly call that moving...
You participated in 0 contests and you have exactly 1 submission in Codeforces. Moving to other platforms won't affect CF much.
Why would you want to downvote an editorial? Do you want it to disappear (at least from the "recent actions")?
That being said, I also think that an author behaved badly.
This is obviously my secondary account. To all the people ready with questions like, "Why do you need to comment from your fake account? Do u fear to reveal your identity?" I have the answer: "I get downvoted for no reasons from my main account. Plus I need such account to enjoy contests and do not let my div1 rating to go to div2.".
Why am I so mad? Because I can't use the coach account and see test cases of gym problems. Plus I am an addictive coder at heart and love my rating. Hope I clear your doubts.
I get downvotes for no reason regularly. Once, I made a contest announcement and quickly got it downvoted. So I made the same contest announcement again — because I don't care about an e-penis (contribution), just about what I write being seen.
Maybe you should move to Reddit instead, it seems more up your alley.
Nice comparison. Btw. that feeling when you have e-penis smaller than a woman (gKseni).
That stands in direct contradiction to Rule 30, though.
So, Problem C div2 / A div1 apparently is http://www.spoj.com/problems/TENNIS1/
The author is the same btw.
And this problem is hidden from the site because of its unclear statement.
My solution was ceil(log2(n)) which I think is right.
Same, I missunderstood the condition and many people did too... Although on this I'm gonna blame myself for not being careful, the author has enough blame on him already.
Screencast: click
Also today’s DIV1 E was actually the same like this problem http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=714#1. You just needed to add two more cycles.
I think the author wanted to make an Educational Round but accidently published it as a regular round :3
One of the worst contests I have ever participated in xS
I love math so much and I want every contest be like this (not)
I think there is problem with editorial link.
The contest with the largest no problems ever
Интересно, а что делает координатор на Codeforces?
I've read all the comments and very upset about the situation. I told to writer and asked him to describe here how it happened. The situation with 736A - Tennis Championship is very disappointing. I'll announce the decision about the rating as soon as I decide something.
Sorry for the issue.
Actually this round is good (which can practise my maths skill)
but someone always try to cheat :(
wish it can be partly rated.
and i got up at 3:35 a.m.(UTC+11) to do this round
it's unfair for non-cheater if unrate
It's unfair for non-cheaters if it's rated because then the cheaters may beat non-cheater.
It happens that 2 problems coincides not only between 2 OJs but in the same OJ.
Last round (Codeforces Round 381 (Div. 2)) problem 740D - Alyona and a tree was the same exact idea as problem 101147J - Whistle's New Car from contest 2016-2017 ACM-ICPC, Egyptian Collegiate Programming Contest (ECPC 16) not the statement or author or anything, but it is the same exact problem (only input format differs). Possibly Telepathy!
I think this is almost the same exact situation here. So it wouldn't be a big problem if this round remains rated.
So they should both be unrated.
and Intel Code Challenge Elimination Round (Div.1 + Div.2, combined) C. Destroying Array was exact same problem with CS Academy round 9 Array Removal problem.
Thank you, please make it unrated.
It's kinda sad for people gained positive ratings without cheating.
When can we expect an update ? Its been 11 hours + now ...
Just my opinion, maybe you could do something like:
Those who lost their rating will get it back(like they never had participated in this round), other ones, who gained rating, could still have it!
Mb you'll think about it
И снова долгие ожидания нового раунда(((
Why did this code not get wrong answer on a test like 100000 50000 50000 and with al the numbers equal to 100000 given that 5*10^9 is bigger than maximum int? no overflow
define int double
Zlobober We need more rounds from you ! :(
Hey, can you please explain me the difference between the various problems A,B,C,D,E ? Are they different in difficulty? Or there are just of the same difficulty but based on different topics? Or both? Hope you dont't mind. Thanks :)
They should be ordered by difficulty. I mean A < B < C < D < E. Nonetheless, it is not always so. With respect to the topics, they are usually different, but A and B are often implementation.
I demand justice! I solve and solve and no point from C. Also I see it copyd from elsewhere. Make it unranked or I leave site!!1
По задаче С второгодивизиона.
Почему при Н=12 мы не можем сформировать дерево турнира таким образом? Условно представим, что выигрывать всегда будет левый сын. В даном случае ответ будет 5, в то время, как авторское решение скажет, что ответ должен быть 4. Где я ошибся?
9 не сможет сыграть с 12, а если в матче 9 vs 11 выиграет 11, он не сможет сыграть с 1
Your text to link here...
" и последним."
Да ладно, че ты так? Крутой раунд, делай еще!)) А косяки случаются, все нормас
What am I missing here ? :(
22565660
Problem : 735C - Tennis Championship
You are wrong in the idea. The problem require fibonacci. View editorial: http://mirror.codeforces.com/blog/entry/48659
C. Tennis Championship why i solved it. its seen wrong answer in test case #6
include<stdio.h>
int main() { long long n,ck,x; while(scanf("%lld",&n) != EOF) { if(n==1) { printf("0\n"); } ck=0; x=1; while(x<n){ x=x*2; if(x<n) continue; else if(x==n){ while(n!=0){ n=n/2; ck++; } printf("%lld\n", ck-1); } else{ while(n!=0){ n=n/2; ck++; } printf("%lld\n", ck); } } } return 0; }