Привет, Codeforces.
Сегодня, 17 декабря в 19:30 MSK состоится очередной, 283-й раунд Codeforces. Автор задач — я, Михаил Тихомиров. Макс Ахмедов (Zlobober) помог мне с обсуждением и подготовкой задач, Мария Белова (Delinur) перевела условия задач на английский, а Георгий Чебанов (gchebanov), Александр Машрабов (map) и Нияз Нигматуллин (niyaznigmatul) заранее прорешали раунд и помогли нам выловить ошибки и неточности; скажем им большое спасибо!
Раунд состоится в обоих дивизионах. Разбалловка будет стандартной (не динамической); распределение баллов следующее:
Div. 1: 750-1250-1250-2000-2500
Div. 2: 500-1000-1750-2250-2250
Это мой четвертый раунд на Codeforces. Надеюсь, он пройдет не хуже предыдущих трех. =) Желаю всем удачи!
UPD: раунд завершен, всем спасибо за участие!
Поздравляем победителей:
Div. 1:
Div. 2:
Разбор доступен по ссылке.
Is this the record for shortest round announcement? Very concise and direct.
Lets hope problem statements are same way
Have to hope editorial is the opposite, however.
look
The first three characters of your name are "End", I hope this contest won't put the end of my green color.
Hopefully this will put the end of my blue colour; I hope to be purple again :)
Why is this blog annoucements, statements, tutorials of a lot other contests?
Perhaps he was thinking, "Hmm, the blog announcement is so small, maybe I should add lots of attachments with it to make it bigger" :p
I don't think so.
Endagorion can write a lot's of things to make blog longer.
I think somebody attached to this blog these contests. But why??? That's interesting.
What you are saying kind of makes sense. Why would this blog post be "Tutorial of 2010-2011 VII International Zhautykov Olympiad"? I guess somebody is just messing around :p
The "someone messing around" theory makes the most sense IMO. I think anyone can create attachments like this (at least I can -- or maybe it's just people with coach mode enabled?)
what is coach mode? and who can enable it?
A coach can create new contests in the Gym and view others' submissions to Gym problems.
For the conditions to have a coach account, see http://mirror.codeforces.com/blog/entry/11037#comment-161942 (you have 28 contests, so you'd need 2 more).
Or it's a bug, probably?
There's a blog post that has a similar issue (this post).
The attachments to that post aren't related to the post itself, just like this blog post.
I have no idea what was the deal with all these. Deleted them anyway.
Как много соревнований прикреплено к этому блогу.
Зачем интересно?
Когда такое спрашивает человек с таким ником — это наталкивает на подозрения
И на какое же интересно?
Что ник не врет.
У тебя тоже знак вопроса сломался, да. Но зачем тогда вместо него ставить точку.
UPD сделал подлянку, исправил)
Честно говоря забыл. :)
Честность никому не нужна) вот накатит волна юзеров, оба это поймем)
Не согласен с твоим мнением.
Вот и проверим
UPD ты был прав
Урааааааааааааааааааааааааа , разбалловка не динамическая.
Вот честно говоря, уже и вспомнить не могу, когда в последний раз разбалловка была динамической на div. 1 раундах... :)
верно ли я понимаю, что стоимость задачи от времени не будет меняться сегодня?
Ой, я, оказывается, написал совсем не то, что имел в виду. Конечно же, будет.
I hope that it will be interesting.
Topcoder Rating are increse. Codefores Rating are waiting......increse/decrese.
You forgot to thank MikeMirzayanov for creating Codeforces and Polygon systems :D Fingers crossed. Lets hope that there are no server errors :P Just kidding, thank you for writing this round, your previous contests were also good.
It seems the Codeforces Google Calendar is out of sync or the entry for this contest has not been added to it. It is kind of sad as I will not be able to participate because of that.
Time to dreamoon_love_AA.
Preparing the contest is exciting partly because you know all the decent coders out there will try their best to solve your problems; it's a pity to know that some of them prefer to opt out of fair competition.
What's wrong with dreamoon_love_AA's account?
See his rating graph
The last Endagorion contest was a failure for me! I hope it will be different today! :D
Hi!
Endagorion thanks! your last contest had nice problem :))
Hi! Endagorion thanks! your last contest had nice problem :))
Oh...
I typing very fast so I'm Careless!
Me too... I type too fast and im very very careless because of that http://paste.ubuntu.com/9551585/ EDIT: this is just a joke dont take it seriously guys
"Hi!" must be in a new line :P
В прошлый контест автора я чуть не затащил (неправильно посчитал максимум). Может, хоть сегодня повезет?
All of your contests were Div1 + Div2. And you prepared all the problems alone.
Today, There are a lot of contests that there is a team with 7 members for preparing problems but the contest is just Div2.
Thank you so much.
I hope all Specialist be Expert and all Expert be master !
deleted
deleted
Then to balance it, each Pupil will become Newbie and each Newbie's rating will decrease :(
I think it is very difficult to make a jump from Expert to Master.
Look at this profile: mhadih
Look at his red dot. It's not from Expert to master but it's very close.
impossible is nothing :)
--> Ibro
hello every body
dis like me plz
are you sure? Link :p
He needs to be more original if he wants to break that record!
lol, it has been a while since "Dislike Me" posts have been made in a round. Not that the absence made it any better...
Вроде уже исчезли лишние анонсы, разборы и пр. Но сейчас опять:
У меня одного снова?
The contest will begin at 0:30 am in China, luckily, i have no courses tomorrow :)
Hope for high rating.
Everyone does.
Except dreamoon_love_AA.
Too bad worse gave up...
Speed of internet is so slow when there is a ten minutes to the contest
The age of unusual score distribution.
All of us second division participants, this is our last chance to win (as dreamoon_love_AA has almost arrived !)
чего всем так охота дать задачи посложнее?
Все вопросы по условиям во время раунда отправляйте через тестирующую систему. Любое обсуждение задач в блогах во время раунда запрещено.
Как решать С?
Идём сканлайном и храним правые концы актёров в сете. Если встречаем левый конец песни, то ищем покрывающего её актёра с минимальным правым концом.
Note to self: avoid geometry =(
It comes down to segment vs ellipse (possibly degenerate) intersections, right?
Yes, in fact it's segment vs. circle intersections.
It would be a circle if they rotated in different directions. Unless you mean you get a circle after squeezing the ellipse along one of the coordinates.
Well, I believe that it's circle when they rotate in the same direction. And with this approach I passed pretest, so it might be correct.
Uh if you consider the movement a point X on the second polygon relative to P, you will notice that Q rotates around P counter clockwise, and X around Q clockwise. If you add these two movements, you will get an ellipse (assuming |XQ| != |PQ|, otherwise it will be a segment).
Well, in frame of reference where A isn't moving point Q rotates around P CCW, but as the frame of reference is rotating CW itself, X will not rotate around Q at all.
was div1 C bipartite matching? or could something like sorting and 2 pointers work? :\
Sorting and two pointers. Assign the scenes greedily (take the ones with lowest A that satisfy the conditions). Good luck with bipartite matching when you have 10^5 nodes and 10^10 edges ;p
Did something similar.. pretest 5 :\
I had an issue with it too, because I was sorting by the wrong coordinate (forgot to pass my comparison function).
Would you mind telling the order of each parameter you used for sorting?
greedy is enough
When will system testing begin?
Your contest have nice problem :)
thanks Endagorion
I'm surprised that div.2 problem is hard for everyone, this is the first time I made to the top 3 in my contest room eventhough I only solve one problem lol. I can't believe it >.<.
nice problem != hard problem !
I think it is time for me to say "Goodbye Expert".
What is the solution of B problem? It was harder for me than C :D
Simple bruteforce
Bruteforce all possible shifts and increasing by 1.
How to solve Div1B/Div2D
Go through the list from left to right to get all possible values of T. For every value, you can 'simulate' the match by using binary search to find where the sets end (calculate partial sums of the number of wins of each player), and check whether you get a valid match (and obtain S in the process). It will work quickly enough because you only try each T once, and the complexity of each simulation is (n/T)*log(n). If you add them together, you will get (n+n/2+n/3+...)*log(n) = n*log(n)*log(n).
I did the same thing. Can you please take a look at my soln ?
http://mirror.codeforces.com/contest/497/submission/9176658
actually binary search is not necessary. you can just store at what index does your ones (twos) become wanted value. so complexity becomes n * log(n)
I stored the first position of a particular number of games won and simply simulated for all values of t from 1. This would be O(nlogn)
You can fix the T in the interval 1, n. Now, you are going to see for each set where does it and and where does it begin.Also, you have maximum N / T sets. You can determin this intervals using binary search. So you have Nlog^2N.
The fact that in Div2 there are less than 10 successfull hacks from current top500 is not good
Nice problems thanks a lot authors
if cnt[1] == cnt[2] cout << 0; <- i wrote it in the beginning
ok kill me pls :(
Welcome to the club. 9178079 9176101
Any test case for contradiction of ( if cnt[1] == cnt[2] cout << 0; ) ??
Sorry, wrong probem O:-)
The number of total points doesn't mean much. For example, the person that won less points may be the final winner.
Example: s = 4, t = 2
2 wins 10 serves, 1 wins 8 serves and 1 wins the game. Kind of unfair, isn't it?
Even simpler:
8 2 2 2 1 1 2 1 1
Очевидно что контест должен стать нерейтинговым. Я еще не придумал почему это очевидно, но это очевидно.
What was the tricky #8 case in D?
I have no idea, but did you consider the case, when a segment crosses a circle, while both its ends are outside of it?
As far as I remember, not considering this gives WA6.
Yes, I did. But considering it was pretty long "if", I hope it was correct, I've read it many times xd.
OK, my solution just contained many bugs (what is funnier, not in formulas) and this test was one of the first test checking anything :P.
how to do div1B ? failed pretest 7 :(
You posted in russian interface, you know?
After ~20 debug submits I found out that 7th test is something like
20 2 2 2 1 2 2 2 1 2 2 2 1 2 2 2 1 2 2 2 1
The answer is 0, your program probably outputs 1 15 1
I think it is much simpler: 5 1 1 1 2 2
Well, I brute forced this test by making submissions with statements like if N > 20 exit(1);, so I am sure that in this particular test N is 20 and there are 5 ones and 15 two-s:)
Hey @admin : I submitted the code when there were 7 seconds left. It didn't accept my code.Please evaluate it :( Problem D
include
include
include
using namespace std; int n,a[100000],f[100000],x=0,y=0,ans[10000000],ac=0; int fact(int o) { for (int i=1;i<=f[n-1];i++) { if (o%i==0) {
} int main() {
}
You will get WA for this: a player can get some points in sets he didn't win, so his total wins don't have to divide equally by T.
Yeah , your correct. That makes me feel better :P
Thanks :)
7 seconds might be wrong time synchronization in browser...
http://mirror.codeforces.com/contest/497/submission/9163878 dreamoon, you are so cute...
tourist makes a new account, dreamoon 2nd on division, a programmer shot himself in a mystrious incident. sad short story :D
Or he may just try one more time:)
Not with the newly increased rating.
As always I finish debugging my E code on examples 2 minutes after round end...
I'm actually hoping it's wrong now, would make me less angry :K
Edit: Yay, TLE! :)
System test started early, but, it is slow. There is always a catch huh...
How to solve Div2B?
Just try all possibilities...
bitagi submitted all 3 problems (A, B, C) in time 00:41 interesting...
Why is the system testing so slow??
9164343
............. //_-
Ты всегда можешь сказать, что просто косишь под dreamoon_love_AA. Я маме всегда так говорю.
о, точно, не зря видимо я занял 898 из 899 мест сегодня)
Чьей маме?
админа
Dear CodeforcesPolice , Look what SaDDaS did during contest time !
The rating update is so fast. Maybe the fastest I've ever experienced.
Still waiting for Div 2 update.
Updated on the moment you write this comment :)
Hey Bro, I can't change the downvote to the upvote. Sorry for that.
Большое спасибо за раунд, я вновь оранжевый, надеюсь сервера опять не упадут, как было в прошлый раз после Рокетона.
И мечта стать международным мастером вновь разрушена, жизнь-боль ;(
accidentally fell asleep during the contest for half an hour :D , and solved problem C after waking up
Still better, than sleeping 10 minutes and then submitting A :-D Especially when no reason for that...
Being relaxed during a contest — i guess you are doing it wrong)
Yeah, purple again C:
Solved B and C, and couldn't get A to pass the pretests (was giving wrong answer on Pretest-7)! Did anyone face the same issue?
http://mirror.codeforces.com/contest/496/submission/9180895
You didn't set variable Difficulty to -1 at the start of for loop which means that it will not reset when you delete new element from array and it will use an old value. I just did that and your code passed.
Даешь Codeforces Round #283.5 :)))
Finally, I became blue. Next stop: purple :)
wow your line is motivated.welcome to bule!
I'd like to talk about time limit in problem D (div 1). I'm really sad, because I spent about 50 minutes on solving this problem and submitted it during last minute of contest just to get TLE on test 30. And, what is even worse, I changed my code just a bit after the contest and got AC.
Here is TLE: http://mirror.codeforces.com/contest/497/submission/9177065
Here is AC: http://mirror.codeforces.com/contest/497/submission/9177860
As you can see, the main difference is that the new code is less legible. Complexity is the same as in codes of others — O(nm), but the constant is just a bit worse. I don't think that making such time limits in geometrical problems is a good idea.
I'm not the only person with this problem — AstroConjecture also has tle on 30.
So I'd like to write my reflections here:
1) Time limit could be less strict when there is no solution with worse complexity that could work with given constraints.
2) There should be one maxtest in pretests. In such problems people often try to write legible codes (it helps with debugging) and they focus less on constants (of course they still focus on complexity). So I think that here lack of maxtests in pretests is a huge mistake.
Fully agree. I always emphasize that constraints should be as small as they can be, so no solution with worse complexity can pass. Here there were simply no other solutions, but on the other hand, 1000 is in fact already very small limit...
But 2) still stands, receiving a random TLE on systests, because our code runs for sth like 1.5xTL is really a terrible feeling, I experienced that few times here and it always costed me sth like 150-200 rating >_<.
welcome dreamoon to div 2
welcome DmitriyH to div 2 too :D
Hello purple! Thank you for a great contest :D
Div2 C, what is it that I'm doing wrong in this code
http://mirror.codeforces.com/contest/496/submission/9178659
I have the same problem, test 15 didn't go through. To me, the test case seems to have clearly more than 4 columns to be removed in order for the rows to be ordered lexicographically. Or did I misunderstood the problem somehow???
http://mirror.codeforces.com/contest/496/submission/9174356
as rajateuler said, one has to go from row to row, not column to column. else it's getting to complicated to decide either the column has to be removed (here is the error).
EDIT: Ignore this post.
I really wanted my name written here but sadly i got the sixth place in the last 3 minutes...
Hi. Can anyone please help me understand why test 2's answer is 2 instead of 3?
case care test code
Shouldn't all columns except the second one be deleted? Because the 1st, 3rd and 4th columns all have irregularities in terms of lexicography. Or did I misunderstand the question completely? :|
Read the definition of lexicographic order carefully. Even though the strings in column 4
aren't in order, the strings
are, so it's a valid solution.
Hey Kynit, i don't understand the definition of lexicographic order.Even i don't understand the second test case how output 2 comes instead of 3. Would you please explain with another example for understanding the definition of lexicographic order ? Thanks in advance.
Let's say that you have string a and b. And for example a=abcd, b=acde.
In string b char on position 2, char 'c', is greater than char on position 2 in string a, char 'b' (c come after b in english alphabet), which means that b is lexicographically larger than a. They don't need to have same length, only one char is enough to one string be lexicographically greater than other.
For example string b=s. Char 's' on pos 1 is greater than char on pos 1 in string a, char 'a', so string b is lexicographically greater than string a.
Superleggera got it right — it's basically dictionary order.
My code for div1B failed on test45 during system testing, and that test case works perfectly on my machine. Can anyone help, what might be the issue?
Dear CodeforcesPolice I got this message during the contest. I've noticed that after the end of contest.
Of course, it is not allowed to ask someone the solution or something like that. Is there anyone who get this type of message from ITDOI during contest?
Do you know Hamidreza Hedayati?
I just know this handles of him:TyperX , hrh2020 ,hamidreza004 , hamidreza.dev , hamidreazshr ,ITDOI.
I know that he has some more handles but i don't know them. I think your next target should be him.
Is the editorial in English ready yet? :) Thanks for posting.
Waiting for English verison of Editorial.:D
.
Notice the "#" sign beside his name. That means this rank is unofficial since he took a "Virtual Contest". Just remove the tick from "show unofficial" above the standings page, and he will disappear.
Probably someone who cannot read well:
Above are "Terms of agreement" when one want to start virtual contest...
Are Petya and Gena from 497B - Tennis Game Petr and tourist? XD
Yep; actually, both of them are quite adept at table tennis which I had a chance to witness at TCO14 finals. =)
Can anyone tell me why my submission 9186328 for problem C div 2 is failing the system test. Here is my algorithm
Starting from the first column, I check if it's sorted, if it's not sorted I mark it for removal and move on to the next column. If it is sorted, I group the rows with the same value at that column and I move on to the next column within each group.
Can anyone please tell me why
is not an answer for following test case in problem 496D - Tennis Game
Ignore this answer.
Why? in testcase 7 judge's output is 0. I can not understand why
is not an answer.
If it would be answer, second player would win earlier than game has ended (testcase is entire game, from start to someone's win).
How would second player win earlier? When the game ends first player wins 5 sets while 2nd player wins 15 sets. As score is 1, they are completing 20 sets together, and 2nd player wins his last set at the last serve of the game, isn't it?
I got it. Thanks for explaining. I missed last "1"
Когда я захожу в соревнование, то у меня никак не подсвечена задача В, хотя я её посылал (даже с полным решением):
Да, у меня тоже самое и во время контеста было.
a very bad and unpleasant round