Всем привет!
4 августа в 18:05 MSK состоится очередной рейтинговый раунд Codeforces #365 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.
Автором всех задач являюсь я, и это мой первый раунд на Codeforces. Советую Вам ознакомиться со всеми задачами, они наверняка придутся вам по душе, да и не зря же я старался :)
Хочется выразить благодарность координаторам раунда GlebsHP и danilka.pro за помощь в подготовке контеста, MikeMirzayanov за замечательные системы Codeforces и Polygon, а также IlyaLos за дельные советы по некоторым задачам.
В этом раунде вам предстоит познакомиться с белым медвежонком, имя которой... кхм... Мишка (ах, моя фантазия). Мишка ещё совсем маленькая, и ответы на некоторые вопросы даются ей не так уж просто. Сможете ли вы помочь ей разобраться с некоторыми из них?
UPD. 5 задач, 2 часа на их решение и следующая разбалловка: 500 — 1000 — 1750 — 2000 — 2250.
UPD. Приносим извинения за доставленные неудобства. В ближайшее время все решения будут протестированы. Вопрос нерейтинговости пока обсуждается.
UPD. Было принято решение сделать раунд нерейтинговым.
UPD. Соревнование завершено. Поздравляем победителей!
Div1: 1. uwi 2. kmjp 3. savinov 4. BigBag 5. KrK
Div2: 1. meteor 2. TmEnd 3. chenjiamin 4. vokeal 5. Denisson
Разбор будет опубликован в ближайшее время.
UPD. Разбор
First Comment!!!
this is codeforces not youtube
I wish high rating for everyone!!!
Really sorry to say but your wish won't be granted until next round. Unrated :(
I cursed this round. I am sorry Codeforces.
At least nobody dropped!
Ok, I knows. But codeforces is not always a rigid place.Some fun is ok. All in all, I am stronger than you.
you stole my comment -_-
Why are you being so rule... Don't you know he is human too??
Anyone else having trouble submitting these problems for practice?
It still says
Pending System Testingfor me...Edit: It's open for submitting now.
Looking forward to a story of Limak and Mishka
Yes, the same problem :(
Let's Help Mishka
Let's not decrease Contribution by this kind of comments!
May be it's 4th August, not 3rd?
Fixed
Is the time correct? Edit: It's fixed now.
Yes, it is ;)
Hello i am rommel
Hi Rommel! Where is Guderian?
Looking forward to a story of Limak and Mishka
Can somebody tell me how to hack?
First you have to solve a problem. If you solved problem A, lock the problem A(in problem page) and go to 'room', double-click someone's (who solved problem A) source code, and click the "Hack!" button. Sorry for the bad english :(
First of all, you need to pass the pretests on the problem you want to hack. When you are done, go to Dashboard and click the padlock which will be on the right of the problem's name. This way you will be able to open every submission for that problem made by someone in your room by going to Room and double-clicking on the cell showing the score and the time of submitting the solution but you won't be able to make further submissions on that problem for the rest of the contest. Also note that you won't be able to use too big test files so in this case you can use a test generator (I think you will see how during the contest), I didn't know that and finished 7th instead of top5 on one of my first contests.
you can find it on google
Today's date: 22 / 23 / 24
and division 21. The task is to take 20 place:)
And the number of fucks given is 20-1
Nice context time, I can watch TI6 after the context :D
I think it's contest, not context :D
my poor English...
Haha I didn't expect anybody on this site of all places to be Dota fans :D
Not only div2 participants play dota. For example V--o_o--V is a very good guy with 5k)).
really? dota1 or dota2?
dota 2. Honestly, I don't know lots of people who play first dota.
Lots of my local OI team trainers are LoL players too.
Good luck everyone
high rating
Why you always announce scoring & duration &... just before the contest ?!
jibancanyang的后援会路过，坐看羁绊妹子上紫，后援会成员过来留言呀呀呀(excuse me...don't decrease my contribution.....haipa..
Pls use English
Actually, I can't read your comment!
啊啊
I think I need a translator or something!
JIBANCANYANG
Ok, I am fighting!Go ahed!
salayou!
Number of problems, duration and scoring distribution will be announced later.perhaps after contest :DWhat does 'Later' mean in Russian?
use google translate :/
Maybe, "never" :D
It means : Any time except before the contest!
Unique Timing...But where's the number distribution? :(
scoring distribution: 500 — 1000 — 1750 — 2000 — 2500
It’s easier to fake a smile and act like everything’s fine than to have people ask you why.
Delayed! :/
By 10 min.
Postponed by 10 minutes...
Is this the first contest on CF for which more than 7000 people registered?
Good Bye 2015 had > 7000 participants (it's a Div. 1 + Div. 2 competition).
Second one after the round that took place right after the color revolution
Delay 15 minutes and the number of Contestants reach 7000+.
7000+...is that a record?
How does the world look through your eyes?
What the fuck is the deal with those inane comments?
Looks like it'll get cancelled or non-rated. I am going to sleep.
todays contest should be cancelled!
+1 to non-rating... 40 minutes for a TLE veredict... really annoying...
It's already 20 minutes while i'm trying to log in...
in queue for more than half hour whats happening
Ультиматум Huyum_nik уже в действии, я так понимаю? :D
I finished B in 10 minutes and successfully submitted it in 28 minutes...
Took 10 minutes to realize a simple wrong file.
There are more than 4000 submissions queued now :-"
That feeling when the first 90 pages of status are "In queue" ...
Is it rated? :P
now that's a good situation to ask such question =)
May be the contest will be declared as unrated.
Codeforces became so popular: Codeforces team should think about improving it's server or finding another smart solution :/
So this time it should be unrated right?
Codeforces, please don't turn into Codechef.
What does it mean ? Please explain.
You would know its meaning only if you had been active on Codechef contests for some time.
В течении 30 минут (если не больше) постоянно выкидывало из аккаунта на кфе и не давало зайти обратно. Это лишь у меня была такая проблема? Началось через 4 минуты после начала раунда.
у всех походу так
That's not deal, I've submitted 45 mins ago, still can't get the result.., sad about that
wow,very fast judging system!
It got passed while I was typing the comment:D
CFOI-_-
You got me:)
Hmmm...... Huyum_nik?
Me off, cause it will be unrated 90% and cause I got no deal with any bitwise ops(C) (that's my mistake I can't really make myself learn something about bitwise ops..), and got no idea how to solve (D) and (E).
bitwise(D)*
After 45 minutes, it finally show the result of my B... And the verdict is wrong anwser on pretest 4 :'(
I accidentally read your nick name as "I am Wrong". Would have fit to your WA perfectly... No offence :)
Maybe, you should have sent a correct solution? There are lines because of such people who send wrong programs.
You are quite interesting...
Раунд не рейтинговый?
лалка
finally , i can see my solutions result. (after 30 min)
After 45 minutes from submitting B, I find out that it's a WA. :D
Got B Pretest Passed 10 minutes ago and still not appearing on standings that I solved it. :D
Is it rated? :D
UPD1: Oh, my B solution is being rejudged.
UPD2: Oh, my B solution has been running on test 1 for over 5 minutes now
UPD3: Pretest passed again and still not showing on standings. -_-.
What a nice rated round. :D
Can anybody analyze the time complexity of this problem?
Did anyone hack successfully?
Submissions sticking on queue for 45 minutes, and you want hacks? :D
just asking :D
Time limit in D is so bad :( n log n solution with segment tree
its not , it has a simple N+QlogN solution.
Segment trees. I wish I could code it
just bit was enough for this problem
Care to explain ??
xor of all dinstinct elements occuring even number of times is equivalent to xor of all distinct elements xored with xor of all elements occuring odd number of times , xor of distinct elements occuring odd number of times is just xor of the whole subarray , so you need to find xor of all distinct elements of a subarray , this can be done offline in N+QlogN in the same way as finding number of distinct elements of a subarray
This can be online with segment tree log^2
This can also be online with persistent segment tree in
per query.
can you elaborate? the online segtree lg^2 solution
Store all nexts (index). Distinct values [l, r] is number of nexts that next[i] (l <= i <= r) > r. This can be with upper_bound. O(log^2) for each query
Are you sure? I thought so too at first, but I found a problem with my idea... You might be thinking something completely different though, which is why I'm curious :D
My flawed solution: Store a set in each node of the segment tree. Add all values on the node's segment to its set. This takes O(n log^2 n) time. And when you make a query, you only need to look at log n sets.
The problem with this: Unless I'm missing something, you can't merge those log n sets efficiently, or get the solution for the entire queried segment from their subsolutions in any other way.
You see the hardest part of this question was to compute the xor of distinct elements. can you elaborate on how you do that offline?
sort queries according to right end point , now go from 1 to N , if arr[i] has occured before , remove arr[i] from last occurance of arr[i] and put arr[i] at i , now for all queries ending at i , xor of distinct elements from l to i is just query(l , i). this can be done easily with a bit
I don't quite understand your explanation. Would you mind giving a code that does this?
Why do we have "xor of distinct elements from l to i is just query(l , i)"?
Refer this with a few changes ! https://github.com/VitSalis/SPOJ/blob/master/DQUERY/dquery.cpp
A great idea!I got it~Thx a lot
Is it similar to Mo's algorithm
Mo's Algo didn't work for me...TLE
Yeah, it got TLE, the best I could reach was prestest 15 after a lot of optimisations. :P
Will you please explain?
Explain++
yep, TLE at test number 14 :( I used BIT Q*logN as well and not pass
After I solved this problem (here's my code: http://mirror.codeforces.com/contest/703/submission/19655570 ), I decided to take a challenge and modify your solution so it will pass :)
http://mirror.codeforces.com/contest/703/submission/19656284
1) add cin.tie(0); cout.tie(0);
2) change endl to '\n'
and you have AC :) Even the second one on it's own is enough. Now it's your part to find out what does this black magic exactly do :P
i don't know why i was forcefully logged out. First submission to problem A: 00:03 & passed pretests at 01:06 anyone else was forcefully logged out every now and then?
Me Too
Yes..During the competition,I can't log in.....T_T
Yep happened while i was submitting B :| Then after 5 minutes, adding www. worked though
Did anyone manage to get through n * sqrt(n) for problem D? Is it even possible to get through 10 ^ 9 operations like that? Spent whole contest trying, guess it is not possible for me. In c++ ran in 7 seconds locally.
I got tle on test case 15 with Mo algorithm. Then switched to (n + q)logn and it passed for pre tests. Was something like counting distinct number in range but xor of those values.
Same for me, couldn't get O(Q sqrt N) to pass
I was thinking of how to find xor of distinct numbers in a range, but failed to. Now I've only solved problem A :(. Mind explaining how you got it?
It is similar to this: http://www.spoj.com/problems/DQUERY/ Read this: http://mirror.codeforces.com/blog/entry/8962 for an offline approach. Here in this problem, just need to use segment tree to update an element at index and calulate xor of a range using segment tree
Keep a XOR segment tree: when you encounter a value for the first time, on index i, in the segment tree update the position i with that value, and rememember that last[ arr[i] ] = i;
And if you've already encountered the value before, also update the position last[ arr[i] ] with the value before updating last[ arr[i] ].
After processing each index i, you can answer all queries that have r = i. You will only ask the segment tree for some query(l, i), in other words, your right bound is fixed.
Personally I did it with BIT, not a segment tree.
Getting WA after about 45 minutes!! I only took a minute to debug my code ... of course not that long That really kills :v :3
How to solve C? Heck i can't even write a bruteforce solution :\
I used binary search on time before start walking UPD: As I can see there are some easier solutions than mine. Nevermind)
Try transforming the problem into the new coordinate space (Time, Y). That is, the first coordinate X is time and second coordinate Y denotes the same thing (distance from bottom to top).
I will write a more detailed explanation (with a picture) after a few hours (I'm still working =)) if nobody writes satisfactory explanation.
PS: no need for binary search.
Imagine that the x axis represents time. If the pedestrian walks at full speed straight up, he'll move with a slope of u/v. Then, you can easily check if he can walk in front of the bus (this line is to the left of the entire bus) and, if he can't make it in front, how long he has to wait for each vertex of the bus to pass (horizontal distance between the line and vertex).
For each vertex, find if it can reach the vertical line before the person can pass the point at which this vertex will intersect with the line. If no/all points satisfy the previous statement, then the person can pass before/after the bus with full speed. Otherwise, you have to go after the bus with different speeds. Start with the lowest (and rightmost in case of a tie) vertex and check the point at which it will meet the vertical line. If you can arrive to this point in a time earlier than the vertex reach time, wait for this vertex to pass the line. If the vertex reached it earlier, then you can move with max speed. Consider vertices in counter-clockwise direction and stop when you pass the highest vertex (at this moment go the remaining distance with full speed).
Instead of moving the bus, just consider the guy to be moving. As the bus is convex we can see that it is optimal to be still for a while and then move at maximum speed. Then we only need to see for how long do we need to wait. Again, as the bus is convex, we just need to see the time needed to pass right through each point and store its maximum (for point (X,Y) it will be X/V-Y/U). Thus, if we can't just walk from time 0, (i.e. among the values calculated there is a positive and a negative value) we will need the maximum value calculated plus W/U, else its just W/U. (sorry for possible errors, first time commenting :) )
Supplement visual guide to the comments above :)
Transformation of the pedestrian's path.
Strictly vertical path in XY-plane becomes tilted to the right in the TY-plane.
Convex bus undergoes absolutely the same transformation, but it doesn't become tilted! After that we should look at the intersections of the transformed figures.
Here is neat solution of the guy from MIT : 19629479
is it rated?
How to solve D??
I use a similar offline-algorithm like http://www.spoj.com/problems/DQUERY/ try to calculate the XOR-sum of distinct number in a segment then the ans = the XOR-sum of distinct number in a segment ^ prefix[r] ^ prefix[l — 1]
prefix[i] means a0 ^ a1 ^ a2 ^ ... ^ ai
I liked B and C but don't know how to solve D. There are so many ideas in my head with different time and memory complexities using huge amount of build-in data structures and written by my own but nothing of this, I guess, can pass tests. Please help me. What is your solution for D? UPD: I think, because of 15 given additional minutes, round must be rated.
Did you use Convex-hull in C?
You don't need to compute convex hull, if you are already given a convex hull ;)
Oh, i'm sorry. I mean traverse convex-hull clockwise to get the answer.
But there can be some good ideas using parts of Graham's scan
No, as I said above, I used binary search on time before start walking and check used simple geometry like oriented triangle area
let's convert it to unRated one :D
Надеюсь будет разбор? (в отличии от раунда №364)
http://mirror.codeforces.com/blog/entry/46283
Did anyone else feel this contest was hard?
Yes I solved only problem A and bugged for B ;(
Same. And it didn't help that I thought my B was pretests passed for an hour and then realized it was actually WA and couldn't figure out how to finish it. Pretty hard contest imo.
Anyone who's D's solution passed in spite of using cin and cout ? I did use segment trees, got TLE on pretest 10.
19633422 can u tell me why my solution for D task is so slow?
Now work:) printf and scanf. I thought that cout/cin is faster with ios_base::sync_with_stdio(false) than printf/scanf
Could try printf / scanf, the input is huge.
I have been in similar situation, you can try two optimizations: 1. Use scanf and printf instead of cin and cout. 2. Use dynamically allocated array using malloc, new or global array instead of vector. Time limit problem will most probably go away. And segment trees are slow(not asymptotically but practically) so you will most probably have to do these optimizations whenever using them.
I thought it will be a unrated so i stopped doing contest after submitting B and start watching a movie. Now one a mine facebook friend ping me and realize me that it won't, pathetic :(
This was evil! I was about to hack this :P
How do you hack this?
You don't. Because you are aiming for int overflow but, since the defender has defined int as long long, your hack will fail.
First applied Mo's in problem D -> TLE. Used segment tree, got run time error. Thought the bug was in to segment tree so removed it with BIT and again got run time error. Can anyone tell me bug in my submission.
It would be such a shame if Codeforces ignores the mistakes and makes the round rated. :)
btw i'm saying this although I did good and I would benefit if it's rated
And for god sake, why the hell isn't my pretest passed showing on standings?!
Please, lets convert this round to unrated.. Because long checking and many bugs..
this contest should be declared unrated .
Making this round rated proves how unserious this website is
the terms was equal for everyone. you guys are not logical :/
this round was the worst round ever the server dies what is this shit !!!!!!! :(
Why do you care if you didn't participate?
thanks for offering the problems,i like this contest,especially problem D,
How to solve E?
I think it's dynamic programming, suppose k=p_1^a_1....p_s^a_s let F(b_1,b_2...b_s,w) be the minimum number of integers among a_1,a_2...a_w you should pick to make the number a multiple of p_1^b_1.....p_s^b_2. That works to get the minimum number of integers needed, although I'm not sure how to change it to get the actual set of number.
This can be easily represented as divisors of the input k, which can be found in
time at first.
Just solved E using iterative DP with state[index,value to make] with scary timing..!! :3 from the looks of it there should be a faster soln i think..!! :/
I solved it by bitmaks dp, since 2*3*5*7...*31*33 > 10^12 , so it should probably fit in the time limit. I can't submit it check though, I've heard that the TL is pretty tight.
And lucky me just read this question's (Here) editorial and learn the approach, and yes you read it correctly, this question has a similar constraint yet a 2 second TL ...
My submission for 2nd question was checked after 50 minutes and I got a WA on pretest 4 when I was implementing C's solution. Please make this round unrated. It would be better. Many of the coders have faced this problem!
Решение C без вращающихся каллиперов, бинпоиска и прочей фигни: Посортим точки по Y.
Проверим, правда ли мы можем пробежать перед автобусом. Для этого мы должны для каждой точки автобуса проверить, что в момент, когда она пересекает зебру, мы находимся не ниже. Если для всех точек это выполняется, то мы просто можем пробежать и это, очевидно, будет наибыстрейший вариант. Ответ — w / u (просто бежим с макс скоростью).
Иначе нам придется пробежать за автобусом. Чтобы найти минимальный ответ, просто пойдем по всем точкам снизу вверх своеобразным сканлайном. Тогда для каждой координаты Y у нас есть только два ограничения : время, в которое i-ая точка проходит зебру и время, которое нам придется бежать до неё от предыдущей точки. Возьмем из них максимум. Ответ будет лежать в y = w.
А можно просто построить касательную к многоугольнику с наклоном (что делается нахождением точки с максимальной проекцией вдоль нормали)
к многоугольнику и заметить, что ответ это расстояние от пересечения этой касательной с прямой y = w, деленное на v.
Еще чуть проще: то же самое, без сортировки.
(+ нужно проверить, что если автобус частично пересекает на момент 0, все считается правильно).
Секундочку, а как без сортировки проверить, что мы можем пробежать за автобусом?
Но ведь это проверка, что мы можем пробежать перед автобусом, а не за ним
Если не можем пробежать перед, значит, можем только за.
(проверить для всех точек)
When after submitting A , my submission list was empty ,it was such a relief. But after 10 min my friend told me I have one submission pending I knew from that moment that this contest will judge my patience :P
I wish that Codeforces judging system were faster so that I could submit my solution 1 minute after the contest had ended.
BTW Is there a way to submit a solution quicker after the contest ends?
It seems long queue affected many participants of the contest. I counted number of users which got verdict after 15 minutes of waiting and verdict was non-OK. It is about 2000 participants.
Taking into account such a significant number, we've decided to make round unrated. Sorry about it.
Today long queue is not a systemic issue, it is a result of several unsuccessful matches. Be sure, I'll do my best to make the next round quickly judged.
====
Похоже, что длинная очередь существенным образом задела большое количество участников. Я посчитал у скольких участников тестирование было в очереди более 15 минут, а затем был получен вердикт не-OK. Таких участников около 2000.
Принимая во внимание такую значительную цифру, мы решили сделать раунд нерейтинговым. Приносим извинения за это.
Сегодняшняя проблема с очередью не системная, а результат нескольких неудачных совпадений. Можете быть уверены, я приложу все усилия, чтобы следующий раунд тестировался быстро.
nrO Mike Orz
Dear Mike, I submit twice because of in queue judgement. Both of them passed pretest, at 47min and at 101min, but why it shows the time of the last one,at 101min?
You're second submission is considered as a resubmission which costs penalty and the first submission will be ignored.
thanks :)
Nice, last time when I didn't do well, it was rated, this time when I do well its, unrated. This is life I guess..Highly unfair
What if you get all FST?
All my solutions passed, sorry for ur pessimist attitude
So when you passed all the solutions, you say that 'Mike you should make it rated'.I just do not think it is fair in that I don't believe if you, unfortunately, get FST, you will still say that.
Same here. I thougth that I'd become blue again :)
Make it optionally rated please.This is so wrong
Why wrong? Getting WA in the middle of the contest at a very easy problem affects a lot your standings,not mentioning that codeforces was loading a page in about 2 minutes.
Usually when these things happen on a site that involves some type of competition, you have to take a decision. Implementing both is very impractical. Do you realise how much time would it take to manually update rating for everyone who wants? and putting a time implementing a feature for it so just when only something like this happens it is used, is a waste of time and money. ( And it's also not fair, because if some people could actually submit solutions, your rank might probably be a little bit down).
These issues rarely happen on CF. Just deal with it as if it was an ED round. No big deal, if you did well this time, you can pretty much do it again in future contests.
khar :/
What does "unsuccessful matches" mean ?
Unlucky coincidences.
How are solution judged? I saw pretestes passed submission for A increasing which show that judgement was going on. However no solution appeared for like first 45 min for B. Isn't it by submission time?
In my opinion people who got problem 1 or 2 wrong deserve to lose rating, but it's not a big deal either way.
It is the second time when I do well in contest and then it becomes unrated.
Q_Q
Mike why won't you try load balancing to more VMs, from example amazon web services or smth similar. They'd be probably necessary only for the first hour of the competitions when the load is quite bigger.
То что была задержка 15 минут, это не так много в тем более это было в начале ближе к середине и еще добавили время. У кого не прошло решение, и они ждали около 15 минут, они все равно знали об этом еще во время контеста и у них было много времени что бы исправить это. Это единственный контест где я так хорошо написал для себя, (никогда не был топ — 50) и сидел до очень поздней ночи что бы написать нерейтинговый контест и еще ждать пару часов своих результатов и потом увидеть что " UPD. Было принято решение сделать раунд нерейтинговым. ". Бомбит ужасно!!!
Я узнал вердикт через 50 минут,ещё и 15 минут ждал чтобы послать.
Это ведь было только в первой середине контеста.
I think that I solved B, but 10 seconds after the contest over when I try to submit it.
I will submit it again when system testing is over,, I'll be sad if I got Accepted verdict...
It's may be the worst feeling when your code remain in queue for a long time.
Anyone can see disappearing Huyum_nik message at the first place in comments? It appears on my screen for a second and then disappears until I reload the page.
As soon as i tried to submit solution i got logged out showing apache format error and since after repeated trying manage to submit after 40 mins later. May be same case with some other peoples too so would it be called a fair codeforces rated round ?? :-(
Something strange.... int this codeforce round.... WHO TO CALL??????
(Just a relaxing comment,don't take it so seriously Xp)
woops, got wrong answer on C because I used int instead of long long, to check if the dude could pass before the car arrived.
why not double
I wanted to avoid precision errors, I just checked if X[i]*u >= Y[i]*v.
Я прошу прощения, но надо было все-таки делать раунд нерейтинговым в течение контеста, особенно когда у многих повываливались аккаунты и образовалась огромная очередь, а не через час после его окончания, когда все уже примерно посчитали свои результаты. А то тем кто написал контест нормально это правда обидно.
Were the submissions in a queue, or in a stack? :p :D http://imgur.com/t9AsTHt
PS: I don't know how to paste image here, can anyone please help me?
I think the problems for this round were pretty good (I struggled quite a bit honestly) but it sucks that the server was garbage the entire time. I didn't even know my B was WA until more than halfway through the contest. Overall, lots of nice problems just horrible circumstances. Hopefully Eran can write some more problems another time.
Edit: An editorial will still be released as well right?
I agree! The problems were excellent — hopefully they can come back for another round :)
what нахуй exellent problems?? просто realization
Блеа, ну какой нерейт? Ради чего я два с половиной часа потел? :_(
Внатуре сначала все нервы из-за очереди теряешь, потом привыкаешь, начинаешь тащить и тебе говорят, что иди в баню shit my shit
В чём проблема, если был бы он рейтинговый? 2000 человек долго ждали своего WA или TL. Ну и ладно. Нечего слать всякую фигню.
И как по мне в данной ситуации было бы правильно, не делать контест нерейтинговым, а тем кто в минус написал — тем не убавлять рейт, а тем кто в плюс — прибавить, если уж что-то делать. Но я не думаю, что сделают такое исключения для этого раунда.
А чё не убавлять-то? У кого должен убавиться, они что, хорошо написали?
Ну я же написал, "если уж что-то делать". Да и как по мне, я согласен, серьезной причины контест делать нерейтинговым не было.
А при чем здесь автор?)
Напротив, это, наверно, самое неправильное решение :)
Уверен, вы говорили бы совсем по-другому, если бы ваш рейтинг должен был упасть, а раунд все-таки сделали рейтинговым, и ваш комментарий имел бы противоположное содержание, но с тем же посылом. Но речь не об этом.
1) Команда Codeforces до самого конца раунда стремилась оставить раунд рейтинговым. Если этого не произошло, то, значит, на то есть веские причины. Я понимаю, что "бомбит", но вы все же не один участвовали в соревновании.
2) "тем кто в минус написал — тем не убавлять рейт, а тем кто в плюс — прибавить" — с такой логикой рейтинг можно вообще отменять, всем хорошо написавшим присылать конфетку, а всех плохо написавших гладить по головке, чтобы не обижались. Да, и поищите по статьям Codeforces что-нибудь про инфляцию рейтинга.
3) Будьте рады, что не покинули раунд и спокойно решали его задачи, получили нужный опыт. Если вы переживаете за то, что это был один из тех раундов, где вы выступили неожиданно хорошо, то подумайте о том, не связано ли это с тем, что некоторые участники просто отвалились, а для укрепления значения рейтинга нужно еще не раз хорошо выступить.
Очень обидно, что контест сделали нерейтинговым. Было бы идеально сделать так например (наверное) Кто ждал сабмишн больше 10 — 15 минут им сделать нерейтинговым, а остальным рейтинговым. (Так как 10 минут иногда и в других контестах ждешь)
Разделять участников уж точно никогда бы не стали по понятным причинам. Хотя да, я тоже хотел бы, что бы мне обновили рейтинг, хорошо написал)
The round is unrated.I wish I can get higher rating but failed. :) I wish next round is rated! :)
Единственный раунд, где я затащил, пожалуйста не делайте его не рейтинговым.
Тут все, кто забил на очередь (и кто нормально отлаживает), затащили. Я, например, занял 92 место, решив 3 задачи. В других раундах за 3 задачи у меня было 500+ место.
Каждый контест специфичен!
I liked the concepts of the problems, they were very interesting, but I have a couple observations to make:
But I think the writers have good potential! They are able to write hard, interesting and complex problems. I wish them luck in the next rounds they will (hopefully) write.
P.S. I find it is in good taste to make the round unrated, mostly because of the huge server issues. Thank you for that.
If 1 ≤ n, q ≤ 2 × 105 on D then Mo's algorithm will pass easily but i think this way the problem will be very stupid,just apply a well known algorithm.
The limits are ok,i looked at your code and saw that you used map of vectors but it is very very slow.
Yes also 1 <= N , Q <= 1.000.000 made the time limits even tighter
:c
Sorry for that, it just burned quite a lot.
When will the problems moved to practice and editorials published ?
Congratulations for what? For doing the best round in their lives only to realise its unrated?
We are sitting here not only for ratings, man
Когда закончится тестирование?
Although there was sure some inconvenience, I still think it a good contest~ Many thanks to contributors~~~
The delay and some other problems are largely due to the large number of participants and div 2 only. It doesn't affect that CF is still a great community to improve coding skills. It just mean that this site is becoming more and more popular and the server need to be upgraded. I think we should support the site rather than complain the organizer or the limited source of the site.
That's it. Just feel a little sad seeing so many people blame the organizer and the site.
Is the testing gonna end any time soon? I was hoping to submit some code.
For problem no B 703B - Mishka and trip , Why my this submission : 19639339 got accepted verdict but this implementation, 19639538 , got wrong answer? When I used cin/cout its got accepted , but for scanf/printf it gives me wa verdict. Please help .... Thanks in advance.
Why Round is UnRated !!!? (Unusual)
Because life can be cruel sometimes, but you need to tough it out.
Все прям раскудахтались "дайте мне мой рейтинг, я топ 50", вы думаете если б с кфом было все хорошо вы бы были в этом топе? А то успели сдать B таску до того как лег кф и почувствовали себя богами.
Why unrated? It's unfair...
It's unfair...that'sWhy unrated!Is it really that the contest was unrated?
Hope the editorial will not come out as late as the number of problems,duration and scoring distribution did.
Well,Why is the time limit of E is 1s? Some of the Accepted source takes 997ms to passed.And I was TLE because of the large constant.QAQ There are same people's Sources didn't Accepted because of the same reason.Could you make the time limit longer?
These are Accept Sources: 19634240 19636289
Nice Chinglish
I am not quite familiar with geometry stuff, I wonder what's the idea behind judging if the point we are checking is the front or the back of the bus?
Edit: I think I have an idea now... Almost forgot about high school maths. Btw, is everyone else's contest page show "pending for system test" right now?
Edit2: Just noticed "input are given in counter-clockwise order" FML
Could you explain your idea please? That problem had me completely stumped.
My implementation: http://ideone.com/mFVRYD
(I can't submit it right now — it says the contest is still pending for system test, so I can't guarantee this code is bug free, as I always miss out small counter-case details. I am pretty sure the approach is correct though.)
Case 1: The pedestrian will not get hit by the car if he rushes through as fast as possible — in this case we just have to check whether he will reaches point (0,y) earlier than each (x,y) of the car.
Case 2: The pedestrian will have to wait for the car to past through first.
In this case we just consider everything as the back of the car, and sort all the vertices in increasing y-axis value. Then you just check for the later event — the pedestrian reaches point (0,y) or the point (x,y) of the car passes (0,y). And as a smart-aleck I missed this obvious observation when I coded, instead I did the following in my code.
We can check from the lowest point of the car, the sequence of edges which starts from it and has a positive slope is the parts where it could possibly "limit" the pedestrian speed as a part of the back of the car. (This is because it is guaranteed the vehicle is a CONVEX POLYGON, and it is convenient to implement since the edges are given in counter-clockwise order.) Again we check for the later among the two events mentioned above — it's fine to just check these points anyways. Don't forgot to calculate for time (0,0) -> (0,ymin) and (0,ymax) -> (0,w)
UPD: Just rewrote the code in a much more simple fashion, this should be easier for anyone to understand the idea. http://ideone.com/ZjTybR
My idea is similar. I implemented it during the contest but after my solution, which past pretests, was judged with the system tests gave WA#12. I too have the problem with still pending system testing as I wrote below. Here is my implementation:19631048.
I think you miss out cases where miny>=w and mawy>w.
Here is a hack case for you:
5 1 1 2 1 2 3 1 4 3 3 4 1 4
It's just the test case 1 with w=1, the pedestrian is able to rush to (0,1) with ease, yet your code outputs 3.0s.
(Whopos just read the constraints again... nvm it's guarantee every y<=w)
OK. So there has to be something else that is wrong.
I found out my mistake (it was in the second case). Here is the AC implementation: 19664924 (complexity: O(n))
I'm new here, why is the contest unrated? Because of the delay time caused by long queue?
Probably yes, since it has cause unfairness in terms of rewarding points.
How many machines does Codeforces have?
Unrated :(
There were amazing beautiful problems which worth thinking! rating isn't the priority always!!!
For problem no B 703B - Mishka and trip , Why my this submission : 19639339 got accepted verdict but this implementation, 19639538 , got wrong answer? When I used cin/cout its got accepted , but for scanf/printf it gives me wa verdict.what is wrong with it?Could anyone explain please ? .... Thanks in advance.
you made array with a variable as the size!!!! amazing!!! i don't know but maybe the problem is from this miracle!!!
Please anyone help me with that problem
Is there someone else having trouble submitting code now?
It just says 'You can't run practice now or contest does not support practice.'
I see some submissions, but I can't submit still.
When I enter yesterday contest now, it still says pending system testing (and of course I can't submit and see what are the tests of the tasks). Maybe there are more people with this problem. I found that this problem is on the devices (my laptop and tablet) where yesterday I was checking the standings for a lot of time and for example if I open codeforces on my phone, there is no such problem. Could someone offer me some advice or a way to fix it?
UPD: Now the problem mysteriously disappeared. Finally the contest finished for me :). Does someone still have this problem?
UPD2: The problem returned again.
Please Switch on Practice for this contest.
It shows
Contest not over and you cant practiceis O(N * (number of divisors of K)) supposed to pass in E?
Our correct solution has complexity O(n * divisors(k) * primes(k)). I will try to publish editorial as soon as possible.
WTF, so the problem is only optimization!
Well... That's it! We decided that otherwise it will be too easy for the Div2E.
Do you think excluding O(n*divisors(k)*log_gcd) solutions was a good idea with author's O(n*divisors(k)*primes(k))?
Yep. We tried to exclude such solutions. However it seems like not all tests were good enough.
Guessing author's constant optimizations — yeah, it is what problem E must be.
This round turns into unrated! it's so disappointing!i hope this type of inconvenience won't happen again :/
Someone help me understand... Why is the contest still pending system tests? I can't even submit a solution now. O__O
Its taking forever for the system testing to finish. I am not able to submit solutions to any of the answers to yesterday's contest.
Why one day after contest it's on "pending system testing" level?!
Please publish the editorial and allow to submit the solution.It is almost a day now... UPD :- It is published now....
Will O( N SQRT(N) ) work for D?
No. I had n log n and tle
what was your nlogn idea? you must be calculating it wrong, the intended solution is nlogn itself.
I sort queries. I have segment tree which can make xor on range and can return xor value of range. I iterate through input data and do xor(1,last_place[input [i]], input [i]). In i step I have in tree data about xor(only for numbers with even amount of occur ) for ranges [1,2,3,...,i;i]. Now i can just check valueInTree(query[i].start,query[i].start).
Now work:) printf and scanf. I thought that cout/cin is faster with ios_base::sync_with_stdio(false) than printf/scanf
Can't you just check it yourself? Just multiply them, ...and tada, the answer appears within a second!
i understand its 10^9 but it is a bit peculiar that the time limit is 3.5 seconds and looks like it is so to make such solutions run
А разбор-то будет?
Будет. Уже есть. Но возникли проблемы с его отображением. Скоро обещали пофиксить.
I have tried to provide an explanation for Problem D here
I have provided an explanation to problem D here
Still pending system testing. Why is this problem caused and is there some solution?
Editorial Please ..!!
Editorial is ready, but there are some problems with displaying it. Still waiting fixes.
Thank you! It's so nice when authors answer the comments.
Please allow us to submit solutions now
Has anyone solved Div2D with persistent segment tree . My submission (Code) is giving Runtime Error on TestCase 14.I don't have any clue of the reason and have allocated more than enough memory (I think). The idea of pst's
root[i]is to store xor of distinct numbers which are as close to it as possible.Look at constraints, 211111 is not enough.