Всем привет!
В среду 9 декабря в 19 MSK будет CF Round #335 (div 1 + div 2) по задачам, сделанным мной и dalex. Идёмте его играть!
Благодарим GlebsHP за помощь в подготовке задач, Delinur за перевод и MikeMirzayanov за сам Codeforces.
Систему подсчета баллов и их распределение вы узнаете вместе с началом раунда. Все равно эта информация не несет особого смысла, пока контест не начался.
Всем полных решений и успешных взломов!
UPD. Поздравляем победителей Div. 2:
И Div. 1:
Разбор: blog/entry/22019.
сыграйте катку без меня.
ладно, ладно, сыграю с вами :) только не минусите
Aaaaaaand the excitement starts again !!! :))
UPD.
This's my feeling after the down voting .. and I must admit it really hurts
I think that now you're like this little boy.
After the down voting ? .. yes. :)
Something that I want to mention here that I don't like it when I've a negative impact on the community that I'm part of. But sometimes you can't avoid it specially when you're a beginner like me .. and finally no one learns for no price.. and down voting is the price here ! :D
It's really hard to get downvotes on CF :D
Круто! Начинается на 30мин. раньше.
Да, Круто! Авторам респект !
Cows give a lot of fame. Why? Because:
3 1/2 hours before the previous contest (the one about cows): ~75 comments to the announcement (I really counted them).
3 1/2 hours before this contest: 7 comments to the announcement.
I think one must comment for his/her help or other discussion. Not to get the upvote or downvote
wait till the contest ends...
Thanks to the contest notification message system too... :)
Is there a way to know if you have already voted on a blog?
Press to upvote/downvote you will recieve notification if you had already voted
hope the questions are as short as blog is
"Prove P=NP."
P=NP
0=NP-P
0=P(N-1)
either P=0 or N=1
sorry for silly joke guys :P
What if P is positive but N is negative? I think your solution passes only few test cases!
"Wish you accepted solutions and successful hacks!" sarcastic :P
Good Luck Everyone, the time is too late for eastern countries
Registered before the contest and appeared as registered right before it began. Once it started, I saw I can't submit any solution and went back to see , to my surprise, that I no longer appear as a participant. I guess I'm reporting a bug :-?
The author had actually protected you from that difficult tasks. You should be happy, though!
Anyone finding the statement for Div2-B hard ? :( :(
Not able to understand problem div2 B.
Please explain output at least.
I asume, that we must go step-by-step by commands to the robot. I think, that if you already was in this cell, you need to cout 0, else — 1. Last number is x*y-(number of couted 1), but i also have understood this problem only few minutes ago and this is my solution that come to my mind suddenly.
Problem B is basically asking how many slots were visited before or not, and at the end how many were not visited yet.
The key lies in the first paragraph when it says X*Y experiments are being made; one for each slot.
You have a robot. This robot starts at position (x0, y0). There are various scenarios (one for every cell in the field). In one scenario, there is exactly one mine in a unique cell. So if the field is of size 3 * 4.
And so on are the scenarios, where "X" means that there is a mine right there, and "." means a empty cell.
Your robot is given a sequence of "moves", and you have to tell, for every "move", in how many scenarios your robot will explode after that move.
In the first testcase:
Is the map without any mine.
How many scenarios are in which the robot explodes doing 0 moves?Just one, the one in which the mine is at the position of the robot.
How many scenarios are in which the robot explodes doing 1 moves?The first move is to go up. So the only scenario in which the robot will explode after going up, is the scenario in which there is a mine in the cell (1, 2) (1-indexed).
How many scenarios are in which the robot explodes doing 2 moves?The second move is to go up again, but the robot can't go up, so it stays at position (1, 2) and there is no scenario in which it will be blown up, because if there were a mine at position (1, 2) the robot would have explode in the last move, when it first got to that field.
And you have to keep this process, for the last move, the robot will explode anyways, so you have to count the number of scenarios in which there is no mine in the path to the final field. Sorry for the english, I hope this can help.
I know what is means, but can you implement it now...
I came here for exactly this. I reach 90 percent of it. And the rest just doens't make sense
Too hard for me :(
Wtf. Get TLE with an optimized O(nlogn) solution in Div 1 B if I use GNU C++, but Pretests Passed if I use MS C++. Why??
Ignore my stupid comment
sorting
Ignore my stupid comment.
Are you talking about div1 B/div2 D?
Reasons I am cyan: 1.I don't even read what people write properly >_< 2. ....
Div 2 C :/
Hmm,
2 3 4 1? If I get your description correctly, you move 2 3 4 to the end?
If so, its wrong.
I also do it from front, so I will only move '1' to the front so its correct for this case at least.
Well, it depends on how you've implemented it exactly, but generally speaking, you should find the longest subseq. of values increased by 1 (e.g. 3 4 5 6 7). When found, the answer is len(seq) — len(max_subseq)
The possible sample for my example subseq above could be like that: 1 3 4 2 5 6 7
But, answer is not LIS
OMG!!! I wrote this stupid comment 3 times ;_;
I used the condition
(A.weight < B.weight) || (A.weight == B.weight && A.inMST == 1)this leads sort sleeping.Cool !!! :) :) Mixing 3 sphere ? :D :D
in div2 D is the graph directed...because otherwise no loops dont make sense??
I think by "no loop" he means that no edge connects a vertex to itself.
Div2B's statement is a little confusing, that's why there are more people doing C than B.
so any help clearing it up?
i think many will really appreciate it.
So I'm no the only one who couldn't understand it :|
Oh My Gods!!!! D is so easy :D . No time to implement. Yay! figured D during contest
Sort edges. If 1st and 2nd one are 0, outpu -1, else add this edge to make a cycle in already made tree so far, using 1-edges
Since no body upvoted my approach, kinda doubting it now.... hmmm it sounded like kruskal's algorithm though
There is really sorting. But the algorithm is harder than you wrote.
Test case:
The answer is -1. You cannot make such graph.
My solution: First, sort the edges by weight, and if the weights are simillar, edges with b[j] = 1 will be eariler than with b[j] = 0
We must have
addvariable, which contatins the current size of the graph.Then, do the following thing: 1). If the vertex is in the tree, locate
addwithadd + 1and increase add by 1. 2). If the vertex isn't in the tree, we try to locate some vertexes in our graph, which is not located. We cannot also add new vertexes using this edge (remember that we have a graph with vertexes[1 .. add]). If it is impossible, print -1.It can be proved by Kruskal algorithm.
Hmm....since multiple edges are not allowed. So you must keep track of theno. of possible cycles you can make uptil a 0-edge is found.
It is not that hard, but it is definitely harder than A, B (except the statement reading :) and C :)
But, is my approach correct?
I don't really get what you mean, so can't say ) Seems close to what I've done, but not sure of your description.
Reversed Kruskal's algo. If a smaller edge is not included but a bigger one is, then that smaller edge(0 egde) must've been part of a cycle in a graph using the edges that are even smaller.
Sounds right. I've done the same thing:
Put the first included ones (2). Loop for others.
If one in included, put it in connecting new vertex. If not, check for the free place in current graph and put it there. If no free place = -1.
I have not seen a more confusing problem statement than of B.
Yeah I am still curious what they were asking. I can't imagine many non-Russians submitted for it.
If you make k moves, answer = 1 for that k if k-1th move didn't land in the same square, else answer for k=0. If k is the last in the string, pretty much any move will destroy it, so, all neighboring cells+the cell it is on at k-move is the answer for the last k.
Well, I'm russian, but it wasn't an easy statement for us too :)
Imagine the grid is full of bombs at first. The robot does X * Y tests. In the first try, it's obvious that he is gonna explode, since there is a bomb in the source point (he took no instruction, so k = 0). In the second one, the bomb that was on the source point is not that anymore, so he can take one instruction. If he walks to some position different from the one he is at, he is gonna explode. If he stays in source point he won't explode (k = 1). Keep doing this. The answer for k = s.size() is simply the total of tests (X * Y) minus the times he exploded in the other tests (since the path was out of bombs).
Кто-нибудь умеет ломать симплекс в С?
Меня взломали на контесте, когда я не делал random_shuffle. Перепослал в дорешивании с random_shuffle — прошло за 124мс.
Да я видел твой сабмит и сильно удивился, что тебя взломали. Странно, этот тест подобрали конкретно к твоему решению?
Тест начинается так:
Видимо, из-за каких-то особенностей конкретно той реализации что я использовал, она ТЛит на тестах такого вида.
In problem 'D' it should be written as "no self loop" as far as i learned.
it is already written in the output section that u != v. Please read the problem statement carefully.
And problem statement clearly said that-
Vladislav drew a graph with n vertices and m edges containing no loops and multiple edges.,I mean if we combine "u!=v" and the above statement then this problem becomes something else. So what nighthowler said makes sense.
UPD: Looks like i messed up "loop" with "cycle" in graph. Thanks to Swistakk for correcting.
No, it doesn't. "Loop" in graph theory doesn't have any other meaning than "self-loop".
In C, Can the optimal answer have more than two types of projects?
No.
Why?
C is a linear programming problem.
minimize sum{xi}
subject to sum{ai xi}>=p, sum{bi xi}>=q and xi>=0.
To make it the standard form, we need to introduce two variables y and z. Then it becomes:
minimize sum{xi}
subject to sum{ai xi}-y=p, sum{bi xi}-z=q and xi, y, z>=0.
The optimal solution of a linear programming problem can only be reach at extreme points of the feasible region. And extreme points must be solution to a linear equation system which has only one solution and is formed by some of sum{ai xi}-y=p, sum{bi xi}-z=q, xi=0, y=0, z=0. Since there are only two equation is not in form "x = 0", the extreme points can only have two nonzero components, i.e., optimal answer can be reach even if we don't used more than two type of projects. However, there are also optimal solution which is not reached at extreme points. So, the answer to the question should be YES. For example, ai={1,2,3}, bi={3,2,1}, {p,q}={2,2}. We can work on each project 1/3 day to get (2,2).
Well, "can" but not necessary. It only occurs when there are more than two points lie on the same line.
Yeah sorry I meant if there exist a unique answer. I guess my mistake is somewhere else -_-
I spent a lot of time to understood the statement? My English too poor?
This round is very interesting. I had lots of fun, even it is 2 AM here.
Well,the same time.
А какая задача была НЕ баяном?)
пруф или не было!
Задачу А я хотел дать на свой контест, но Zlobober сказал, что это баян и мы не будем ее давать. В итоге я скопипастил задачу из полигона.
Задача B может и не баян в явном виде, но идея абсолютно не свежа.
Задача C — стопудово баян с миллионом вариаций.
Задача D — аналогично B.
Чет мутный пруф какой-то. Но разбираться лень, поэтому гордо заявлю: согласно последним данным, не баян у нас Е!
Что-то похожее на Е тоже уже видел несколько раз. Про задачи A и C savinov прав, особенно задачи похожие на C последнее время часто были (например, похожая задача была на контесте МГУ в Петрозаводске примерно год назад, называлась Ito).
C — VkCup финал, задача "Макс Мин". Код оттуда отлично подошел
Действительно, к задачам, где надо найти выпуклую оболочку, отлично подходит код нахождения выпуклой оболочки. И что?
Ok, how do you solve Div 2 — A? I have never had so much trouble with an A before D:
let input be a1,a2,a3 and x1,x2,x3
if a>x then remain + (a-x)/2
else remain — (x-a)
yes if remain >= 0
Sorry, I didn't understand that at all.
Why not remain == 0 but remain >= 0 my solution hacked I write remain == 0 Can you explain me ?
Not sure about english statement, but in russian it was "AT LEAST x,y,z", so >= x,y,z
I made a mistake, I misunderstood condition more accurately did not read
After each contest , i ask myself " how many rounds left of my life of getting UNACCEPTED solutions and SUCCESSFUL hacks ? " :( :P
Well,I accomplished my code a few seconds after the test.
Me too. Made many stupid mistakes today......
Есть ли в Div 1D что-то принципиально проще 0-1-bfs по 2D дереву отрезков? Заранее спасибо за ответ.
Простой bfs по простому декартовому дереву.
У меня была простая sqrt-декомпозиции без лишнего логарифма.
0-1-bfs по 1D дереву отрезков.
I try my best to understand Div.2 B.But who can tell me what's the "test" means?What kind of role the "mine" played in the problem?What are differances between blow up with"a bug in the code" and without it?Maybe a explanation for the sample could make it easier for understanding.
m*n times of work
each time the mine in different block e.g. (1,1) (1,2) ... (2,1) (2,2) ... (m,n)
and process the same command
Now I get it,thanks.
It means the mine is in every position of the map,a position is a test
Thanks for help,it has bothered me throughout the test
ss
5 7 7
6 6 6
The problem statement for Div2 B was very poor, should have been clearer.
I think it was clear. But maybe it was difficult. I understood the task clearly. But i had some problems what I should print. And the tests can help in this case. Of course, it was harder than usual B. But it was real to understand and solve.
What the? In 2 weeks, Round 337 Div 1 but Round 335 Div 2? :O
What is the hacking testcase Div2 C ?
5
1 3 2 5 4
correct answer is 3
UPD: Sorry for the typo ... I fixed it
the correct answer is 2, move 2 to the beginning, then 1 to the beginning
1 3 2 4 5 -> 2 1 3 4 5 -> 1 2 3 4 5
Yeah, It is just a typo .. fixed it
the answer should be 2?!
Why? You can move 2 to the front and then move 1 to the front.
I think correct answer is 2 1 3 2 4 5 — > 2 1 3 4 5 — > 1 2 3 4 5 Have I made a mistake?
sorry for bad english :-|
You give me a heart attack !
thank Almighty, I almost had a panic attack seeing your test case :v
Div2C / Div1A, how to crack this nut?
Computed the length maxlen of the longest subarray that has a sequence of consecutive numbers sorted. and the ans is n-maxlen. Hope it is correct. I even survived two hacking attempts
how about "2 1 4 3 5 6"?
the sorted subarrays are:
1, 2 3, 4 5 6 therefore maxlen is 3 ans is 6-3=3
I should have said subarray that contains continuous numbers in a sorted manner. Sorry for bad english_
Found a funny bug :)
umm.... do u mean the upvote and downvote ? I had noticed it long time ago . So its a bug , eh? :v Didn't know. I just enjoyed the colours.
Think 'longest continuous sub-sequence' :) the answer is n-longest continuous sub-sequence. At least i passed the pretests with that.
Take 1 2 3 7 5 6 4. THe longest continuous sub-sequence is 1 2 3 4. Now you can shift the remaining elements in a particular order to get the sorted array always. At least that is how I thought of it intuitively
1 2 4 5 7 8 3 6
longest continuous sub-sequence: 1 2 4 5 7 8; 8 — 6 = 2, but answer is 5
(you should find longest continuous sub-seq. that has step = 1 (e.g. 1 2 3 4, 7 8 9), i think)
I'm not sure what you're saying. My logic was accepted. Here's my submission. Barely 5-7 lines 14730166
Sorry, you have correct solution. I thought "continuous" meant "increasing" or "decrasing".
1 2 4 isn't continuous, right?
(english isn't my native language)
Sub-sequence is an ordered subset of the array, 1 2 3 5 7 8 is a subarray.
That system test tho.
It was very difficult to understand the problem B (Div.2) isn't it?
For me, Absolutely NO! And I think many agree with me.
I still don't understand DIV2 B.... Can you explain output of sample test??? This is the most confusing statements I've seen...
Sample test 2:
Size of field: (2, 2). Start position (2, 2). Sequence: ULD.
Each round the mine starts in a different position of the field.
Round 1: Mine is in (1, 1). After executing UL the robot explodes, 2 moves.
Round 2: Mine is in (1, 2). After executing U the robot explodes, 1 move.
Round 3: Mine is in (2, 1). After executing ULD the robot explodes, 3 moves.
Round 4: Mine at starting position (2, 2). After executing 0 moves robot explodes.
Answer: 1 1 1 1.
Each position i(starting at 0) means how many times the robot exploded after i moves.
What is the point to check our English language skill by giving a problem like Div2 B -_- -_- -_-
Many will fail on DIV.2/C .. for a simple reason , LIS doesn't work ! :)
What is the point to test our English language skill by giving a problem like B -_- -_- -_-
So you want to say that I'm lucky because I'm preparing for The TOEFL test nowadays ? :D
statement of problem div2 B was very poorly made
I understand my bug in DIV2 D very late! cause that i couldn't submit the correct code :(
but i learned this: first think then code :D
In Div2D, test case 10
given answer is 1 2
2 3
1 3
1 4
My output
1 2
4 3
1 3
1 4
Checker Log is
wrong answer Multiset of lengths of MST edges is not the same as required by the input
Please tell what is the error in my solution? What am I missing?
in your graph, the correct MST is { (1,2), (1,3), (3,4) }, but (3,4) should not be included to MST according to input.
Interesting!! Even none could do four problems in that room.
How he possibly could do 115 hacks in total ? I mean, considering 4 solved problems, how much time was left to be spent on this ?
1.5 hours, last problem solved is in 32nd minute
"Oops I accidentally succeeded with two hacks" said .o. :D
Who ever knew they take your points away for non-successful hacks!
I think, it would be nice if after the contest we could see the test-case for which the solution got hacked.
Anyway, it was a great round!
You could see the hack case by filtering your solution in this page for Div2.
Thank you!:)
14723712 You can click on "View test"
Thank you! :)
1 point away from red :(
I accidentally made a submission, and now I am almost pupil
When you hack peoples code using a testcase your own code fails on
Div2 C hypnotize me :/
and it must be interesting =D
Div2 C was the easiest problem altogether
Yes i find out that after contest :)
well actually, B could have been counted as the easiest if the problem statement was written a bit more clearly
Wow, I didn't know .jpg can store animation...
:) :) :p
https://i.imgur.com/gBKH3cj.jpg
Hello, am I the only one who thinks that those two submissions share the same code ?
http://mirror.codeforces.com/contest/606/submission/14725950 http://mirror.codeforces.com/contest/606/submission/14730116
That doesn't look suspicious for me at all. Common part is exactly LPSolver which was very definitely prewritten code and could have been easily shared before contest. Note that main() functions are definitely different.
Here you go.
Yayy, today I have solved my first E ever ^.^ (more precisely, most valuable problem on a contest to include rounds with more problems)! Few times I was like two seconds or two chars\lines from getting it, I have solved many Es during virtuals, achieved >2700 rating along the way, but I was never able to get AC on E during real contest and today I finally beat that long standing challenge :)
div2 A http://mirror.codeforces.com/contest/606/problem/A
Why answer is "Yes" ?
Test #6
Input
0 1 0
0 0 0
Answer
Yes
It's Yes because the number of spheres you have of each color (0, 1, 0) it's greater or equal than the number of spheres you need of each color (0, 0, 0).
The problem statement says:
He does have at least 0 blue, 0 violet and 0 orange spheres.
.
swap(Div 2.Problem B, Div 2.Problem C);
swap(A,C) B is as it is
Почему остановилось тестирование у всех?
Оно на всем Codeforces остановилось, не только на задачах этого раунда...