Всем привет!
Сегодня состоится второй и последний регулярный рейтинговый раунд, составленный с использованием задач VK Cup 2016 Final Round. Разумеется, как и в предыдущий раз, был дополнительно подготовлен набор простых задач, чтобы контест был интересен всем участникам.
В прошлый раз в комментариях указали, что я забыл поблагодарить MikeMirzayanov за великолепные платформы Codeforces и Polygon. Исправляюсь, Миша, реально норм :)
Разбалловка будет опубликована ближе к началу раунда. Желаем удачи и красивых решений!
UPD1. Разбалловка div2: 500-750-1000-1500-2000-2500. Разбалловка div1: 500-1000-1500-2250-3000.
UPD2. Соревнование завершено, поздравляем победителей!
Div1: 1. ainta 2. W4yneb0t 3. Petr 4. muratt 5. kcm1700 6. Vercingetorix 7. Tinsane 8. Reyna 9. aid 10. zemen
Div2: 1. MinamiKotori 2. Ancient_mage 3. WhatTheFua 4. Yanba 5. macieck9 6. OMRailgun 7. radoslav11 8. zhsh 9. skywalkert 10. abgnwl
You also forgot to tell the main character of the problems.
There is no main character in the statements this time.
Old driver will fire his car!Come on, become candidate master!
DI DI...
di di student’s card
don't forget to add codes on editorial as previous round.
LOL it should've been
DONT FORGET TO WRITE AN EDITORIAL
Where are you tourist? :(
He took part in the onsite event, thus is unable to participate in this round.
Why the fixation on tourist to get top rank? It may be EvenImage.
ba dum dis :P
how many tasks are in this problemset ?!!!
how many tasks are in this problemset ?
how many tasks in this problemset??!!
petr now
a week of Petr
today EvenImage will be the hero :D
When You get -116 in rating after getting Rank #3 in div 1 :O
want another Christmas tree!!
Is tourist travelling？-_^
This
666
New king of the iron throne of codeforces is Petr now :). tourist is busy in westores and hoping to see him to fight for the iron throne of codeforces again :P
You watch too much game of thrones.
what's wrong in that?? It is the most amazing tv series so far i have seen. I suggest u must also watch to get something from nothing ;)
Btw, i've watched every single episode of this show, But it didn't improve my coding skills at all. ..hmm weird, isn't it?
I had never said watched it at the stack of your coding. And all the time coding is impossible even for tourist , petr too.. When i m tired and for refreshment i watched to gain my momentum again. So it helps me to back to coding..That's how it helps :p
I'm Really surprised :D
I hope I'll be Specialist :))
->-> Thanks A lot <-<-
Guess it will be a colorful contest ;). Good luck everyone :)
what if mike Participated in one contest ? .. won't be great contest :p !?
Wish good-luck to all. Happy Coding :)
Всем удачи)
Всем много удачи!)
Game of codeforces throne likely to be unseen today as neither tourist nor Petr have registered so far! Can TooSimpIe make it happening today?
Petr had registered.
Petr got -116 and tourist become top rank again!
Scoring distribution?
Tired of pokemon commercials.
Seems like I can't concentrate on the contest with police helicopters hovering around...
police helicpters?
What did you do?
Live in Munich and work near OEZ
The shooting was reported about an hour ago, But you commented about 90 minutes ago, wtf? Are you involved in this? :/
Because police helicopters were there much earlier than any reports. And my colleague who left work a little bit earlier reported hearing shots (and hidden in nearby home)
I also couldn't concentrate on all past 30-50 contests which I participated with missiles falling around me.
Said like a boss :D
You deserve a special competitive medal, dude. I was really surprised with your performance in the last ACPC contest when you became second on the Arab region alone because your teammates couldn't get visa for Egypt. You live in the most dangerous city in the world where you are not sure how your tomorrow is going to be. Go on and keep competing, you are a wonderful example and inspired a lot of people! May Allah keep you all safe.
You forget about electricity shortage :D .
Edit: It's too late to delete this, so I'm sorry for taking up some unnecessary space. Basically I made an incorrect assumption that I'm not sure is legal to post here during the contest.
Is anyone thinking the sample test case #2 for D is incorrect possibly?
Here is my understanding for the second sample test:
this is already more than the answer the sample case gave.
I misunderstood the problem in the same way.
That's how I understood it as well. Maybe we're just thinking about it wrong? But that's the only way I can see it.
I think the return of the bus can be neglected.
Bus can go non-integer amount of time.
I still don't understand how you get that low number. The lowest I could get is:
+ 
+ 
= 3 + 1.5 + 0.75 = 5.25
I thought same at first.
Same here.So I left it and went for E. But was too slow.
its easy ... SPOILER (HINT) ahead . . HINT : all of them (all n) and the bus will reach destination at the same time ...think about this..
Yes, I also thought so. In fact, according to that, the time only dependes on the last guy and there are some inequalities with the others. It was so weird :c
Students can get off the bus at any point. You are assuming that students gets off the bus only at the end.
I strongly believe that it should be mentioned explicitly to avoid those confusions. But, I understand that it is part of the contest.
So how about the bus take a student 3 unit far everytime, shouldn't it take 4.5 time ?
I was wrong
Oh, and here I thought "as well as the reversal of the bus ... can be neglected." indicate that it doesn't take any time for the bus to return, there go my first hour into the contest =.=
I spend 1:00 too...(And got 150 points because of 10^-6... :( )
What is it supposed to mean then? "the reversal of the bus ... can be neglected." made me think it took no time for the bus to return as well.
It means that after the bus moves some distance from left to right, it can turn around and start moving from right to left in zero time. The time taken to turn around is zero.
OHHHHHH turning around ok got it. Thanks!
You can do it by using binary search on time. You know the optimal way is to make all students arrive on the same time. So, If time is set, you can calculate the 1.28s and 0.42s in my post when the time is set in 4.68s.
Could you please include an explanation for Div.2 D second example?
When the bus takes some students (or maybe only 1 student) it will be more profitable if it doesn't take them to the final. Think on this a little bit and you will get the second example.
I still don't get how I decide where to leave each student then. I thought about binary search but wasn't sure on what to apply it / conditions.
Ok see if the bus takes some student directly to the final then every peace of time after that these student will not be doing anything they will just wait on the final, but if the bus take them some distance between the final they will walk during the transportation of the other students and that will reduce the time.
Ok, I drop them before the final, but how do I know how much before the final? As in, at what position to drop them?
Wait for analysis.
let maximum people bus can carry be n and total people is N. So bus can make ceil(N/n) trips. You have to drop people such that last set of people carried by bus reach final point at the same time when the rest of people reach.
I thought of this logic but wasn't able to implement.
This idea is indeed correct. It implies that all persons need to be carried the same distance
d. The bus then makess = ceil(n/k)trips from start to end. The total distance travelled by bus while carrying is thend*s, total distance in reverse isd*s - l(since we ended at distancelfrom the origin). Total time is thenT = (2*d*s - l) / v2.Now lets take a look at a passenger. It is carried by bus for
dmeters, and walks distance ofl - dmeters. Total time isT = (l-d)/v1 + d/v2.We have two equations with unknowns
Tandd, we solve forTwhich has exactly one solution (provided thatv2 > v1) and voila, we have aO(1)solution.I would say it is not particularly easy for a Div1A problem.
It's not productively always go to end of way by bus.
Can you explain more? I figured out this has to be the case but couldn't use it to solve the problem. :/
Good contest with good problems! Hopefully everyone did well and learned a lot today. :)
В задаче B div.1 Nlog^2N предполагалось отсечь?
Даже если и не предполагалось, то отсекли:D
ЦД-шка чет не зашла:CC
Там есть решение за O(n), так что ничего удивительного.
и как ее так решать?)
Подвесим дерево. Очевидно, выгоднее всего, чтобы все пути, которые мы выберем проходили через корень. Это можно сделать, если в поддереве каждого сына корня не более половины университетов. Тогда ответ — сумма глубин всех университетов. Если есть сын, у которого в поддереве больше половины университетов, то нужно соединить все осталные университеты с университетами этого сына и решить для него задачу рекурсивно.
Как выбирать с какими вершинами максимального поддерева соединять, а с какими — нет?
Можно передавать в качестве параметра функции количество вершин сверху, которым нужно найти пару. Тогда нужно будет их соединить с университетами того сына, в котором их больше половины.
Можно так: рассмотрим каждое ребро графа. Допустим, что по одну сторону от ребра X вершин, по другую Y — тогда в оптимальном разбиении по ребру всегда будет проходить min(X,Y) путей (показать просто, если рассмотреть перестановку путей). Потому просто считаем количество университетов в каждом под дереве (X) и выбираем минимум между X и Y(что равен k*2-X).
Nlog^2N в Б div.1 предполагалось отсечь?
Если даже и не предполагалось, то отсекли:D
ЦД-шка не зашла :C
Could Div 2 E be solved by keeping count of number of childrens if a subtree that are in the 2*k vertex list. And then counting how many times an edge u-v would be used depending on something like min(count[v], unpairedLeft — count[v])?
Do you mean problem E?
Yes sorry
Any ideas about this solution by ainta? It pairs university i with university i+k on the Euler tour.
It makes sense intuitively, but why is this correct?
can you elaborate your approach. ?
I tried to explain it better here. That unpairedLeft should have been 2*k only.
Can you explain the correctness ? What if that particular edge isn't included in the 'best' solution ? Like 2 nodes in the subtree of v pair among themselves ?
This was the same reason why i couldn't submit this during the contest. However thinking now, lets suppose that we have choice to go through the edge u-v or pair 2 vertex in subtree of v (name them as a and b).
Assume we pair a and b directly. Distance b/w a and b would be depth[a] + depth[b] — 2*depth[lca(a, b)]. Notice lca(a, b) is always in subtree of v, so we can reduce the subtracted term 2*depth[lca(a, b)] to 2*depth[v] if we consider using the edge u-v and also depth[v] <= depth[lca(a,b)] Hence choosing the edge u-v will always maximize the answer
To what are you comparing depth[a] + depth[b] — 2*depth[lca(a,b)] ??
If we pair a and b, addition to answer would be depth[a] + depth[b] — 2*depth[lca(a,b)]
However if we don't pair them directly, but pair each of them to other vertex on other side of u, then addition to answer would atleast be depth[a] + depth[b] — 2*depth[v] + 2 (the 2 for edge u-v)
Many thanks to GlebsHP for a nice round.
My code fails for pretest 11 for problem C .ANY idea? http://mirror.codeforces.com/contest/701/submission/19344527
I failed the same test, I am very curious. Seemed like an easy problem
isn't it "baacdabc"?
mine is giving is 4
I found a counterexample for mine.
My solution says 4 but correct solution is 3.
Your code finds some interval, not necessarily the shortest one. Consider an example: 8 abcaabbc Your code will first move l from 0 to 4, leaving r=7, and then stop on "abbc" getting 4 whereas the returned value should be 3 (the first three letters "abc").
Beautiful Div1-B. The problem seem impossible at first, but after you switch your point of view (from vertex to edge), it become very easy.
would you mind explaining a little bit why?
For each edge, we want to count how many time it is used in the maximal sum, and that number equal the min of university count for the subtree from each vertex of that edge.
Because there is no hack in Div2-B, can we consider Div2-B's pretest is system tests?
UDP: I know the answer now. The author may add some more tests.
Implemented a solution for Div2-D using ternary search optimization, really nice problem, unfortunately my solution works but it is too slow i didn't even submit it (a lot of recursive calls going on). Curious to see what the real solution is :D
A O(1) mathematical formula exists.
T = el / (ev1 + v2 - v1)
Can you explain your formula?
Let us try to make all people reach the end at the same time. So every person has to travel by bus(at most once, as given in statement) by the same amount of time.
So, let distance travelled by every person in bus be P. If bus picks up some people at point A and they disembark at point B, then it needs to travel (v2 - v1) / (v2 + v1) * P(let this be equal to Y) back to get to other left people, because they would have travelled some distance on foot with speed v1.
Let Z denote the number of trips bus has to make, it is equal to ceil(n / k). Therefore we have a relation, bus goes forward Z times, and goes back by the amount Y, Z - 1 times. Add these up, and they should equal L.
That is, Z * P - (Z - 1) * Y = L. So we can find P now. Once we know P, we can find the answer easily.
Could you, please, explain Y = P ×
a bit more?
Why do you divide by v2 + v1?
Take a paper and pencil, draw a line segment AB of length P. Now we will imagine that bus goes from A to B, leaves children at B and then returns and meets other children who started from A at some point C on the line segment.
Time at which they both meet will be equal. So equate time( = distance travelled/ speed ) of both and you will get the formula.
Time for bus to travel from A to B and return back to meet students who travel on foot (at point C) is
Time for bus to travel from A to B is
Hence, time for bus to return from B to C is
, which equals to 
.
Therefore, DistanceBC = t * v2 =
* v2 = 
I understood everything before this equation Z * P - (Z - 1) * Y = L. How is the difference(or sum, since its written sum above) equal to L?
Z = ceil(N / K).
As everyone reaches the end at the same time, we have to make exactly Z trips in the forward direction. Naturally, when the bus goes forward the last time, it should reach the end point with all children and it won't go back.
Therefore trips that bus makes going back is Z - 1. Therefore, bus goes Z times forward and Z - 1 times back. We have to subtract them and it should equal L. Try drawing it on paper, by making exactly ceil(N / K) trips forward and ceil(N / K) - 1 trips back.
a simple mathematical formula:d = [(n-1)/k]+1 ans=l/v2*((d*2.0-1.0)*v2+v1)/(v2+(d*2.0-1.0)*v1);
Isn't div 2 D binary search on time ? But can anyone layout the conditions ? Same as div 1 A.
I was thinking that you should drop them off at a point b such that the time remaining after you drop them off multiplied by the walking speed of kids is equal to the remaining length.
http://mirror.codeforces.com/contest/701/submission/19348156
Yes. I solved it like that by fixing time using binary search.
Div2D/Div1A: Can anyone explain what is wrong with this approach?
2 groups of walkers, front and back. In the beginning all pupils are in the back group. Then the bus picks k pupils and moves them to x distance from the goal (binary/ternary search for best x). This group is now the "front group". Both groups walk continuously. The front group stops walking when they reach the goal. As long as there are pupils in the back group, the bus keeps moving pupils from the back group to the front group.
WA test #7: http://mirror.codeforces.com/contest/701/submission/19349308
I think the best distance x depends on the time remaining so the drop off point wont be the same for all the kids
Right. The front group is continuously walking, so the drop off point won't be the same for all pupils. In my previous comment "x" refers to the first drop off point.
I give up. Got as far as test #9. If anyone has an idea of where this rounding error comes, I would love to know: http://mirror.codeforces.com/contest/701/submission/19350779
edit: nevermind, solved it
Anyone please explain the 2nd test case of Problem D (Div-2). In which way the ans is 4.7142857143 . My calculated ans is 5.6666664444 :( .
5.666644 was coming only if you assumed bus will always reach towards the end of destination. Answer could be reduced if the bus leaves those k persons somewhere in between
ans is 33/7.0 and theres a O(1) formula
WTF with DIV2 A? Almost all people in my friend list have it wrong on system tests :O Edit: Seems it is fixed now! phew :D
Div2 A with N <= 100000 would've been fun.
Haha, is there anyone notice a small bug in the very first seconds of system testing? All of the accepted submissions are shown to be hacked!
Is there anything particular about Div1,B testcase 10 or is it just a large test case? I'm pretty sure my code was O(n) and I couldn't think of any exceptions.
19346020
I can't find any exceptions too... How about changing recursive function to loop? If It still gets TLE, then it will have an exception.(I'm just saying that recursive depth 200000 is dangerous)
I resubmitted without using std::pair and going threw only one dfs. I think the complexity was the same but the use of stl, etc. just increased the time constant a lot. Thanks for the help
19367422
I think problem setters should not add unnecessary character set like in Div2 C. Either keep a-z or A-Z , but why both? >( ..
Why not both?
Increases the implementation not the complexity of the problem?
Am I the only person who understood the sequence: "...reversal of the bus, take place immediately and this time can be neglected" that it takes 0 time to reverse (go backwards) no matter how long?
I know that it would mean a very strange bus, but I lost 25 minutes before noticing it :(
I interpreted it the same way. Although I probably wouldn't have been able to do it even if I had interpreted it correctly :P.
WTF!! I came to know now!!
So ... what does it mean in the end ?
how to solve div 2b?
Denoted by x the number of rows where no rook is placed, denoted by y the number of columns where no rook is placed. Answer = x*y.
In total (in the beginning) there are n * n cells.
These n2 cells can be viewed as n rows of cells and n columns of cells.
When we place a rook, it destroys completely 1 row and 1 column.
Let's keep 2 arrays which will tell us, whether the row/column was destroyed or not:
bool destroyedRows[100000];
bool destroyedCols[100000];
After you place the first rook at cell (r0, c0), we can destroy row and column like that:
destroyedRows[r0] = true;
destroyedCols[c0] = true;
The amount of alive rows decreases like that:
long long cellsLeft = n * n;
cellsLeft -= n;
// for destroyed rowcellsLeft -= n;
// for destroyed columncellsLeft += 1;
// because row and column intersect at point where rook standsIf you place the next rook at cell (r0, c1), you cannot destroy the row r0 the second time.
That is why you should first check whether it was already destroyed:
if (!destroyedRows[r0])
{
destroyedRows[r0] = true;
cellsLeft -= n;
}
The final idea is to accumulate the amount of destroyed rows and destroyed columns till the current rook.
Imagine that you have already processed i - 1 rooks. Now, the i'th rook wants to destroy the row ri and the column ci. If the row ri hasn't been already destroyed, you should destroy it now. But some cells on that row ri where previously destroyed by i - 1 rooks before the current rook. When they (previous rooks) were destroying there's columns, they also crossed the row ri! How many times did they cross the row ri? Well, they should have crossed it when they destroyed their's columns and we should just keep track of the number of columns destroyed (which is ≤ n - 1). We will use this number to add back the amount of destroyed columns:
...
destroyedRows[ri] = true;
cellsLeft -= n;
cellsLeft += destroyedColumnsCount;
// add back cells that were already destroyed beforeThat is the general idea. The rest is implementation detail... =)
I think the basic idea is quite easy.
Initially, number of rows(n) = number of columns(m) = n
Then there are only 4 cases:
1. if you have not visited the row and the column both
visit them and reduce them, n-- & m--
output:
cout<<(n*m-(n+m-1));2. if you have not visited the column visit and reduce the column size, m--
output:
cout<<(n*m-n);3. if you have not visited the row visit and reduce the size, n--
output:
cout<<(n*m-m);4. if you have visited both the row and column, there is nothong to do
output:
cout<<n*m;Here is my approach :)
For each query, you have to find number of cells on the board which do not have their row number and column number equal to any of the positions of the rooks placed uptill then. Actually, I did it by solving its complement, i.e. number of cells on the board which have their either their row number or column number or both not equal to any of the positions of the rooks placed and then subtracting this answer from the total number of cells.
Maintain two sets for rows and columns. Denote them by r and c. Total cells -> (n*n)
Cells which their row equal to any of the rooks and column not equal to that of any -> (n-size(c))*size(r)
Cells which their column equal to any of the rooks and row not equal to that of any -> (n-size(r))*size(c)
Cells which their row not equal to any of the rooks and column not equal to that of any -> (n-size(r))*(n-size(c))
Therefore Answer = (n*n) — (n-size(c))*size(r) — (n-size(r))*size(c) — (n-size(r))*(n-size(c))
On further simplification, this turns out to be,
Answer = n*n — size(r)*n — size(c)*n + size(r)*size(c)
Answer = (n-size(r)) * (n-size(c))
Here is my solution: Code
can rating fall over 100?
I think mine will...
T.T...
I started trying problem A after I read it I couldn't understand the second sample, so I decided to move to B, after I solved it I went to read C, I figured out the solution quickly:
apply max flow considering all edges capacity equal to 1, if it's more than 2 then output -1 otherwise try out to remove each edge which became saturated and for each of them find bridges and pick best bridge on the path between s and t of course there's some corner cases to handle.
wow very easy idea I decided to code it although I have bridges and max flow codes beforehand it took me a full hour to code it, after passing all samples I submitted it and got WA after fixing some bugs I still got WA the contest ended but I didn't solving anything except B, if I knew coding C is overkill I would have returned to solve A instead :(
I had the same solution to C as yours, but little bit simpler — you don't have to compute maxflow. If for every "deleted" edge, there is no path from s to t consisting only bridges, then we print - 1.
I didn't code it, but it's O(m2). Isn't it too slow?
I had a solution that didn't need flows and works in
.
Get a path from s to t. If none exists, print 0.
This path will consist of at most n-1 edges. Now for each edge in this path, remove it from the graph and construct the bridge tree of the remaining graph. If s and t are in the same block int the bridge tree then removing this edge is of no use to us. Bridge Tree can be constructed in
If s and t are in different blocks find the minimum weight edge on the path from block of s to block of t in the bridgeTree. Now you have two edges, compare their weigths with the current minimum and update accordingly.
Add the removed edge back to the graph and repeat.
Took too much time debuggin but oh well :/ 19347868
Nice!
Глюки
Системное тестирование100%Дорешиваниеdiv 2 D anyone ?
thanks Physics for div2 D ))
let maximum people bus can carry be n and total people is N. So bus can make ceil(N/n) trips. You have to drop people such that last set of people carried by bus reach final point at the same time when the rest of people reach.
I thought of this logic but wasn't able to implement. Am I thinking right?
Yes, right idea. You can get it if you go to the frame of reference, where students are stationary. We can solve it by solving equation system.
Overflow in B anyone?
Overflow case is already present in pretest 3
I have a case of what I think is an overflow at testcase #31. Its a negative number, and a huge test case, so its the first thing that came to mind.
edit : Its a case of unsigned integer overflow.
Was I the only one who thought "reversal" in Div2 D means "traveling" back to the students after the drop-off? Bad me. :(
Why the system testing is stuck at 100% ?? We have been seeing this for the last few contests !! Please fix this issue! :(
Getting WA in test case 31 in Div2 B. Can anybody give any insight why? Thanks! :)
Solution
row.size() and col.size() are returned as unsigned ints, and in the worst case multiplying them can make them overflow. Type cast them into (long long)! :)
i too had similar solution....failed because size function returns unsigned int :(
Откройте, пожалуйста, код сабмишенов с финала ВК
petr now
Rank 3 and -116 O.o .. WOT
because he was in rank 1
When will be editoral?
Any hints on how to solve div 2 C ??
I used cumulative sum + binary search on window length approach. But it can be solved using two pointers technique. Hope this will help.
You can solve it by method of two pointers.
Can you explain How?
It can be solved using 2-pointers technique.
We keep 2 pointers :
leftandright, which indicate that currently we're working with the houses(string) with indices[left, right].Also, we maintain an array to keep a count of all the pokemon's(letters) that we've caught so far, and a variable
min, to keep the minimum substring length which includes AT LEAST 1 pokemon of all types.Then, inside a loop for
leftwhich goes from 0 to n — 1 (n = length of the string), we run another loop and incrementrightand add the pokemon at indexright, until we don't have AT LEAST 1 pokemon of all types orrightbecomes equal to n.At this point, we update our
minvariable if the current substring[left, right]includes all pokemons and it's length is less thanmin.Then, we decrease count of the pokemon at index
leftand then incrementleft.Again, we check and update our
minif needed.We do this inside a loop for
leftas stated above.Since
rightgoes from 0 to n — 1 once and alsoleft, the total complexity is O(n).I dont understand how the complexity of your algo is O(n). If i am not wrong it is a nested loop. right ??
You're wrong, because both pointers only move forward, which means that the complexity is O(n).
UPD: We don't move right pointer everytime from left, we keep its' position saved.
No, right is initialised only once, outside the first loop, and inside it is only incremented. We never reinitialise it or decrement it. So, right goes from 0 to n — 1. And the other loop is for left, which also goes from 0 to n — 1. Hence, O(n).
You can refer to my code : 19349919
P.S. : I actually initialised right to -1.
I hope it's clear now. :)
I tried something like that , but it's O(n^2)?...here is my code that took TLE;
Actually you are setting your right variable to n — 1 multiple times and then are iterating it down to i for 0 <= i < n
so, for i = 0, you have n — 1 loops, for i = 1,you have n — 2 loops and so on..
So your worst case time complexity is O(n^2).
You need to increment both your left and right variables from 0 to n just once. if you still don't get exactly how it's working let me know, I'll explain :)
Move across the string recording the last position of each character that occurs in the string. Once you have seen each letter at least once, each time you move take the difference of the biggest last position and the smallest last position. The smallest such difference is your answer. This is worst case O(52*n).
Binary Search + Segment Tree Problem-C
I don't like 2-pointers
that's just wrong man...
i know
two pointers much simpler than seg tree+binary search.
ofcourse , but I was bored a little bit and I had the seg-tree code ready
just the final touch
upset..I got rank 10 too but not on the winners' board..Orz
rest in pepperoni petr :'(
Hi, can anyone tell what may be the cause of this error in the Div.2 task A?
19333396
sum/n is not necessarily an integer but sum/(n/2) is.
In recent rounds I have seen a glitch in the standings. When the system testing starts all queued submissions turned to failed. May be it's not a big deal but I wonder why this is happening?
NB: The round was great. I'm looking forward to seeing so many rounds like this one. Thanks for the round :)
can anyone explain the approach to Div2C?
Here
Go through the sequence and push symbols into the queue one by one. When it contains all types of symbols, this means you found a subsequence that satisfies problem statement. Now you can crop it from the beginning to make it as short as possible — just delete front symbol from the queue while it still contains all types of symbols. When done, check if this snippet is the shortest that you found so far. To continue searching, just remove first symbol from the queue (it should miss one type of symbol now) and continue pushing them from the given sequence. All the procedures can be performed quickly using STL structures like queue and set.
I will explain my solution (binary search + sliding window) at first, its obvious the answer is the size of some contiguous subsequence that have all types of pokemons.
if you try every range with size 1, then every range with size 2, .. until have range with all types of pokemons you can get the answer. but this is to slow which takes O(n^2).
so you should do binary search on the size of the range, which takes O(n*log(n)). http://mirror.codeforces.com/contest/701/submission/19338973
approach for div2E ?
Find a node such that all subtrees have <= K universities. Answer is sum of all depths. Complexity : O(N).
Nice explanation, thanks!
It took me a couple of minutes to figure your comment out, but this is beautiful.
I tried finding a node such that it has exactly K on one side. Can you figure out my solution fails?
Your node will also have this property. 19342855
I think you meant K and not K / 2 ? Also, there may not be a node such that exactly K nodes lie in one subtree.
Yes, but there is always a node which has a subset of sub-trees having exactly K nodes and exactly K in other subset when the tree is rooted at this Node.
In un-rooted definition , if we remove this node all the components have <=K nodes.
Is anything wrong in this hypothesis?
What if the subtrees have the following count of nodes : 2,2,k-3,k-1 ?
Thanks.
So close yet so far from the solution. :)
Could you more explain the algorithm?
can you prove that such node is optimal choice?
Yes. When we choose such a node, we know that each subtree has <= K universities. For a university in any one subtree, we have two choices : To pair it with a university in a different subtree or to pair it with a university in the same subtree. You can see that pairing universities among different subtrees maximises the answer, which is what is required!
how will you prove that it always give maximum sum
Suppose there is a edge u->v and there are count[v] vertices that are in subtree of v and also in the 2*k list, then the edge u-v would be used (added) in the answer min(count[v], 2*k — count[v]) times only since we can always select min(count[v], 2*k — count[v]) pairs such that one is from each side of the edge
Link to submission
Когда будет разбор?
Div2D: What is the significance of "In order to avoid seasick, each of the pupils want to get into the bus no more than once"? I can't think of a case where shuttling a student more than once would be useful.
For example, let there be three students, but let the bus carry only two simultaneously. Intuitively, a good solution would carry each of the subsets {1, 2}, {1, 3} and {2, 3} on the bus for the same duration. However, this is impossible given the constraint.
Because the bus takes time to drive back the constraint doesn't matter. Makes the problem easier though, otherwise you'd have to figure out yourself that it doesn't matter...
It does matter. I think the point in Gassa's example is that without the constraint we never have to drive a half-empty bus. So the bus is always driving at 100% capacity.
It's impossible to drive the bus at 100% capacity if there's 2 seats and 3 pupils. The bus will always have to drive back to get the last pupil and drive at 50% capacity.
Right, when the bus is driving BACKWARDS it's always empty.
When the bus is driving FORWARDS we have a capacity problem. Without the constraint we could always drive forwards with 100% capacity. With the constraint we might sometimes have to drive a half-empty bus. In Gassa's example, we might first drive {1, 2} and then drive {3}. Even though we have room for 1 more passenger, we can't take anyone, because 1 and 2 have already been to the bus and we have no-one else we could take.
'The constraint' meaning 'each of the pupils want to get into the bus no more than once', even without the constraint the bus cannot always drive forwards with 100% capacity.
There's no better solution without this constraint, just like you stated in your original comment.
Read Gassa's example again, it's very short and it illustrates the problem perfectly. It has the bus always driving forwards with 100% capacity. Add the constraint and the capacity drops.
After reading Gassa's example again (and again) I still don't understand. Could you give me an example of how the bus will always drive forwards with 3 pupils and 2 seats?
I wasn't able to construct an example. I may have been wrong about the capacity thing.
Let's say we shuttle {A,B} for some distance. Now we have to shuttle {C} for the same distance on its own. We can't shuttle A with C at this point, because A is ahead of C.
So now I'm back to square 1, wondering what's the significance of the constraint in the first place.
This looks impossible even without the constraint. How does the carrying of each of the subsets {1, 2}, {1, 3} and {2, 3} looks like?
Do they need to travel backwards with the bus? Does it add efficiency?
I wasn't able to construct a speedup example so far.
My point is a bit different: when the constraint is there, it is irrelevant whether or not it's possible to get faster without it. So this investigation happens after the contest, not when solving the problem. Which is a good thing, especially if there is indeed no faster solution without the constraint.
Who else has noticed that tourist has become top on the rank table even without participating!?
Ставь лайк если бесит, когда авторы не выкладывают разбор после раунда и приходится читать чужие говно-коды.
Хотя иногда находятся забавные комментарии:
туши быстрей
Куда тушить??? Ставь лайк, если бесят подобные сложно-бесполезные комменты на цф
Can anyone please help ?
http://mirror.codeforces.com/blog/entry/46213
can someone explain me the process to solve div1 D? i was thinking mo's algorithm but can't figure out the calculations. please help :(
By mo's algorithm, you can know the occurance of each number in the query interval [L, R], and also you can know which kinds of occurance has appeared. Since
, the number of different occurance is no more than 
. So you can use pair < occ, cnt > instead of only occ to represent a node in priority queue. And every time you pick up a node from the top, you can simply do this : occ *= 2 and cnt /= 2, if cnt is odd then you should split it. The whole algorithm is about 
.
thanks :D nice explanation :)
Did someone actually fit this exact complexity in TL though? This last part (with priority_queue or w/e else) seems a bit too slow for me, I spent quite some time trying to make it work (I've heard the
solution, but I'm really curious if it can be passed in 
)
The priority queue can be replaced by two queues. And this whill be
.
How do you bound number of Huffman's vertices? Is it surely
? Won't it be multiplied by some small nonconstant factor?
I made it work. The only part which is beyond n sqrt(n) is the sorting — I perform O(n) sorts on an array of length O(sqrt(n)), which works really fast. Other than that everything else is O(n sqrt(n)).
Oh, and using a custom list implementation instead of std::list resulted in a 20x speedup :D
Link: http://mirror.codeforces.com/contest/700/submission/19373681
can someone help me out im getting WA in #17 test case in DIV2-C 19356617
It can be solved using binary search. map all the characters and store an array dp. where dp[i][j] represents the number of occurrences of the ith character from index 1 to j. Then run a loop from 1 to n and for each i find out the lowest index r, greater than i where each character occur at least once. the complexity is O(n log n), so it easily passes. there might be two pointer solution but, binary search seemed easier and safer to me.
Line 28: r<=n is causing problem.
You have to stop the loop when r hits n, remember to care of the cases where string[n-1] is part of the optimal solution.
When will we read the anlysis of the problems?
My approach on Div2E/Div1B, not necessarily correct, maybe I just slither through the system test cases.
Step 1:
Set a node which is only connected by an edge as the root of the tree.
Step 2:
DFS from this node, for each subtree count it's amount of university inside the tree. Select the minimum among all the nodes which has at least k university. (This is probably the node which every pair in the optimal solution will past... I say PROBABLY because I don't have a strong prove for this, but I can't think of a counter case.)
Step 3:
DFS from this node, the answer is the sum of this tree.
My submission: http://mirror.codeforces.com/contest/700/submission/19363132
A kinda similar question I would recommend to try out: http://mirror.codeforces.com/problemset/problem/685/B
Any tips on Div2F/Div1C? Cycles in the graph seems to be a huge obstacle in the problem.
For simplicity assume that there is no multi-edge nor self-loop (they can be handled in the beginning).
First idea: brute force — remove every edge and look for bridges between s and t and find the best option. Iit can be done with standard dfs with low fuction, but -supposing you start if from s — you also need to remember if there is t in the subtree you've just visited. Complexity: O(m^2)
Better idea: take a path P between s and t (if it doesn't exist — output 0 0). Observation: At least one edge from P must be removed. As the path contains at most n edges, we get O(n*m) which easily fits the limits.
Hope you don't mind that I'm asking, but how do you get O(n*m)? I'm only able to get O(n*(n+m)). After I remove and edge from the path I have to redo the DFS and this leads to O(n*(n+m)).
Yeah, but n<=m so it is fine to write O(m) instead of O(n+m). Of course I also have the same complexity as you.
dude , where is the editorial ?
How long we wait for the editorials??
Подскажи кто нибудь,как в задаче D див2 правильно использовать бинарный поиск. Как и по чем его организовать? Если можно обьясните на русском языке и подробнее. Спасибо.
Будем писать бинарный поиск по ответу, то есть зафиксируем "минимальное время, по истечении которого все школьники доберутся до места проведения экскурсии". Дальше рассказывать?
Конечно рассказывать!
Я вывел такие формулы. Допустим возьмем какое-то произвольное расстояние k. Тогда автобус его проедет, за время t = k/v2. Это же время пешеходы тоже двигались. Значит за это же время они прошли путь (k/v2)*v1. Остаток пути для оставшихся пешеходов будет равен k — (k/v2*v1) . Дальше никак не пойму что делать? И как учитывать вместимость автобуса?
Вместимость автобуса можно учесть разбив всех людей на округление_вверх(n / k) групп. Далее будем симулировать процесс прохода каждой группы расстояния l. Основная идея в том что мы будем определять минимальное расстояние которое нужно проехать данной группе на автобусе, что бы успеть за ранее закрепленное время.
Will Editorial be published this time? Waiting...............
Editorial will be published soon, I guess. Another question is "when is the next round?"
why does pairing node i and i + k after sorting according to dfs start time work in div1B?
Hints for E and F div 2 ?
E and F div 2 = 7. That's all I can tell about that :(
However, you can check out these hints: E and F.
Hint for F: Let find any path P from S to T: O(M + N). The length of P will be less or equal to number of vertices. Try to remove any edge in P: O(N). For each removed edge in P find all bridges in resulting graph: O(N + M). Check if removing the bridge will disconnect S from T (it is possible at O(1)). Don't forget to check special cases: 1) There is no path from S to T. 2) Removing some edge in P disconnectes S from T. So this solution will work at O(N * (N + M)).
How did you check if deleting an edge would disconnect S from T? I did this while building dfs tree: if recursive DFS on edge has found T and that edge is a bridge, then account it.
I did it exactly the same as you did
D solution:
Note these observations:
Code:
In the second test. Why can't I take each pupil on the bus per 3 meters?
let (p1, p2, p3) positions of the pupils i
t = 1.5 — (3, 1.5, 1.5) — p1 in the bus
t = 3 — (4.5, 4.5, 3) — p2 in the bus
t = 4.5 — (6, 6, 6) — p3 in the bus
total 4.5
You are ignoring Bus return time. Bus can not teleport from one kid position to another instantly. You need to add to your calculations meeting time from the bus going left and the kids going right.
" as well as the — reversal of the bus, take place immediately "
The reversal is the time to the bus to flip, not the time to the bus to return to search for more pupils.
Your example of V2 time = 1.5s (3 meters) would be
t = 1.5 — (1.5,1.5,3)
te = (3-1.5)/(2+1) = 0.5
t = 2 — (2 , 2 , 3.5)
t = 3.5 — (3.5 , 5 , 5)
te = (5-3.5)/(2+1) = 0.5
t = 4 — (4 , 5.5 , 5.5)
t = 5.5 — (7 , 7 , 7)
You end in position 7, so you need to reduce V2 time.
You are right, I misunderstood the problem statement. Thanks a lot.
Почему до сих пор нету разбора???
Any ideas on how to solve Div2F/Div1C?
Find any path from S to T. Try to remove each edge of the path, In the resulting graph try to remove each bridge. This solution complexity is O(N * (N + M))
Публика требует разбора!
составленный с использованием задач VK Cup 2016 Final Round.
Какие из задач этого и предыдущего раунда были на VK Cup Final Round?
http://mirror.codeforces.com/blog/entry/46254?#comment-307044
waiting for the editorial and next context ...
Ну где же все таки разбор? Каждый в ожидании ждет разбора.
Вот он!
Why does python submissions for div2 problem E gets runtime error in test 11? n is 200000 and my code: http://mirror.codeforces.com/contest/701/submission/19425329
I know nothing about Python, but it seems that you are not using 64-bit integer to store the results: Test case 11 is the first case where you need long long to store the answer. If Python has RE when there is overflow then this is probably your answer.
There is no overflow in Python. Python's integers can store any number.
The RTE is because of recursion depth limit reach in your case. This happens mostly with me I used to switch to c++ with same logic!
Thanks! How do you overcome the problem or how to increase the depth limit?
11