Всем привет!
17 июня в 19:35 MSK состоится очередной раунд Codeforces #358 для участников из второго дивизиона.
Автором всех задач являюсь я, и это мой дебютный раунд на Codeforces. Надеюсь, что задачи вам понравятся.
Хотелось бы сказать большое спасибо Глебу GlebsHP Евстропову и Данилу danilka.pro Сагунову за помощь в подготовке задач, Михаилу MikeMirzayanov Мирзаянову за замечательные системы Codeforces и Polygon.
Участникам будет предложено пять задач и два часа на их решение. Разбалловка будет объявлена позднее.
UPD
Разбалловка: 500-1000-1500-2000-3000
UPD
UPD
Поздравляем победителей!
Div.2:
Div.1:
Auto comment: topic has been translated by halin.george (original revision, translated revision, compare)
The comment is hidden because of too negative feedback, click here to view it
Poor trick :/
Semester final! The very next day. :'( But well, who cares? xD
In my elementary school, it is also a math final examination. I don't care the score, but I care my father's stick fore when I don't get full score. All in all, I will have this contest in my quilt, and beat everyone who see this comment!
It's very excited.
Road to Master
What's your meaning?
Road to blue. xD
Every time I saw your ID, I would mis-read it as JiBaYang.(For people who don't understand: This means "my dick itches" in Chinese.)
I thought I was the only one...
You are bad man!
Hoping to turn green today :D
Hoping not to turn Green today :D
Hoping to remain blue
Codeforces has invented a way for its users to comment even if they are inside a dream
But I think my color is blue, and your color is green...
Hoping to become blue...?
halin.george, your graph is inspiring.
There's a huge gap from July 2013 to April 2014. He must have trained very hard in that time.
I wish to achieve something like that :') ancien, thanks for making us notice it
break;
Email for regular rounds is always saying that the contest duration is 2.5 hours and it will contain 6 problems.
it's said that on your birthday everything goes well. lets see :)
Hey, happy birthday.
thank you . and wish you high rating :)
Happy Birthday! and all the best :)
thank you :)
how old are you?
happy birthay amigo
I have went back to green, and it makes me sad for several days QAQ
it is sorry.
Hello gay， I love your id！
Why you know he is a gay?
It's not green, it's cyan.
You will be blue again, I think.
Thank you.
Can I get your facebook girl?
No.oN
Dat palindrome.
No.oИ Hello from Russia :)
Oh my god. There is no JIBANCANYANG's message here!!!
You can find it here: http://www.codeforces.com/blog/entry/45475?#comment-300556
It is here, and somehow he managed a +ve number of likes too! :P
Do you mean I always get oppose?
You'll make it, xiaoai. ;)
Подлизун
I probably have missed blue this contest, at least I am diamond in league of legends!!!
halin.george your graph is truly inspiring for us. hope to get positive rating.
Although there will be a exam tomorrow, thanks for this contest，hoping to turn green(just rating + 1)!
hoping to perform well in this contest..... working hard :-) hope i get blue :-) n its inspring to see graphs like these !! thanks :-)
Did you light a candle? It may work :)
What's up with these hoping comments?
hoping not to repeat the mistakes made in the previous round and making no new mistakes :D
The only way to learn is to learn from mistakes :)
I don't what I should say.
This my first time to take part in Codeforces. I'm very excited!!
All the best man!
Hello,girl.Can I get your facebook?
Sorry.Facebook is a inexistent website in my country.
Can I get your Wechat?
Nope!
hoping be a rated contest
Hoping that you will learn english
No need to be rude.
think twice about grammar, write once :v
It will be my first round on codeforces. Just learnt coding this month Wish me luck :D
Good luck and welcome to CF community!
no matter how bad it is or how bad it gets ......i'm going to make it.......
https://www.youtube.com/watch?v=dQw4w9WgXcQ
Guys I am Beginner from India,is this Contest for me or not? Any suggestions?
Yes, the contest is open for all! All the best. :D
this looks like a fake acc
Series of Contest coming , two div1+div2 contests :D
Also in the last 5 days, 4 contests in Codeforces, among them 2 contests are being rated. It's amazing !
hoping for delicius problems
I wish to be Specialist today =D
Off topic question.
Why do these codes give different output for
run(0,3)?In second code, mid value in run(l, mid) is not same as that of in run(mid + 1, r). You can just simulate the function calls till depth 2 or 3 and you will get to know more clearly!
In the second code after running run(l, mid) recursion the mid variable will be different for run(mid + 1, r) (because it was modified in the other case). And in the first code it remains the same.
global vs local variable.
if you want to keep mid as a global variable, you have to reassign it after the first recursion so it has the correct value again.
Hoping to turn black and red today
GOOD LUCK EVERYONE! GET MORE RATING!
Автокомментарий: текст был обновлен пользователем halin.george (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by halin.george (previous revision, new revision, compare).
Wish my rating higher than 1700
Сложно Ее взгляд упал на строки s и t, длины которых равняются n и m соответственно. Как обычно, Алёне быстро наскучило читать, и она решила переключить внимание на строки s и t
Just look at the top 3 of div 2 participants.
what is the point of creating fake accounts?
ХОЧУ БОЛЬШЕ МИНУСОВ
i'm only 9th 'cause Shokoladnitsa sucks :(
Мы в русской ветке. У меня есть неплохая идея, какие хэндлы вам нужно взять на следующий div2-only контест, если сможете занять топ таблицы в правильном порядке.
ХОЧУ БОЛЬШЕ МИНУСОВ
Что-то не так с таблицей результатов: некоторые посылки не отображаются. Например, 1e18 вроде решил первую задачу (посылка 18547785), но этого не видно.
Upd: Fixed
How to solve D?
http://mirror.codeforces.com/contest/682/submission/18554461
Nice solution, thanks. But how to calculate asymptotic complexity? It's O(nmk), right?
Yes
No it's worst case O(nmk(n+m)) because of the while loop. That I guess is why it failed on TLE
fill -1 http://mirror.codeforces.com/contest/682/submission/18710163
U need to go to KFC to solve such hard problems.
You are not funny. Please delete this account. Use your 'normal' one. It's against the rules to have multiple accounts. I wish your red or nutella account get banned for this.
th-th---thanks senpai!
D can be solve using dynamic programming. See my submission for details.
I made a similar recursive solution and was consistentaly getting WA at pretest 4.
In this part of code
I missed the second line
ret=max(ret,rec(i+1,j+1,k-1,0)+1);. I thought that when characters are same then breaking into substring at this point is bad idea.The girl noticed that some of the tree's vertices are sad, so she decided to play with them. Let's call vertex v sad if there is a vertex u in subtree of vertex v such that dist(v, u) > au, where au is the number written on vertex u, dist(v, u) is the sum of the numbers written on the edges on the path from v to u. this statement is not clear...
And I thought you were about to say something humourous :P
Who dis?
fake accounts , CodeForces must reduction of this phenomenon
how?
Just relax. In McDonalds especially for you we have an open cleaning position. 10$/hour
You are good with algorithms but bad as a person. Hope you get banned
The facepalm moment when you realize that you have misinterpreted the variables u, v in the problem C. Normally I use v for child, u for current node. So I messed up in understanding the problem and instead implemented a slightly complicated solution.
The exact same thing happened to me and I started solving D in the mean time. When I came back to have a look at C for the last time, I realised that I misinterpreted the u,v nodes and then I was able to solve it in 5 mins. Truly Facepalm!
My facepalm moment when I realised that i had misunderstood D as a harder version of the problem :(
Same here. But thankfully realized that the figures in explanation of samples won't make any sense in such an interpretation, hence was forced to look back and check. Still, the notation used in statement is pretty unusual.
What is testcase 4 of problem C??????????????
I using BFS from root=1 and I remove every child node of V when sum(root,V) > a[V]
is it wrong solution??
when sum(root,V) < 0 you should make it 0
before sum(root,V) > a[V] every node will push back to queue.
although sum(root,V)< 0 it will be pushback
Can it be solve using BFS ? because I use DFS
Both are fine
Wrong solution:
3
1 10 15
1 -100
2 115
your solution doesn't delete any leaf, but need delete leaf number 3.
why delete leaf number 3?
in this case sum(root, 3) should be 15 and a[3] = 15 so i think it isn't sad vertex..
This is why your solution doesn't delete third vertex.
But sum(2, 3) = 115 and a[3] = 15, so 2 is sad vertex. This is why you need to delete third vertex.
You don't need to check sum(root, V). This is because, the question states that a vertex V is not sad if sum of weights from node V to any node u in it's subtree should be <= a[u], but you are considering only sum from root. There may be a case where weight of root to all it's children is negative. So, we don't have to count the negative weights. For eg., Consider this graph : 1->2->3 Let wt(1->2) be -10, and wt(2->3) be 10. a[1] = 1 , a[2] = 10 , a[3] = 1. Here, vertex 2 is sad, because path 2->3 has weight 10, but a[3] < 10. However, you will end up considering weight as 0, because you will be adding the weight of 1->2 as well, which is not required here. Hope you understand. I haven't taken a look at the test cases yet, but I too had a WA on pretest 4, and this was the change I made to get Pretests Passed verdict. Hope this helped!
First time to get pretests passed with 4 problems, I hope they survive the main tests :P
It was my worst contest ever, I spent one hour to solve A and i am still not understanding how to solve it efficiently
You should combine 1 with [1, 2, 3,
4, 5, 6, 7, 8,9, 10, 11, 12, 13,14, 15..]More clearly:
1 + 4 = 1 × 5
1 + 9 = 2 × 5
1 + 14 = 3 × 5
...
Even more clearly:
1 + (4 + 0 × 5) = 1 × 5
1 + (4 + 1 × 5) = 2 × 5
1 + (4 + 2 × 5) = 3 × 5
1 + (4 + 3 × 5) = 4 × 5
...
Do you get it?
I have a simpler method than that look at 18552140.
It is not a solution.
It is about how you should start thinking :)
For problem E, you just need to find the triangle with largest area... but I have no time to implement it T_T
You can fix two points, and then run ternary search to find the maximum. It is n²logn. This was the first time I solve E, but I didn't manage to solve C, D for some reason :(
Can you please elaborate?
You are right, and this can be optimized to n^2 by using two pointers. All I need is time...
Yes, it is TLE using ternary search.
This is my worst round. solution to A failed test 11, I took a long time checking code but still can't find what's wrong. solution to D is the same case, can't find the bug. my rating will have a big decreasing ...
Maybe you forgot about using long long
In A, the result can be larger than 32 bit int
I am so stupid .......
Take a look at my graph and keep fighting bro!! We all have bad days :)
maybe my solution could help?
http://mirror.codeforces.com/contest/682/submission/18566989
Anybody used hashing in D?
I did a dp on [i][j][used][using] where used is the # of segments started so far and using is whether a segment is running...
I have no idea if this actually works; I just BSed a solution while being frustrated about missing TC 3 on C and it ended up passing pretests lel
Dp :-?
There's a pretty simple dp solution: http://mirror.codeforces.com/contest/682/submission/18566989
The only solution with hashing i can think of is if you used binary search + hashing when "taking" a segment, to quickly find out for how long are both strings the same. Not sure if that solution would be fast enough, though.
Do you care about my sad story?
Today my family told me they're not proud of me. ;_;
So I decided to compete today, just to get some acceptance ;_;
And you got +67 rating, your family must be proud of you now :)
Unfortunately, they don't. I'm glad the judge at least accepted me
I'm so sick of these red's fakes which win Div 2 contests
Are u referring to KFC logo being red?
Well, registred 3 hours ago, just before the contest -> total newbie here, but able to finish third? Seems legit...
ухади.
When I was hacking, I noticed that this submission 18550167 of problem B included the solution of problem A as comments. Does this count as rule violation? Some contestants might lock their B and be able to obtain a solution of A.
I finished C 2 seconds after time's up...
How to solve E (without random shuffle) ?
I think you should get the convex hull, fix two points, then ternary search the third point for the largest triangle then do the scaling
How to solve C ?
Read about Kadane's algorithm (maximum subarray problem) first (it is very easy — a 5 minute reading).
Now let's take a look at some internal node vk. There is a path from root (v1) to that vertex:
v1→...→vk
The only thing we need to determing is whether vk makes feel sad ANY of the nodes on that path (that sentence is the key to understanding; read it again till everything is clear).
The node vk makes some of the nodes on that path feel sad only when
a[vk] > max(d(v1, vk), d(v2, vk), ..., d(vk - 1, vk))
Kadane's algorithm helps with finding max(...) value fast during dfs.
dfs(v1)
maxDist = max(0 + d(v1, v2), 0)
↓
dfs(v2)
maxDist = max(maxDist + d(v2, v3), 0)
↓
dfs(v3)
maxDist = max(maxDist + d(v3, v4), 0)
↓
...
dfs(vk - 1)
maxDist = max(maxDist + d(vk - 1, vk), 0)
If vk makes someone sad — it is a bad vertex and we have to remove it with all of it's descendants (using the same dfs we calculate how many children every node has).
Is the vertex can be categorized as sad if a[k] > d(1,2)+d(2,3)+...+d(k-1,k)?
How to deduce it to a[vk] > max(d(v1, vk), d(v2, vk), ..., d(vk - 1, vk))? Thanks
It should be a[v]< max(dist)
problem D is exciting, DP but not simply DP :)) :))
How is it any different from LCS? Am I wrong in assuming that the only added condition is that the answer of lcs >= k
Yeah abcdef abxef k = 1 LCS: abef
Okay
http://mirror.codeforces.com/contest/682/submission/18564850 Got WA :( Can someone tell what is wrong with this soln?
You're not completely reseting your dp table. Loop until r <= 10, not r < 10.
It is simply dp. Just 20 times more states than regular LCS, and one more line.
http://mirror.codeforces.com/contest/682/submission/18566989
Guys from Div 1! It's really not fun to see you competing with us, taking rating that we deserve. Why do you dissapoint others? Would you like this situation if you were in Div 2?
We participate Out of Competition, so Div 2 rating is not affected. You can uncheck the button "show unnoficial" in the standings
I think he is referring to the Div 1 people who participate with a fake account.
That makes more sense
He is talking about the 'funny guys' that ended up in first to third position using fake accounts.
When will system testing start? :(
Started.
For problem B test case 105 is anti-quick sort one . So for all problems involving sorting can we hack other's submission by providing anti-quicksort case as in Java Arrays.sort juse quicksort rather than merge sort. Is it valid?
Use ArrayList instead...
I know that but I thought that providing anti quick sort test case is against the rules.Once in an Educational round it had an anti quick sort case and after that contest I used to have merge sort implementation in my template but didn't use it.
What's going wrong with problem B, s.o could explain for me the difference between these two solutions one takes only 186ms and the other exceeds the time on test 105 : http://mirror.codeforces.com/contest/682/submission/18551509
http://mirror.codeforces.com/contest/682/submission/18550284
BY shuflling the array anti-quick sort test case doesn't work
Arrays.sort uses quicksort which has a worst case time complexity of n^2. Test 105 must have made this happen. If you shuffle the array, then it will run in closer to nlogn time.
It's incredibly unfair to make such test cases for Div2 B. Every solution that uses java.util.Arrays.sort failed with TLE.
Not all. Only those that passed an array of primitives to Arrays.sort
Lesson for everyone, dont use vectors, use static memory always to be safe.
My D MLEd on test 59 because I used vector to memoize. Changing to static array makes it AC :/
With array: 18565081, with vector: 18558041
for B, I don't know why I thought of adding the numbers to a hashset and then iterate over them and add them in ArrayList and then sort it and find the answer, even though it was such a simple question and later saw the solution I was like "was I drunk today"? :P
But seeing all the java solutions getting TLE in an anti quicksort test case I now feel damn lucky to have been drunk :P
So.....fake participants won't be eliminated?
You can't prove they are fake
If CF's cheat detector could detect coding styles, then it would be possible.
So sad, B problem has a test that kills Arrays.sort in Java. I only had to change long for Long, after results. :(
Edit: never mind, I found out what's in common with the solutions failing B: primitive int arrays. Either Array.sort() is really bad at handling primitive ints as bodmas said, or the unwrapping when you cast Integer objects (from Integer.parseInt) to primitive ints is super slow. Wtf Java!
Seems relevant: http://mirror.codeforces.com/blog/entry/4827
Java uses Quick sort for primitive type sorting, and merge sort for Object Sorting. Quick sort runs in O(N^2) in the worst case, so that alone would TLE your solution. ( Also this does not occur in every problem, sometimes random test cases happen to do that, or the author does it on purpose).
Alternatively, a nice strategy is to shuffle the array before you sort, or declare it as Integer/Long instead of int/long, that way it becomes an Object and runs in NLogN.
Can I use Integer always or it is slower than int in other operations so I should only use it when I need to sort?
Integer will be slower than int because there will be autoboxing/autounboxing involved with it(you can read about that here).
That being said, the performance reduce because of Integer won't create a difference big enough for an AC solution to get TLE in competitive programming for almost all problems.
But the best solution before sorting will really be to just shuffle the array.
Turned Blue :D But.. I can't think of Dp solution for D. Can anyone help me out?
I also turned blue :D Hopefully I don't lose it this time. Maybe my solution could help? http://mirror.codeforces.com/contest/682/submission/18566989
If you already know regular LCS dp, it's not hard to limit it to only take 10 substrings. And for regular LCS dp you can just google it.
Rating changes disappeared from graph and contest tab of user profiles
Ratings have been updated. My rating improved by 1 :)
Yeah
And the unrated people from top 10 removed also :D
Should be more than top 10, don't you think? Anybody who registered 5 hours before the contest and made it to top 100 is suspicious
I say top 10 by guessing as i only advanced 5 positions.
and look to this one ( mikezhw ) he registered 6 hours and ranked 17th, but anyway this is awesome that CodeForces admins made this choice this time :D
Registered as in, registered on codeforces with a new handle. Maybe they should inspect all handles that were registered just hours before the contest.
Thank you for eliminating fake accounts! I think it should be stated clearly that fake accounts violate rules of CF.
Seriously. I missed Blue by 1 rating -_-
Seems like there is something wrong with checker for problem E:
UPD: Here is the 18565596, starting from test #33 all outputs are "0 0"s and checker still says it's OK
You are undoubtly right, there was a problem with checker. Unfortunately, checker at the moment of the contest duration has not checked that the output triangle has non-degenerate area.
This causes a bug in checking if the triangle contains all the points from the input, because it is implemented by checking the sum of three triangle areas equality to the original triangle area, i.e. if the ouput triangle is ABC and checker processes point P to check if it is inside, checker just ensures that S(ABP) + S(APC) + S(PBC) = S(ABC) states true, then it considers a point lying inside. Of course this is not true statement if, for example, A = B = C or the point P lies at the same line as the points A, B and C do (if they do). Of course, now we have fixed this bug and implemented additional checking on the triangle area.
This unfortunately caused one solution to have accepted on the final tests (which it shouldn't get), but we have decided not to change the verdict because, firstly, because the participant had "Pretests passed" verdict during the contest, which he should not get the participant, secondly because his solution has the right logic and has some non-crucial bug causing the output triangle to be with degenerate area, and thirdly because we have found it late, very after the system testing. We hope the community will understand our decision right.
We are very sorry for that, and I hope that the explanation above will help someone in contests or in preparing of those to not to allow this situation happen again.
I've just noticed that my rating change increased by 3 , it was +93 but now +96 .
Fake accounts have been deleted from scoreboard , I was in 136 place but now in 130 .
Once fake accounts got removed, you should change the list of winners too.
Well, it looked like a good joke, but in fact it's not. We are really sorry for it and won't do it again. And I politely ask administration to remove us from scoreboard. And sorry one more time.
I'm not sure how they did it, but you are removed, at least from the top contestants.
Can somebody please explain me what is wrong with my solution for problem C? Thank you in advance! :)
http://mirror.codeforces.com/contest/682/submission/18561628
EDIT: Nvm, I think I got it.
Nice Contest, Well Done!
Is B even solvable in Java? My solution was literally the same as the solution in the editorial. I even modified it to use BufferedReader and String.split(" ") and it still fails on the last test case...
Any ideas how to speed up the input?
Check this comment regarding your TLE.
I just sent the same solution but with ArrayList instead of int array, and it passed. Are Collections.sort() and Arrays.Sort() different?
EDIT: nvm, I read that sorting primitives is in quick sort, while sorting objects is in merge sort. Hmm a weird design choice if you ask me...
In D , why is my soln giving memory limit exceeded on n=1000 m=1000 k=10 I have used dp[n+1][m+1][k+1][2] array http://mirror.codeforces.com/contest/682/submission/18585400
Try to sort the array dimensions, i.e. change it to dp[2][k+1][n+1][m+1]. Will help you a lot for sure.
yup that was the problem Point noted
Hi halin.george :D I solved your problem Alyona and Triangles, but i was curious, about find a maximum area of a quadrilateral, instead of a triangle.
Do you can help me? To find the maximum area of a quadrilateral in set of points? Do you know any problem about it?