Всем привет!
Лето... Прекрасная пора для поездок на отдых, прогулок с друзьями, новых открытий и, конечно же, написания новых увлекательных контестов на Codeforces. Поэтому, я предлагаю к вашему вниманию мой новый Codeforces Round #495 (Div. 2) с интересными задачами и не менее интересными разборами, который состоится в 05.07.2018 19:35 (Московское время). Если ваш рейтинг меньше 2100, этот раунд будет для вас рейтинговым, иначе — вы можете участвовать вне конкурса.
Хочу поблагодарить Михаила MikeMirzayanov Мирзаянова за помощь в подготовке и за системы Codeforces и Polygon. Также Ильдара 300iq Гайнуллина, Дмитрия cdkrot Саютина, Даниила danya.smelskiy Смельского, Chin-Chia eddy1021 Hsu и Kevin ksun48 Sun за тестирование задач.
Вам будет представлено 6 задач и 2 часа на их решение. Разбалловка будет объявлена ближе к началу раунда.
В этом раунде вам предстоит помочь девочке Соне с ее ежедневными проблемами. Удачи вам в этом!
UPD. Разбалловка 500-1000-1500-2000-2500-3000.
UPD. Поздравляем победителей!!!!
| Место | Ник | Баллы |
|---|---|---|
| 1 | EZ_fwtt08 | 7892 |
| 2 | milisav | 5550 |
| 3 | VisJiao | 5294 |
| 4 | Jatana | 4832 |
| 5 | wasyl | 4762 |
June 5?? Please correct the date, it's JULY 5!
June 5?? Please correct the date, it's JULY 5.
I think this is the shortest, precise and most exciting round announcement I have ever read.I hope the problem statements are along the same lines.
Hope that we wouldn't see number 502 with label "Bad gateway" again)
CF servers, please, be OK during the contest.
maybe best joke ever
maybe best editing ever. Did you use Microsoft Paint?
Is it rated??????
deleted
Just kidding
i m _S1MPLE_ :\
Rating is like life . Full of up and down down down down down down down .
are you saying this !!! hardly your rating had a downfall man ....but still i agree with you
I think what I have said may come true. :(
Thank you for this announcement on the glorious Fourth of July. I hope my rating goes to 1776 after contest. For America, her allies, and my constitutional right to shitpost. #AMERICANUMBERONE
Unimaginably, they've mentioned Mike.
One more task and this would have been a beautiful regular round with two divisions.
+1 if you want problems to be short and concise instead of long confusing stories...
How about +2 ?
UPD: By the way, what is so wrong with wanting the problems to be short and precise?
unfortunately it canot stop...
The same thing that's wrong with "is it rated"
kun? Another Mathforces round?
How are testers related to the inner contents of the round?
However, it happened...
I hope codeforces work properly today.
Where is KAN for help to prepare the round.
I smell math for this round either
Be careful — you've got 3 of 5 the most popular jokes in one picture. It will be very difficult not to be hidden.
What to do if you don't meet Wael.Al.Jamal in comments and can't downvote all his comments for reaching the new record (-200 contribution)? EXACTLY! You must help Codeforces community to reach another record — the greatest total number of downvotes under the announcement in the history.
arsijo, Is she the same Sonya from Codeforces Round #371 ..??
Again my rating will decrease.........Why there is no rank name under newbie....?
you have chosen wrong handle maybe :)
I've noticed in the previous two Div 3 only rounds the registrations exceeded 8000 at both times and Div 2 contests don't often get that many participants. I wonder why
Rating is like life . Full of up and down down down down down down down .
see my graph
you are everywhere
Problems are loading very slow. Is it just me?
#define int long long
Are you serious?
Welcome to CF
Congratulations to Codeforces with 40,000,000 sent solutions!
Am I the only one who is not able to submit the solution for problem C
But you LGM! We believe in you!
A very uneven contest. Problem C has 2k+ solutions, and problem D has less than 100. Codeforces needs to work on the aspect of balancing the problems evenly.
A easy B easy C easy then suddenly D hard? Nice diff spread
very confusing statement
Strongly agree. I had hard time understanding pA statement. Also forgot to set array value 0 in pC, cost me around half hour and 2 WA :(
Attempting Problem D after successfully submitting Problem C:
Well, I had no idea for D but I solved E(hopefully)(edit: RE 12) :P
Простите, но это было очень скучно, т.к. проблемы D и E остановили почти всех, а A B C были достаточно простые.
Was it just a bad day for me or there was seriously something weird with problem A? -_-
No, you are not alone
The way problem was framed: For the given test case 2:
The answer should have been:
7i.e.2, 6, 13, 14, 15, 16 and 21If you're gonna count 14 and 15 why not count 22,23,24... as well?
"She wants to make the minimum distance from this hotel to all others to be equal to d".
14 and 15 are not valid cities, because the minimum distance to an hotel is 3 for both of them, and in that test d = 2.
When a hotel is located at
13, how is the distance equal to d for all the other hotels apart from hotel at11"The minimum distance from this hotel to all the others" = "The minimum of all the distances to the others hotels" = "The distance between this hotel and the nearest".
Actually, if you want to "make the minimum distance from this hotel to all others to be equal to d", then you are saying that for each hotel different from the yet-to-add hotel, you want the distance to be equal to d.
It's obvious in this problem that this wasn't the intended meaning (actually, it wasn't obvious to me, I had to look at the sample tests), but if the problem involved a graph, for example, then I would never have thought that:
"The minimum distance from this hotel to all the others" = "The minimum of all the distances to the others hotels"
is true.
"the minimum distance from this hotel to all others".
The minimum distance to an hotel if you are in city 13 is 2 (hotel 11). Please notice that the problem ask for the minimum distance to any other hotel, not all the distances.
Wow, D was pretty tough for me...Can anyone provide a solution? My only thought was to simulate different possibilities with BFS and use heuristics to lower the search space, but I still timed out.
How to solve B? I didn't get any idea
Just print an alternating 01 array. (Convince yourself why this is true)
Kill me :')
We all have felt the same in some contest or the other.
I had thought of this solution but instead of proving it correct I thought it is too stupid solution which will not pass even the pretest.
I also thought it can't be right, but since I didn't have any other ideas, I figured the risk of WA will be worth it on the off chance that it's correct.
Why not? Let x be no. of roses then we have to maximize x(n-x) = nx — x^2. Differentiate and get x = n/2. For segment of even length if we place alternating 01 we will get equal no. Of both the flowers. For odd length segment we will get (n+1)/2 and (n-1)/2 which will maximize the product.
i thought the same way
I thought it can't be right because that solution is too easy for Div2B.
I just printed a n length alternate string and it passed the pretest (01010101010...till n). I hope it passes the system tests.
You need print "01" alternativey. Now why this is the right way. Supposefor some person has start l and end at r. Now what's the max possible answer. suppose you have R roses and L lily. Now R+L=(r-l+1) And we wish to maximise R*L. Standard. Very Standard. It will be maximum when R is as closed to L as possible. Which will be always satisfied by our answer of printing "01". As in every segment abs(R-L)<=1. So this answer is correct.
What was Pretest 4 in D?
I think it will be either for n=1 or m=1 type of test case. Or where no of occurrence of each digit always produce -1.
How could so many people solve B? Is there anything I didn't keep in mind?
Also, F seems to based on sqrt-decomposition approach, doesn't it?
answer B:"01010101010101..."
Nooooo
But what if
Input
2 1
1 2
The maximum beauty will be 1 with
01or10. If two flowers are of the same type, you'll get the beauty of 0 (since one type got no flowers).I want to die :(
I thought in "010101..." but did not notice what you said so I discarded that solution >_< .
Chill bro I couldn't even think of it for entire two hours :D
Goodbye ratings anyway :D
01 is still optimal as it gives 1 as ans. others give 0.
Approach and Proof For B a/c to me. You need print "01" alternativey. Now why this is the right way. Supposefor some person has start l and end at r. Now what's the max possible answer. suppose you have R roses and L lily. Now R+L=(r-l+1) And we wish to maximise R*L. Standard. Very Standard. It will be maximum when R is as closed to L as possible. Which will be always satisfied by our answer of printing "01". As in every segment abs(R-L)<=1. So this answer is correct.
B=1010101
F: Nope segtree on bits I think
Can you express your ideas?
I tried with sqrt but got completely stuck in the 1st query.
for B, you just have to print alternative 0 and 1.
In B it is always optimal to print alternating ones and zeroes
Its solution is constructive. You just need to output alternate 1s and 0s as they will maximize the product for all segments given a fixed sum.
What????????
Why didn't I even think of that in B? :<
Thanks anyway guys ;) kukyo BeardAspirant noobied samyakjain Renaats JustInCase adityakumar3811
It happened with me too :(
I spend all my life to implement a f**king super algorithm ...
Lol. I actually got no idea and decided to try F instead. Worst decision I've ever made :D
how to solve C
For every unique element from left to right, add the number of unique elements to the right of it to the ans.
this will be O(n^2). That is why didn't even try this approach
You can do this in O(nlogn)... Initially traverse from right to left keeping track of unique elements using set. And then traverse from left to right, (using a new set) for every unique element just add the value of the number of unique elements to right of it.
can be done in O(n) http://codeforces.net/contest/1004/submission/40006342
I believe you can keep two vectors, one for the positions of the leftmost occurence of a number, and one for the right. You can iterate over the first vector and sum up all the ones in the second vector that are bigger than it (meaning no intersection) using binary search or c++ upper bound.
for each position find the number of distinct numbers in the range [position+1, end of arr]
3
1 1 2
According to you answer would be 3 but it will be 2, right?
It is quite easy with sets in c++.
For this contest will have to say don't think too much.
What could be testcase 4 of D ?
Does the solution to E involve finding the Centroid of the tree? (Centroid in terms of the distance, not in terms of the number of nodes)
You mean center of the tree? Yes.
Take a diameter. And check each k consecutive on it?
I placed the center on the path, then binary searched on the answer. For each such value I accounted for the nodes which needed to be in the path, and tested whether the path was valid (one segment of length at most k). I'm pretty sure that binary search was unnecessary, however.
could you please tell me proof or how you came up with your idea of E .. that is sliding a window of size k on the longest path of tree..thanks
For me,it seemed we can always move towards a global maxima taking suboptimal path and greedily making it better (But no guarantees of it being true.Will be happy if someone can confirm it.)
Then I proved that answer will exist on diameter by exchange argument.
Then sliding window is kind of searching complete space.
Yes, the center. Thanks.
So, after finding the center, do we maintain a priority queue with ascending order of sums of distances the children of a node have to travel to the parent of the node(the parent will have an ice cream store for sure)?
In the PQ, we first insert the neighbours of the center, then take one node out of the PQ, set an ice cream store there, then insert it's neighbours, and keep doing this until we don't have any stores left to set up?
I believe that should work, as long as you are checking that the stores form a valid segment at every point in time.
Got it, thanks! :)
Too long statements. Surprised with the problem B.
I had one interesting idea for E which I want to share, I am really curious will it pass all testcases. I think I have a little strange background of my solution, so it possible I have bug. Anyway here is idea with randomisation:
In case we know one node in the result path, we will always go in subtree which contains furthest node from that node ( if we have two ends, we will choose node with 'better; subtree...)
Now if k < const and diametaroftree < const we can explore paths from each node and calculate best result. Otherwise we can choose const random nodes, investigate them in O(k) and choose best result. For const near 1000 , probability for mistake should be really small.
What was the solution for F?
How did you solve Div 2 D ?
Hint: Given n and m, if you know the maximum element in the list and the smallest element x whose frequency is not 4*x, you can determine the position of zero in the matrix(if solution exists for given n and m).
I have an interesting idea. let mx=highest value of the elements. if it is odd than 0 will be in (mx/2+1,mx/2+2) position if it is even than 0 will be in (mx/2,mx/2) position now try to build the matrix with 0 in that position for all divisors of n. example: 18 2 2 3 2 4 3 3 3 0 2 4 2 1 3 2 1 1 1 mx=4 0 will be in (2,2) divisors of 18 are 1,2,3,6,9,18 so we will try to build the matrix where m*n= (1*18) /(2*9)/ (3*6)/(18*1)/(9*2)/(6*3) and position of 0 is (2,2) (I think this solution will work but not sure. just sharing my idea with you. :D Let me know if you find anything wrong in this idea)
if frequency of maximum element is 3 it will fail 0 1 1 1 2 2 3 3 3
It can't be 3. There is no solution for your test case.
how ?
Assume zero appears on the bottom right quadrant, maximum element appears on the top-left corner and element x-1 lies to the extreme right of zero. (You can flip any other solution to get this configuration).
Is there a reasonably short way to solve D? My idea was to watch the growth of the sequence of counts of different numbers, predicting what the next number should be assuming that the corresponding rhombus does not hit the edge of the matrix. Then, if the prediction turns out to be wrong (the actual count is lower than the expected one), consider the different cases of edge positions. But those predictions and subsequent pattern matching have tons of corner cases and are ridiculously tedious to implement.
I actually used the same thing. Yes it was hard to implement. But not as many edge cases as you might think. n and m can be interchange. if i,j is center then m-i,n-j being center is also a solution etc. So quite a few cases get handled together.
In problem D,if matrix of i x j gives me correct ans,then,I think j x i will give me correct ans too.Correct me if I am wrong?
Ya that was actually what I meant when I said n and m can be interchanged.
I wasn't sure about TL but it passed. My solution was to stop once you hit first edge, let's call that distance
s.Now let's look at the biggest number
mand iterate over all possible splitsm = a + b. Then one edge of rectangle isa+s+1, and if that dividesnthere's only one possible position for0. Now let's check that it's correct with bruteforce approach.For those who passed D with >1000ms. Try test n = 840, m = 858, cx = random(1, n), cy = random(1, m).
what the hell is testcase 4 in D..!!Can't debug..
Чето в последнее время див 3 это див 2, див 2 это див 1, а див 1 это тоже див 1, но с еще более плохими задачами.
Согласен. С появлением div. 3 задачи div. 2 стали сложнее. Очень даже.
div3 никак не влияет на div2, сомневаюсь, что это два явления связаны.
My ratings to me after not solving B. :(
Can we solve E by choosing K consecutive segment of nodes in the largest path of tree? Like sliding a window of size K
I think so. Though I used binary search after finding the longest path, not sliding a window.
how did you write check function of bs?
Yes. https://codeforces.net/contest/1004/submission/40007113
could you please tell me the proof for this idea?
Suppose that you don't choose the K nodes in the maximum weighted path, it means that at a particular node you chose a path that was smaller than the largest path. Now this means that the farthest distance of the node with ice cream will increase. The best way to visualise this is by arranging the tree structure such that it looks like the most weighted path is a straight line and all other sub paths are hanging from each of the nodes in the max weighted path.
Did anyone actually solve problem B with a solution different from "01010101..."? That would be hilarious.
not entirely different but I sorted ranges based on l and r. Then for each ranges from l to r put alternation 0/1 based ans[l].
feeling stupid now
http://codeforces.net/contest/1004/submission/40000339
Only difference i recognize that your code writes 101010... instead of 010101...
Unhackable round ! xd
Though that +1 hack really saved my rating... it gave me like 200 ranks.
Lucky you. Some people did not have wrong solutions in their room.
i hacked +1.
D was hackable :D
A quick system test considering the number of participants and even quicker ratings update.
Why is this code getting TLE in test 52 in problem E? 40007267
Imagine star graph (one vertex connected to other n — 1 vertices). For example lets consider center vertex numbered 1. You will call function llenaDist(1, p) n — 1 times. And function llenaDist(1, p) working in O(n). So complexity is O(n2)
Thanks! Do you know how can i calculate this distances more efficiently?
Make tree rooted, do 2 dfs. First calculating dp bottom-up, second calculating it top-down. See submission for details Fuctions called dfs1 and dfs2
legendary speed system test and rating update
elijahqi was 4th in standings. After system tests, he is not in the rankings at all. what happened here?
maybe cheat !
Why are long and int of the same limits on the compiler used in Codeforces? In other websites long has wider range than int and equal range as that of long long.
Which platform are you talking about? I've never seen that. In every new compiler I've seen long long is larger and int and long have same size.
https://www.codechef.com/ide This is not a competitive coding platform: https://ide.geeksforgeeks.org/
Why the answer of problem E for the second sample is 7 and not 6?
If the shops are in : 3, 4, 5.
The minimum distance of node i to any shop is:
Junction 1: Shop 4 — Minimum distance is 6
Junction 2: Shop 3 — Minimum distance is 6
Junction 3: It is a shop — Minimum distance is 0
Junction 4: It is a shop — Minimum distance is 0
Junction 5: It is a shop — Minimum distance is 0
Junction 6: Shop 4 — Minimum distance is 6
Junction 7: Shop 5 — Minimum distance is 2
Junction 8: Shop 3 — Minimum distance is 1
Junction 9: Shop 4 — Minimum distance is 6
Junction 10: Shop 4 — Minimum distance 5
In this way, the answer is 6, isn't it? What is wrong in this solution?
shops should form a simple path.
Thanks!!
Problem B was kind of a one-shot problem. You need to wait till you realise the answer is alternating zeros and ones.
easy problems B, C
how to solve problem D?
Can anyone explain me, why one submission gets AC, and other TL4, they seem to have near the same complexity and idea?
AC code — http://codeforces.net/contest/1004/submission/40000703 My code(TL) — http://codeforces.net/contest/1004/submission/40004156
I think there was a mistake in my source code for problem A. But my solution got accepted. Here is the link to my solution: http://codeforces.net/contest/1004/submission/40001844 If i input 4 as hotel number and 2 as difference and 1 2 4 and 40 as the hotel locations,should there not be all locations in between 6 and 38 and the additional 2 locations for two ends? i think my solution did not cover this part. I hope it can be checked and clarified. Thanks
The problem description created this confusion to me also as it said the minimum distance must be d.But when I asked about the same they replied "The distance from new point to the nearest existing point should be exactly d."I wasted a lot of time in this :(.
However, it works because when you compare c[n] — c[n-1] (j = 0, 1, ... n-1) and d * 2, c[n]-c[n-1] is bigger, because c[n] can be everything, something like 1006547729 for example.
test9 on problemE is so danteng
I'm surprised rating change was given in just about one hour. Thanks to the Codeforces team for reducing the waiting time.
I'm surprised the rating change was shown in just about one hour after contest end. Thank you to the Codeforces team for reducing the waiting time. Hope to see this improvement in future contests!
When you skip B because you have no idea of the right greedy strategy, spend 1h30 on D and at the 1h55 mark understand what B was really asking for...
i get the idea in 1 min
I count two minutes (three minus one minute for reading). Maybe this is the reason of downvoting...
I'm not gonna say this contest is bad because I'm always grateful when there is a new contest, but the problems' difficulty distribution makes no sense: A, B, and C were all the same difficulty (actually A is probably the hardest). It doesn't even test programming skill, just write fast and pray there aren't any bugs and you get +100 rating.
Especially with a troll problem like B. :/
how to solve A?
Just open the list "standings", click on anyone's solution and be happy (you'll very soon find the clear to you solution).
Problem F is very similar to COCI 2017/18 Round 2, last problem (link to the codeforces blog). The difference is that that there we want the number of ranges with gcd(A[L;R]) = 1, but the same idea will pass (you can look at the comments).
So if anyone doesn't want to wait the editorial, he can check it out.
Link to my code for that problem.
Am I the only one who thought about Codeforces Round 439 (Div. 2) and people, who solved B and C but did't solve A which was even more funny than today's B?
I was stuck on A as well. I was really sad that I couldn't even solve A in a contest was thinking of leaving the contest but then saw B and faith were restored. I solved A with a time penalty of 110 (around) points and 150 points attempt penalty.
Your crafting.oj.uz ratings are updated!
I think pC should replace pA and there should be another pC which reduces the gap between pC and pD. I don't know why contestant are calling pB troll problem because it was nice simple problem. I don't like pA and pC(as C). Also this was my first contest and I learned that "Implementation is a part of competition and it should be a part of preparation".
B was a troll problem because of the answer which wasn't any way dependent on input. There was no need of input of l,r segments, the only n was sufficient to generate the pattern. Even if you didn't know that answer should be alternate 0 and 1, you could prove it mathematically to maximize to the fact that in any segment (even number of elements), there should be the equal number of two type of roses for the function to yield the maximum result.
It's a competition. I bet that many people have wasted time thinking about l & r. Also it requires finding maximum value attained by downward parabola which I think is okay for Div2 pB .
The problem was tricky. Very very simple differential calculus is required for mathematical proof. After thinking of approach, the main time wasted was checking under various test cases if approach really is correct or not.
Why check for various test case if you have proof
Could not believe that the answer could be this simple.
I was able to solve problems A and B but not the problem C. I know it is quite easy. But I somehow couldn't explain myself the logic in my mind. All I could think was of a prefix array will the ith index in it denoting the no. of the unique elements to the left of it in the array. Can someone explain the solution to C? It can be short too, I kind of have a rough idea after looking at the codes of other participants who used sets and maps for the same.
You probably have guessed it right. I first created a prefix array which gives me the unique elements to the right of an index i. Then we iterated from i=0 to i=n-1, and for each unique element I added the prefix sum from it. Here's the pseudo:
i too figured it but unable to implement it .......it sucks if this happens
I face a problem with Pypy on CF.
I got RE with exit code is 13131313 if I import random library. The same code is AC with python
http://codeforces.net/contest/1004/submission/40007659 — AC with pypy3. http://codeforces.net/contest/1004/submission/40007677 — RE with pypy3 because of import random. Exit code is 13131313 http://codeforces.net/contest/1004/submission/40018157 — AC with python3, (has import random also).
Any help?
After 2 years of python I forgot that I have to use long long instead of long. :-D good bye good rating.
I suppose I have a relatively easy way to solve D. First of all, let d be the distance from zero to the nearest side of the rectangle. Then we can find it as following: numbers 1, 2,... d must occur exactly 4, 8,... 4*d times, while d+ 1 will occur less then 4*(d+1)
Next, notice that the max numbers is the distance to the furthest corner. Now check all pairs (m, n) such that mn=area. Notice that we can find position of zero By distance from nearest rectangle side and distance from furthest corner. Now simply check if that position is ok (I had a special function for checking if specific m, n, x, y were ok. That's it
Editorials are not here....
Here it is. editorial
thanks..
can anyone help me with problem C
guys can anyone help me with problem C because in that problem i m getting a TLE but still after going through the editorial also i m unable to figure it out...........PLz help
Iterate from last element. Keep track of number of different elements before current element and also make sure not to count pairs (*,y) multiple times you can do it having a boolean array
The complexity of your solution is (1e5*1e5).It will give you TLE.
can u let me know a simple way of doing that becoz i m new so dont know much tricks to over come these issues
Почему в Е нельзя взять позицию, с минимум из максимумов дистанций, затем жадно брать вершину с наибольшей оставшейся дистанцией (k-1) раз?
Разобрался, это решение ищет ответ с не простым путем.
101010101 = LOLOLOLOL
Editorial here...
разбора не будет?
Can anyone tell me what is wrong with this submission? http://codeforces.net/contest/1004/submission/40022548