Всем привет!
23 ноября в 19:35 MSK состоится очередной раунд Codeforces #381 для участников из обоих дивизионов.
Задачи подготовлены Александром Alexandr_TS Цаплиным, Максимом HellKitsune Финютиным и мной. Надеюсь, что задачи вам понравятся.
Хотелось бы сказать большое спасибо Глебу GlebsHP Евстропову, Николаю KAN Калинину и Евгению MrDindows Задорожнему за помощь в подготовке задач, а также Михаилу MikeMirzayanov Мирзаянову за замечательные системы Codeforces и Polygon.
В каждом из дивизионов будет по 5 задач. Разбалловку объявим позднее.
UPD
Разбалловка для обоих дивизионов: 500-1000-1500-2000-2500
UPD
Поздравляем победителей!
Div 1:
Div 2:
Отдельно поздравляем Petr как единственного участника, который решил задачу D в div 1.
UPD Разбор
Dont know why got downvote but hope it will be rated and fast judging
That's because I'm not Mike?:)
(downvotes)
It is not for that "you are not mike"
It is for this
Click and see everyone ! :| -_- :P :P
Can you pls tell me whats wrong with this revision?
Oh yeah it's rated! :( Really, guys, stop it.
(It's a meme)
Obligatory comment: Is it rated???
yes.
Is it rated ?
Finally usual five problems two hour contest in a usual start time :D
This time is no longer considered usual :D
Congrats! you didn't get downvotes
I have a lot of friends :D
Ура! Надеюсь контесты продолжат проводиться с той же периодичностью
Халява приди
Is it rated?
Yes
After thousands of "joky" comments about "is it rated?" I think we all need motto "Yes, it is f*cking rated".
Your graph is really inspirational halin.george :)
Will you put dp problem?
Will you put Greedy problem?
I think Six or Seven problems in Two and Half hours is more interesting. Because there at least four solvable problems to an Expert.
there is only half an hour between the time for the contest with 5 problems and the time for the contest with 7 problems and this is not enough to solve the extra 2 tasks
I hope I can become red after this round. (Maybe a little bit difficult)
and maybe jqdai0815
:)
Haha... Interesting ^_^
is it rated...! where is this guy there is one each time?
Did you read like the first 5 comments?
Also, what is the deal with you guys anyway? You see 3 "is it rated" questions being downvoted to oblivion, do you think the 4th time is the charm or something? What the fuck is wrong with you?
Please don't swear on Codeforces. Someone said their ISP blocks websites with these phrases so they wouldn't be able to access the site if their ISP blocks Codeforces. Please continue making the world a greater place ;)
Wish interesting problems and more ratings :)
Seems too difficult for me
finally no "usual" word in this round
finally no "usual" word in the statement
Which means it is an unusual statement.
Score Distribution? Its 16 minutes to start
Your wish has been granted
I'm freezing now , it's just a little bit hard to code with a blanket on your whole body
maybe some hard problems can make me warmer
Автокомментарий: текст был обновлен пользователем halin.george (предыдущая версия, новая версия, сравнить).
Guys how to change the language of preference to english. I am unable to understand the google translated russian into english. I know this is stupid but please help.
Click to the flag in the top rightmost corner.
I think it's going to be a hacking contest. specially problem A div 2.
Yeah, It will be. This is the first time I've seen my live rank bouncing up and down so frequently.
Also once you lock in and check others programs, you can easily identify a mistake if you made one and then start hacking others who did the same as you.
Here's an example of it happening to someone in my room:
That was a nice revenge bro!
Чуваки, завязывайте решать, там Ростов Баварию гнет :)
меня тут не меньше нагнули
Hackable contest
I wonder why so many people don't write bruteforce instead of dealing with lot of cases in div2A. Also, will mo's algo pass in problem D(O(N * sqrt(n) * log(n)))?
we love complicated Solutions
My solution was O (NlogN) in the problem D Div 2, or can say O (N) with lower_bound
it's a great feeling when you find your problem in a Codeforces round
link
you own me ECPC participants
thank you <3
Also Div2C/Div1A is similar with F from some russian contest.
Finally, I suffer from the problem that std::set has no way to count the number of elements < k ...
Hacks for Div2A
7 50 2 100
ans=50
7 50 100 1
ans=3
7 100 1 1
ans =2
Fingers crossed. Finally Blue. Maybe. :)
Dang I wish someone in my room hacked me.
You are now blue! Yaaay
Problem div1 B looks very similar to Problem J in the last ACM-ICPC Egyptian national contest.
Actually it is that problem, I have just ctrl+c ctrl+v the code.
i did the same but the log^2 idea that passed in the ECPC didn't pass now :D karma...
i have log^2 pretests passed .....
o.o
maybe you copied the slower log^2 :3
actually i didn't know that return make_pair() returns in O(n) also copying is in O(N) and SOMEHOW this code got ac in the national problem , great testing O_O
What does this mean? Anything related to make_pair ?
if u returned a vector with make pair it'll call the copy constructor
i got solutions skipped because i ctrl_c and ctrl+v the code i want that status removed right now... not my fault they decided to ripoff the problem
Also similar is http://usaco.org/index.php?page=viewproblem2&cpid=576
That's an LCA problem, and is completely different from div2D...
What I mean, is that techniques are very similar. Binary jumping and the prefix sums are both used in this problem, the only thing not included is the rewriting of the condition, but even that is a common theme in these tree query problems. This D was pretty much a subset of the usaco problem.
Oh whoops my solution to D was pretty different but I guess you're right ;)
Please, someone who passed C but had WA #4 before that, tell me what you have changed :)
Stupidly forgot to use long long instead of int in one of the variables... cost me 50pts.
Shit, my lazy array should be long long! Thank you! :)
Harder version of Div.2 D/Div.1 B
dist(v, u) ≤ Au => dist(v, u) ≤ Av
I misunderstand problem and solve the harder version in contest :(
Me too. :|
By the way how did you solved the harder version? ( Merging Treaps? )
I did it too -______-
I used segment tree with value compression...
Just realize I read the problem wrong after implementing it. :'(
O(n log n) with BIT.
Let di be the distance from i to root. Precalculate all value of ci = di + ai and sort these values. Then visit tree with dfs order. When we visit a vertex x, we can know it will contribute answer to which vertices by by binary search on sorted array c.
Please see my code for the detail: http://codepad.org/Q2NDUqDi
Simply by doing the dfs order, the problem reduces to finding the number of values <= x in a range, which has a nice known solution using BIT in increasing order of values.
How do you find the number of values <=x in a range using BIT? Can you please explain?
Sort the array values and queries values, together, then if an array value comes (v,0,index) update(BIT, index, +1). Else, for (v,1,index) query [l,r] answer = read(BIT, r) — read(BIT, l-1). This is a well known solution to this problem.
when I first saw the problem, I think it is the difficult version, and it takes me 20 minutes to realise
Can somebody explain C to me? I assume that mex is always length of the smallest subset + 1, but I have no idea how to make the array. Can someone explain? Also, hacks on A saved me, would've had a terrible result otherwise :D
Div2. Of course
Denote M = mex
Make array like this : 0 1 2 ... M — 1 0 1 2 ... M — 1 and so on. Any consecutive subarray of this array contains all numbers from 0 to M — 1
Ah, damn now I feel stupid. Thank you!
Let l be the smallest length of the subarrays. Then a[i]=i%l. It's pretty easy to prove
I can feel the power of Alyona's mother
-
I think it would be better if in div2 B : n, m <= 1000*1000
by the way thanks for contest.
True , O(n^2) shouldn't be allowed.
Div1 B is exactly the same with ECPC 16 J.
B — rewrite the condition and apply well-known tehnique
C — apply Maximum subarray problem for segments but with another combine function.
How to solve DIV1B? What's the well-known technique (Atleast I am unaware of it).
Yeah these comments are driving me crazy because half the discussion is about Div1b/Div2d but noone explaining how it works :)
For a given node i, let's find what's the closest node to the root that still controls node i. In other words, we need to find the closest node j such that i is in j's subtree and dist(j, i) <= A_i. This sounds like a job for binary search. I implemented the process of finding j using skip-lists. The lowest node that controls i, is i's parent. The farthest node from i that still controls i, is j. So every node that lies on the path between j and i's parent control i, or in other words parent[i], parent[parent[i]], ...., j. This can be calculated using the same technique as in partial sums' updates. If for a node x, parent[i] is in its subtree res[x] += 1. If parent[j] (first node that doesn't control i) is in its subtree as well, then res[x] -= 1.
Petr using C++, what has the world come to???
Free CLion evaluation ends in 5 days, will switch back to Java soon :)
Petr, I'm happy you've solved D. It was my idea of the problem.
Codeforces has hosted Kotlin Unknown Language Round and got few licences for free. I'll be glad to make you a gift: one year 100% discount for any JetBrains product. Each time in a year if I'll see your "Accepted" on C++ I'll be glad to think that there is small part of our contribution there :)
Well, I think they pay enough in Google so that issue is not in having the license :)
We are going to end up with battle between Egor and riadwaw for users with their respective products CHelper and JHelper :)
some hints for problem C?
Check this comment .
find minimum length interval len = (r - l + 1) obviously answer can not be more than that. So just print 0, 1, ...len - 2, len - 1, 0, 1...
you can see that for every interval mex will be equal to len
It was not "obviously".
Maybe you are right, but at least it's something which does not require too many steps in thought process. Either you see it or you don't, it's not like you have to think of A then B and then come up with conclusion as in many harder problems.
Shit !!
I used binary search on mex! :P Shame on me...
But got AC... This Shouldn't be allowed ! :)
OMG!!! I had two bad performance in two contests, I think i should take a break for a while :(
Or the other way around — train more intensively before the next contest, which will be in this sunday :)
Too much pressure is not good...
Maybe codeforces's computers are too fast! Div1. E:22443543 This submission just uses an O(n^3) and passes !
Lesson learnt: brute force even the obvious solution looks a bit too slow :(
http://codeforces.com/gym/101147/problem/J
is similar to today's div. 2 D. I got AC in Gym, but the same code didn't pass today's system test. :'(
shame on me
I've prepared it's tests very well
can your please give me your code ?
hello i did this problem J one time and i just did the same process as that time i solved J since i already solved the problem, i used my own code as a guidline (since is gym obviously i am basically guiding myself) and send it , now i got skipped obviously because you guys are flagging me as cheating, remove it. If you are going to ripoff a problem without any twist don't expect us to do something different if we already solved it before. Thanks.
Можно ли без особых извращений сделать k-ую порядковую в set-e?
Это?
When system testing will start ?
it's nearly not fair that the people who solved the ECPC problem j only paste their code in problem D div2 and got accepted
By-by blue.... :(
so hacking :)
Omg, D is so tedious. If I'm not mistaken it can be simply solved by linear greedy, but that requires big amount of ifs and a lot of stupid boring code.
EDIT: Okay, I was wrong. So easy to get head messed up at this one.
Hmm, I had similar thoughts initially, then I realized I was wrong. The solution I came up with uses maximum matching.
EDIT: After getting it accepted, I can safely say that even though it isn't greedy, the solution still requires a shit-ton of special cases :D Or maybe I just lost my touch...
How to solve problem E (Div2) ?
Probably seg tree + lazy propagation
For each interval, keep the left hill, the right hill and the answer. When you merge 2 intervals, the answer will be:
max(new left hill elements, new right hill elements, hill in the middle (you merge the right hill of the left and the left hill of the right), max answer of the smaller intervals)
merging the hills needs a bit of time to code but it's not hard to think about the answer. You will need to save the left number, the right number, whether it has reached a peak, whether it is decreasing/increasing, etc.
can Anyone describe the solution of problem D in Division 2? i got nothing other than O(n^2) solutions.
I can tell you how I solved it.
Build sparse table on a tree. You have every 2^kth parent and for every 2^k parent sum of all edges on path.
Now, for every vertex we want to find the farthest parent such that our node is controlled by this parent. Notice that sum along path can only increase, so it's binary searchable. In this part we use 2^k parent, which we have from sparse table. Let's call that farthest node V.
All nodes on path [V -> our node] controlls our node. Then we use little trick: add 1 to parent of our node and -1 to parent of V. Now with standard DFS we can finally make answer.
Of course, I've omitted implementation details.
I was working on this problem but got stuck on how to add +1 to those nodes that control the current node, how does the "little trick" work it's not clear at all? Thank you.
We have an array where we want to sum v on intervals l<=i<=r.
Let's first process the intervals and then get the array. The array "a" first starts with all 0's and there will be an auxiliar array "aux". When we want to update the range, we make aux[l]+=v and aux[r+1]-=v.
But why? If we consider the cumulative sum of all elements of aux until i, we will get exactly the value that we added on i. So to get the answer we do aux[i]+=aux[i-1] and a[i]+=aux[i]. Why does this work? Because on the range l<=i<=r, you will have v on the sum and from r+1 onwards, you will have excluded that v, as needed.
Can you help in figuring out the mistake ? (the test case is big) . My approach is exactly same as yours. http://codeforces.com/contest/740/submission/22459911
I had a greedy solution for Div1 C but it was splitting into a large number of cases. How to improve the solution?
For problem c:find the minimum gap among all the l and r ranges...val=min(val,r-l+1) run this for all m subarrays and now just start off with a variable x=0 and print it modulo val and then increment x after each iteration
div1 C :)
super fast system testing
Спасибо за очередную задачу, в которой проходит подмазанное тупое решение 22443543.
Если писать во float-ах, то вообще 2 секунды 22450669
Если флажки подпихнуть, то секунду: 22452676
(ну тут никакой магии, если кому-то интересно, просто там очень простые операции со float'ами, компилятор оптимайзит в SSE почти все)
Hack-round
Автокомментарий: текст был обновлен пользователем halin.george (предыдущая версия, новая версия, сравнить).
Hello, why in the world my submissions are "skipped"? , it is not my fault that you decided to ripoff a problem from the Egyptian ACM contest, my solution is exactly that , you can't argue i cheated in the contest. If i solved the problem the same way i did in that contest is not cheating, so please remove the "skipped" flag on my submissions... thanks.
My name disappeared from the final standings and I found my submissions transformed to skipped on my profile. MikeMirzayanov why did this happened?
I see cheatCount=9 in database in your profile. So I simply even do not want to answer.
Hello can you check mine? you can even check on the GYM the solution my team and i did for problem J sadly the setters decided to do the same exact problem, so i just used that solution which is ours. But got flagged as "skipped" , sir i never ever cheat on this contests, i beg you to check i don't want to miss my chance to get back to blue and be treated as a shady contestant which i am not.
Contest is ACM Egyptian Collegiate Programming Contest 2016
I opened the profile of "_underr" and couldn't find a submission with ID "18552489". Also user "just_fuck_you" logged in 4 months ago, so how does this relate to me and to the contest? Please give me more details about why this happened.
MikeMirzayanov I appreciate if you could give credit back to my solutions, as seriously the solutions you mentioned don't belong to me and I don't know anything about them. I've been competing actively for many contests and I never cheated.
You can re-check my submissions, and for example, I submitted the 'A' problem very early from first time (maybe after 3 or 4 minutes from the contest) so it's not logical that I was cheating.
Thank you.
He implies you are cheating from a long time. See in this contest : http://codeforces.com/contest/740/submission/22428017 , http://codeforces.com/contest/740/submission/22428028
Can, you give me phone number of pashka921? I want to ask him if he is your father or mother?
Also, your post should be downvoted to hell and oblivion.
Also, don't make white lies — _underr's submission is here: http://codeforces.com/contest/682/submission/18552489
For Div1 A, a[i] = i % ans did not strike me. So I thought of removing the intervals which subsume at least one interval. Now, sort the intervals according to the left end. Now, you can fill in O(nlogn) by only checking for those elements which do not overlap with the just previous interval. Did somebody go down this line?
http://codeforces.com/contest/740/submission/22453551
Can you please explain little more in detail. I was thinking in similar lines. Thanks :)
Triveni sir, if you remove all the intervals that subsume another interval, then it would not matter, because the smaller interval will have all the numbers from 0 to ans — 1. So, step1, remove such intervals.
Step2, sort intervals by left end;
Let the intervals be a1, a2.....
Then you have to understand that ai.l < = aj.l and ai.r < = aj.r for all i < j. So, when filling ai you check for overlaps with ai - 1 and fill the part only in ai with elements only in ai - 1. In this way, you fill each position at most once, so O(n). We need O(logn) to check if an element is already in the interval or not, so O(nlogn).
TLDR: we fill part of each interval that is not contained in the previous interval.
Can someone provide a hint on how to solve Div2 D?
dist(v, u) <= a[u] <=> dist(u) — dist(v) <= a[u] <=> dist(u) — a[u] <= dist(v)
TooSimpIe beats Petr!
Какой хороший раунд, впервые получил больше +300 за один раз
Please update the ratings with the same speed as the system testing so i get to know how much will my rating decrease :(
For you -12. You are welcome!
When will be editorial?
Nice contest :D
Ehhh, out of seven ACed solutions to E, four are obvious O(n^3). Will this ever stop? Give me my deserved TOP5 :<.
Give me my deserved TOP2 :<
Problem C was a mess to implement. Problem D was worse, as far as I saw. Problem E seemed the cutest one, but could be squeezed with N3 complexity. I'm not blaming anyone, I just hope the next rounds will be more balanced.
Here is proof: http://codeforces.com/contest/739/submission/22452983
By the way, what is the solution for problem E?
http://codeforces.com/blog/entry/46693
I used min-cost flow to solve the linear program: http://codeforces.com/contest/739/submission/22454812 I feel like it should be O(n^2 * log n) if implemented efficiently (mine uses Bellman-Ford, hence probably isn't theoretically fast enough)
Can anyone tell me why this code for Div1 A gets WA but this code gets AC?
O my bad! Anyway thanks.
a[n][2] — m>n
I sent a PM to MikeMirzayanov i found out new information but i don't want to spam him, so i will copy and paste the PM here:
"Hello sir, since nobody is addressing my petition to check on my submmited codes nor answering why i got flagged as a cheater, i will then send this message and hope you can answer me. Sorry for the inconvenients but i am really mad about this situation.
Problem D div 2 is the same exact problem as problem J in the ACM Egyptian Collegiate Programming Contest 2016, me and my team solved this problem around 2 weeks ago or a little more.
Since it is the same exact problem without any twists i just used my already AC solution, it is not my fault that the problemsetters did not want to place any kind of twist to the problem nor i care, if the problem was that and i did not copy it from anybody in the contest i am 100% sure that can't be counted as cheating, so please remove the skipped flag since this makes me look like a shady contestant, but i have never cheated in any CF nor any contest in my life, actually i am fighthing about cheating in ACMICPC since a long time. So please check, i guarantee you, you will find out everything is ok."
Now to the new.
A friend of mine user poiuyt2022 , found out that there is a user that ripped off my solution for problem D from the contest, which it is indeed cheating, but had nothing to do with me, link to the submissions:
http://codeforces.com/submissions/_underr
Can you please put me back into the contest?.
EDIT again: The issue was addressed, thank you so much for reading and helping, hope everything goes fine with this.
And when will this Tomorrow for editorials happen?
Auto comment: topic has been updated by halin.george (previous revision, new revision, compare).
Auto comment: topic has been updated by halin.george (previous revision, new revision, compare).
Why does everybody use binary lifting? I just used the merging sets technique + priority queue. It's quite fast tbh.