Всем привет!
Рад сообщить, что скоро состоится Codeforces Round #303 для участников Div.2, автором которого являюсь я. Как всегда, участники Div.1 могут поучаствовать вне конкурса.
Это мой первый раунд, и я надеюсь, что он будет для Вас интересным.
Раунд не состоялся бы без помощи команды Codeforces! Спасибо Zlobober за помощь в подготовке раунда и Delinur за перевод. Отдельное спасибо всем, кто вложил силы в создание и поддержку систем Codeforces и Polygon.
Распределение баллов будет объявлено позже.
Удачи и вдохновения!
UPD Распределение баллов по задачам — 500-1000-1750-1750-2500.
UPD Поздравляем победителей в официальном зачёте:
И в неофициальном зачёте:
UPD Ссылка на разбор.
Hope the English version won't be from Google translator!!
Come on people,why downvote? I made some prediction here and as you can see the 1st problem really had some sign of google translation: "Little Susie, thanks to her older brother, likes to play with cars." Didn't my prediction work?
People just like to downvote comparatively low rated programmers comments whatever they write.Racist everywhere.
World Final for div 2 :)
Maybe not so many genius unrated contestants, because most of them are in relaxation mode for tomorrow Div. 1 World Final ;)
Many strong coders won't take part due to world finals . All of the strong coders are in div1 . That's why there are many div1 contests consecutively lined up after the WF ends.
When tourist said his team did not feel any pressure for the world finals i thought OK.. But then querty787788 went ahead and registered for this contest as if he has nothing to do tomorrow. Let's see if he actually participates.
I wonder why all the contest at the same time of the day ! It's not suitable and not reasonable at all .. can anyone explain this ?
Score distribution will be announce later :) When??? JUST 10 min. befor contest and no announce :/
now 1 min :D
Well, the author thought that good luck and inspiration are enough :)
Just 5100 participants?? too few! :D
Do you believe in EDITORIALS??
stfu
who was translating statements??? i hate him with passion.
Telling what exactly you think is wrong in a translation is a more constructive way rather than just saying you hate someone.
I thought the translations were totally fine with a few minor mistakes that didn't really matter in understanding the problems.
ye sorry for nonconstructive criticism, but some of the problem's statements weren't translated fully, compared to russian statement (example: E's english statement didn't contain that graph is connecte initially, while russian statement did)
Мне кажется или контест выдался легким :)
The worst Contest EVER!
A,B,C,D,E were all obvious! -_-
E was so obvious that I thought my logic has got to be wrong.
Guy registered 3 hours ago judges the problemset. You even weren't brave enough to participate from your real account, lol =)
In problem E, using std::set(to implement Prims) gives TLE ?
How do you use Prims?
Dijkstra with set doesnt give TL on pretests
Sorry, not Prims its Dijkstra. I keep getting TLE on 6th pretest. http://codeforces.me/contest/545/submission/11165455
I can't open it until system tests will pass(.
My Dijkstras gave MLE on test 6. What changes are expected ? http://codeforces.me/contest/545/submission/11167671
What I did (after contest) was just to add a check when there is a tie in distance to reach a specific node X. If the distance of the last edge checked is smaller than the last edge of the previous path to X from the source, then update the path to X to the new one.
Of course you also need to store all the time the edge that took you to each node after visiting it so you can be able to replace it afterwards.
That's exactly what I implemented
Problem C was really hard for third problem(C).
In E, how to prove that shortest path tree we get using dijkstra is indeed the shortest path tree with least weight ?
This solution may be hacked by following test case:
3 3 1 2 8 1 3 6 2 3 2 1
Simply doing djikstra — it will output 14; correct answer is 8.
Even using dijkstra, we get 8. Ofcourse, the modification if ( dist[X] <= dist[current]+weight of edge )then parent[X]=current is to be made.
Is that always true anyway? At least my implementation of Dijkstra does not have that property, and I spent forever trying to figure out how to modify it to get that property.
so, what's the correct solution for E?
Use Dijkstra and modify (d[v] == d[u] + w);
it isnt because i used dijkstra and i got WA. i think you should modify dijkstra so when (d[v] == d[u] + w) happens, you change d[v] to d[u]+w if the trees wieght decreases.
Let d[x] denote the minimum distance from u to x. Let's construct a tree in G using this approach: 1. Let u be the root. 2. For all other vertex p, we can choose as a parent any node q such that d[p]=d[q]+w[q][p]. The most natural idea is to select the q with minimum w[q][p].
Since for each vertex we are selecting the edge with minimum weight, the total sum of weights will be minimum. It just remains to prove that for two different vertices, we can't choose the same edge as a link to the parent node (this is a consequence of positive weights)
Question similar to E was asked in ICPC regionals this year. Here is the link.
Actually solution algo was directly google-able too :P one can get ready-made algo for E in 2 clicks :/
Problem C was really hard for third problem(C).
It's obvious I think :) But D is easier than C.
i think C is the obvious one cuz its a simple DP.
i think you can solve it by using greedy approach also.
i would love to hear how.
Starting from left, If you can fell a tree left, make it go left else if you can fell it on right make it go right.
Why this works ? If you are falling left then it is easy to see that you are not spoiling the chance of the next tree. The option for next tree is open.
If you are falling the tree to right, may be there is a possibility that the right tree can't fall left. Only thing is worst case scenario you have to select only one of this tree.
I did the same thing except in a way which is unnecessarily more complex. Why do you think it gets WA? My Submission
It was greedy. All problems were greedy :)
D easier than A
Hard ?? why ?? it was a simple implementation .
During coding phase,Earthquake at NEPAL-INDIA border ruined everything!! :( :(
I am From Nepal (Original) . Please Don't Make a Joke about Earthquake
I am from north India. There was no such earthquake.
unexpectedly easy problem set. appears as if we are participating in a DIV 3 contest
if the difficulty level was "standard" ANY of problems A,B,C,D could be Div2. A or at most Div2. B.Because no specific algos were needed,and problem C had some tricky coroners and wasn't actually difficult
Thanks for nice contest for Div.2. There were interesting problems. Maybe pretests could be a bit weaker.
Why am I still unrated after this contest? (It is my first btw)
You will get rating after system tests and rating recalculation
What was the 7th pretest for C :(..Kept getting WA
It was DP. You should initialize 0th tree at -infinity(-10^14) and n+1th tree at infinity.
Well, that's obvious. But what about other trees, could you please explain to me? I couldn't code a working solution.
Either a tree doesn't fall at all, or falls on left or right. So, 3 arrays to hold these results.
Actually when the tree falls on the left or doesn't fall generates the same sub-problem!
So you can use only 2 arrays :)
I did C in a greedy manner: keep 3 arrays(one for trees position, one for trees height and one for where will the rightmost part of the i-th tree be). I initialised the rightmost part of the first element as the position of the first tree and the (n+1)-th with INFINITY. Then for each tree starting from the second to the last i check first if i can make it fell to left(using the rightmost array), if i cant i check if it can fell to right and it is still impossible i move to the next tree without increasing the amount of trees that can be cut.
PS sorry for bad formating.
Here is my source code: CODE
Actually it could be solved in a greedy way without any extra space.
The first tree is toppled to the left and the last to the right.
Keep a variable "lastUsed" initially equal to the position of the first tree.
For trees [2, n-1] try to topple it to the left. If not possible try toppling it to the right and update to x[i] + h[i]. If it couldn't be toppled or it was toppled to the left "lastUsed" gets updated to x[i].
My code
Hmmmm.... either I drunk too little coffee or I have to participate in Div3 contests....
It was a GREEDY contest!! :D
A car is good if it turned over in no collision --> RIP English
What's the problem?
A car is good if it was not turned over in any collision
This was easier than Codechef Lunch time contest, which is supposedly designed for school students.
Have you actually participated in those, because I certainly feel that overall level of lunchtimes is at par with Div2 contests(old ones when I used to participate :)) and most of the times even difficult than that.
Yes, I have and I believe that last two problems of Div2 contests are harder than last 2 problems of lunchtime. The level of first three problems are more or less the same. But today first 4 problems were very easy and 5th was direct implementation.
I don't think you can judge the difficulty of problems which you can't solve in contest time. Just because the solution uses a familiar concept or uses less code doesn't necessarily mean it's simple. Have you solved Div2 E or the last problem from Lunch Time contest?
IOI is also for school students. Do you think it's easy?
Codeforces favors C++ over Java too much. I cant make E accepted with Java, got TE all of the time. The algorithm I implemented is exactly same with accepted C++ version.
There have been many Java AC too ,so probably your implementation could have been slightly slow ?
Could you please give me a link to Java source of whom got AC? Many thanks!
http://codeforces.me/contest/545/submission/11164079
Also you can search by language as parameter too ,if you want to see more solutions :)
I think the status filter is good enough for what you want:
And here are some of the source who got AC with Java: http://codeforces.me/contest/545/submission/11161969 (fastest in Java 7) http://codeforces.me/contest/545/submission/11163503 (fastest in Java 8)
Thank a lot! It's very useful.
After looking deep into the solution, the trick for Java developers is re-implementing ConsoleIO and PriorityQueue (Heap).
It is still a bit favor for C++ developers, since the built-in STL is pretty good already.
Only 3 "Failed System Test" solutions in my room. wow... XD
Can anybody explain this?
Task D. Sort and calculate got AC. But in query 1 1 1 1 1 1 1 5 two satisfied. But in query 1 1 5 1 1 1 1 1 1 three satisfied. Where am I wrong?
Because we sort the array first, so both of them will produce
1 1 1 1 1 1 1 5. The answer should be three: serve the first two, and serve the last person.Hope it helps!
what an awful contest ?! Everything depends on problem E!
What did solve task C? I am build dinamic and found states with binary finder... Why it was not correct: http://pastebin.com/PHVYYqWC ?
o_O what a grammar ?!
The pretest was so strong i got two times WA in problem C&D and at last AC.I scanned the whole c++ coders of my room and there was no sign of mistakes in their codes :D
My room 1016, NO successful hacking, NO system test fail. :|
The same situation is in my room, 1014.
rasoolll and Behnam.B cheated look at their submissions : 11152882 and 11153982 they are also from same university (shame on ferdowsi university of mashhad)
Code doesn't look 100% similar. Their outputs on the third test differ also.
This is Common Problem With Short code. Two code can Have similar Idea ( Even These Code seems to be same but not Exactly Same). And another thing is, Generally Student from same University have closer Idea about many problems.
I am new to this site, and this was my first ever coding contest. I managed to solve 3 problems getting a rank of 1802. However, I cannot see any rating being alloted to me. Can anyone explain the reason for this, and how I can earn a rating.
System testing wasn't finished. It is finished now. Your rating's 1448, gratz on your first contest!
Thanks, I also wanted to know that few people were awarded more marks for certain questions, and I lost out on few points. For example Problem #1 was of 500 points, where as I was awarded only 408 points, even though I didn't fail any submission. I read somewhere about hacking other people's code and some room concept. Can someone explain me my roles about hacking and what am I supposed to do in a room.
you get less points if you take more time to solve. If you are sure of your solution you can press the lock button on the dashboard. Then you can view others' solutions to that problem by clicking the score in the room. If you find a mistake in their code, give a test case which satisfies constraints and gives sub optimal answer wwith their code. You get +50 if their code gives wrong answer and -50 otherwise. Also, if you click the lock, you cant resubmit for that problem.
It is actually +100 for correct hack.
Finally into DIV 1 (purple) after almost a year on CF :D
Congrats
Thanks.
Answers to both of my wrong submissions (WA on pretest one in Problem A and Runtime Error in Problem D) is showing correctly on my computer. anything i am missing here?
When a[i][j] == 3 || a[i][j] == 1 you should skip entry. i cant understand your code seems like you do the same for a[i][j] == 2 and it give WA.
In my opinion, problemset was like A-B-B-B-D, but it's just my opinion.
A A B A D in implementation imho
Can anyone tell me why this solution gave WA for test 11 question C? I used DP where prev=0 means previous tree wasn't cut, prev=1 means previous tree was cut to left, prev =2 means previous tree was cut to rightLINK
its simple because you assume tree number 2 will always be cut in code: int ans=1+func(2,1); ans=max(ans,1+func(2,2));
No, I am assuming that tree 1 will always be cut to the left (this is optimal, I know). ans=max(ans,1+func(2,2)) means tree 1 is cut to right. func(i,prev) means I am checking for tree i and I have solved for i-1 trees and (i-1)th tree was cut to prev.
I tried to solve the problem E using Dijkstra modified. It is my aproach:
I get WA in the 8th case. The test case is very large and I cant debug it...
Here is my code.
I read several comments and found some similar ideas. can anyone help me? (sorry for my poor english) thanks in advance
Try to change distance (vector dist and priority_queue) to long long :)
Thanks a lot!!! long long vs int
I try to don't forget it...
I am getting WA in http://codeforces.me/contest/545/problem/D
My solution http://codeforces.me/contest/545/submission/11166839
why?? please help thnx in advance :)
";" after if — delete it
If statement has empty body
Too few successful hacks for A, B, C, D. Problems were so clear and obvious. Also, since I passed too many pretests, I was sure about getting accepted for first four problems!
:D
A very nice contest with both easy and medium level questions.
Can anyone plz explain why problem E is not minimum spanning tree? I thought it as MST but I know second test case is not following my observation. So plz elaborate why my assumption is wrong.
The MST does not satisfy the condition: "shortest-path tree from vertex u" ... " the lengths of the shortest paths from u to any vertex to G and to G1 are the same".
Make some test cases yourself and you'll realize it. (Sorry for my bad english)
You have to find a tree such that each vertex has least-possible distance from an specified vertex of the graph, not just being connected to the tree with least-cost.
Thanks
Since this round was the author's first contest as a writer, I think there should have been a reviewer working with him. The problems were okay, but the complexities didn't match the score. Even though most of the problems were easy, I spent relatively too much time trying to solve them because the translation was not clear enough.
Impressive result from latisel! http://codeforces.me/contest/545/...
My E solution failed because of
long long. I legit feel sad now.11160086: initial submission
11171670: correct submission
this round very easy ! =D
Вам дан связный взвешенный неориентированный граф G и вершина u. Необходимо найти дерево кратчайших путей заданого графа из вершины u, суммарный вес рёбер которого минимален.
Это было архисложно, но я решил Div2E (Div1C), дайте мне красного :)))
has anyone did problem E with MST(kruskal's or prim's )?if yes then please explain the approach?
This was my first CF round so I can't compare it with others, but I'd like to give the author some feedback: I enjoyed the round :), although it was an one hour contest for me (A, B, C and D). I couldn't finish E as well, although it was a nice problem, also the only difficult one. I think that C deserved more points than D? or D deserved less points than C?
Hi every one in problem C can explain in test #7 why answer is 5? which trees can cut down? I think tree x=1 to right, tree x=41 to left, tree x=55 to left, tree x=59 to right, and last tree with x=105 to right why my answer is wrong?
Your answer is almost right , but always cut the first tree to the left not to the right :)
I forgot tree x=68 so: tree x=1 to left, tree x=41 to left, tree x=55 to left, tree x=59 to right, tree x=68 to left, and last tree with x=105 to right we can cut down 6 tree and correct answer is 5! what's wrong?
If you cut down tree x=59 to right, it takes segment [59;66]. If you cut down tree x=68 to left, it takes sement [61;68]. These segments are intersect, so we can't do this.