Hello! Codeforces Round 756 (Div. 3) will start at Nov/25/2021 17:35 (Moscow time). You will be offered 7-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.
The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.
You will be given 7-8 problems and 2 hours and 15 minutes to solve them.
Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:
- take part in at least five rated rounds (and solve at least one problem in each of them),
- do not have a point of 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University teams: MikeMirzayanov, MisterGu, myav, Vladosiya, Aris, senjougaharin and me Gol_D.
Also many thanks to God_Of_Code, oversolver, FlakeLCR, Igorjan94, Jester, KHiMAeRA, KerakTelor, Loolo, MatheusMonteiro, Resende, teraqqq, dedlocc, doreshnikov, kbats183, kocko, vsinitsynav and pashka for testing the contest and valuable feedback.
Good luck!
UPD: Editorial
I really want the round to go well. I have gathered a team of ITMO students so that they can quickly prepare such rounds. For example, for this round we had to get together twice for several hours: to approve a set of problems, and I also showed and told all the details of preparation. The guys put in a lot of effort. Thanks to them!
I am sometimes asked why the circle of Div3 contributors is so narrow. The fact is, for such rounds we do not have coordinators: the skills of preparing problems are very important. You need to take into account a large number of little things and accustom yourself to be careful when preparing them. The easiest way for me to do this is with a permanent team. I supervise the preparation several times, the writers themselves encounter difficulties and as a result, they already know how and what to do. In such easy problems, quality and uniformity of preparation are more important. Then you can count on a regular schedule of such rounds.
That's so cool, good luck to them!
But I miss vovuh's Contests, Why did he stop preparing for the Div3 Contests?
I really liked this division 3 (I did it virtually, since I couldn't attend the real thing). Right mix of implementation and observation AND a reasonable solve count for each problem. Some non-trivial data structures, like sparse table/segment tree, and some really satisfying problems! I hope to see more rounds like this in the future :D
Can someone help me,please https://codeforces.net/contest/1611/submission/137113575
Just one contest in the weekend tbh :/
Really?
26th Nov: Codeforces Div 2 && Codechef FizzBuzz (Rated for Div 2 & Div 3)
27th Nov: Codechef Nov Lunchtime && ATcoder Beginner Contest
28th Nov: Codeforces Deltix Round && AtCoder Regular Contest
29th Nov: Codechef C.O.D.E.R.S (Rated for Div 2 & Div 3)
:) It's raining contests! Yay!
I guess he is talking personally.
Friday isn't weekend and i only like codeforces so I'm still waiting
Add leetcode contest also
Can't wait to participate! This is the first contest that I'll be able to participate in since these are usually at 9:30 AM for me. Good luck everyone.
As we all know, div3 is more difficult than div2
This aged well
I love div 3 very very very much♥♥
I'll ask you about that after the contest :))
Hope everyone will have good contest.
Good luck to everyone!
Hope I will get +100 in this contest.
hope i able to solve more than four question
Hope your hope turns true
thaks for this great contest!!
problem F should be before D, maybe even C
C shouldn't had been there at all ;)
I don't think so, problem D was very simple in my view
Problem D and E It's all about trees. I don't have any ideas ,It's sad
You could actually do D without trees too! For ex., I created a map m1 with the keys as vertices and the values as their parents. I then created another map m2 with the given permutation, with the keys as the vertices given in the permutation and the values as the summation of edge weights going from the root to that vertex, started from 0, and incremented the value by 1 for each subsequent vertex. I then just used m2[i] — m2[m1[i]] to get the weight of the edge connecting the ith vertex to its parent, m1[i]. If this was negative at any point, I returned -1, otherwise I printed out these weights. My only peeve with the contest was the placing of D, I feel that F should've come before it as it was easier.
Hmm I personally thought that D was much easier than F. This kind of thing is quite subjective, though.
Nice problemset. Although, not a good idea to put 3 Tree problems in a Div3 imo. Also, can we solve E2 without binary lifting?
I solved E2 using a modification from my E1 solution, which used 2 BFS. The first BFS would find the minimum distance of each node from one of Vlad's friends and store the value in an array. The second BFS would be from room 1. This BFS finds a room with only one corridor. For every node that the BFS visits, it checks whether there is vlad's friend that could arrive at the node faster than vlad. If vlad's friend can't get to the node quicker than vlad, then continue the BFS, else stop the BFS (this is the E1 solution).
For the E2 solution, modify the final BFS. If there is an instance where there is a node where the BFS stops (vlad's friend can get there quicker than vlad), then we can observe that one of vlad's friends has to stop him, so we can observe that one of vlad's friends has to stop him at that node. So, add 1 to the result (the minimum amount of friends required to stop vlad) by 1 (you can also use the answer to the first problem to check whether it is impossible to stop vlad).
But how does this find the min number of friends? I mean, it is not so difficult to find which friends can stop vlad at any given vertex. But still how can we know what is the minimum set of friends covering all leafs?
Since this is a BFS, the BFS will stop at the closest node to node 1 where his friend can stop him. Since this is a tree, stopping at a smaller distance to the root will minimize the different nodes where vlad's friends need to stop him at.
Through this observation, we can try to find the closest node to the room. We can find this using the aforementioned BFS from the root.
Ah, i see. At each vertex where vlad would be catched, there is exactly one friend able to catch him. And that friend cannot catch him anywhere else. Clever.
Exactly same with my solution. you don't need to return which friend should stay, just the number.
I did E1, E2 with Euler tour.it was the first that come to my mind. I can explain that solution if someone is interested in it.
Could you explain it, please?
E1:lets do an Euler tour and some structure for asking minimum in the segment. Let's do a dfs. if we will reach leaf(and it's not bad) then we will print YES otherwise NO. if we are currently at some node v and it's bad then we don't go deeper. How to check if the node vis bad or not? let's look at the depth of vertex v, it's equal to the length of the path from the root to v. then we are interested in the shortest path to all of his friends that are in the subtree of v.We can find that by asking for a minimum depth in our structure. However, there can be some vertex that is higher than v and has a shorter path than any friend from subtree of v. However, it's turn out that if we have such vertex then we will never go to v. E2 it's really easy to modify E1.just when we are at bad vertex do ans++. That's all. Have you understood it? I can also tell u about an Euler tour if u don't know what is it.
А, кстати, ты ведь с Украины... Под какой-нибудь структурой для поиска минимума на отрезке ты имеешь в виду ДО? И каким всё же образом ты применяешь Эйлеровы пути?(Я знаю, что это, но как тут применить, до меня не доходит...)
yes, I used a segment tree as such structure. with the Euler tour we can get minimum on a subtree because if we will write down all the vertices in the order of Euler traversal then each subtree will form an uninterrupted segment. E1 code 136893182 E2 code 136893182
Ok, I got it.Thanks!
During this round i realised that cp is not for me ;)
This round was a little harder than usual Div 3s, don't get disheartened, keep persisting, if you enjoy CP
Really enjoyed problem D, I like problems of this kind. thanks
can you explain your approach to problem D as I'm very confused as to how to set the distance of the edges...!
[UPD: Solved} the biggest hint for me was to use the permutation p itself. And No dfs is not required as you can just iterate through the permutation and assign the weights in increasing order and check while assigning if the sum of weights from parent to that node(say total_weight of that node) is equal to the total_weight of the previous element. if equal then just assign the weight accordingly for the condition given in the question to be true.
Can anyone tell me why my Solution of D is getting WA 1 ?? My Solution for D
Thank you for the help !
You can see the failing test case when you scroll to the bottom of the submission page and click on see test details.
I think that the authors of this contest need to be reminded that this is a Div 3 round, not a Div 2 round. Div 3 should be ideal for beginners/newbies, this round certainly wasn't.
No, the problems were not so hard as in div2 contests. Anyway problem B was much easier than in div2 contests
I can solve 7 problems during the contest and G just after the contest (so disappointed to miss it in the contest). For Div.2, usually 4 or 5.
Im. shocked. Why I got WA in B?
https://codeforces.net/contest/1611/submission/136901877
https://codeforces.net/contest/1611/submission/136919221
I can't totally find out fault in my codes
try this:
3 5
A team needs at least one programmer. Hence the number of teams can be at most a. A team needs at least one mathematician. Hence the number of teams can be at most b. A team needs at least four members. Hence the number of team can be at most = total people / 4 = (a + b)/4.
So finally the number of teams = min of above three = min({a, b, (a + b)/4})
How to train math problems like B?
I'm disgusted with the codeforces recently. My performance continues to increase in atcoder, but codeforces ruins the round depending on the problem.
Usually you can use binary search instead of formula in this type of tasks. Problem B of this contest is not an exception.
Universal method xD (binary search: 136850518)
so how "at most" is always achievable ?
a, and b is easy to achieve, you can prove (a + b) / 4 by contradiction. if (a + b) / 4 >= a, and t = a + b — k * (a + b) / 4, t can't greater than 3.
Good day to die
For C, I just simulated the described process on the reverse of the input array and printed that as the answer. Can someone explain why this works?
It was just to reverse the given array.
Because element with max value will always be either on first or last position(if ans is not -1), so comparing any other element with it will lead to insertion of that element. Try writing few test cases, u will get it!
Is this on the right track for G? If so any hints for what I'm missing?
Split points into two grids by parity, i.e, (i + j) % 2 and solve them independently.
Now in each grid, depending on the row and parity we can either go down / left or down / right (some of these moves may be invalid at the boundary col).
While there are candies remaining in the grid, in each pass our priority is to remove points from the left most columns possible.
So, we take the first remaining candy for each non-empty row and sort them by column.
Now we process these values in sorted order and try to see can we insert them into the current path, if so we do.
Checking if they can be inserted can be checked in O(log n) time by storing a set of {row, col} of the points we have taken, binary searching for the points in the currently taken path before and after the insert point (if they exist) and check if this newly added point is reachable from them.
Reachability can be calculated in O(1) time by calculating the max columns left / right we can move in this row range (number of rows / 2 + 0 / 1 depending on starting row parity).
This passes samples but gets WA2 so I suspect I'm still missing something.
Submission in case that helps — 136926073
exactly same with my solution. just check for implementation details.
Thanks, probably an implementation mistake somewhere since I finished right at the end.
C is trash.
you are
C is observation, and like allways very disapointing if not found.
The difference between the difficulty level of C and D made it another speedforces round
yeah I did E1 before D
Enjoyed! I dunno if it was just this contest, but every problem kept me on my toes.
My statue on problem A and B today :
In my defense Bustinza was just trynna hug me dude
E2 approach?
I solved E2 using a modification from my E1 solution, which used 2 BFS. The first BFS would find the minimum distance of each node from one of Vlad's friends and store the value in an array. The second BFS would be from room 1. This BFS finds a room with only one corridor. For every node that the BFS visits, it checks whether there is vlad's friend that could arrive at the node faster than vlad. If vlad's friend can't get to the node quicker than vlad, then continue the BFS, else stop the BFS (this is the E1 solution).
For the E2 solution, modify the final BFS. If there is an instance where there is a node where the BFS stops (vlad's friend can get there quicker than vlad), then we can observe that one of vlad's friends has to stop him, so we can observe that one of vlad's friends has to stop him at that node. So, add 1 to the result (the minimum amount of friends required to stop vlad) by 1 (you can also use the answer to the first problem to check whether it is impossible to stop vlad).
for each node, keep track of the minimum distance among all friends in the current subtree to reach this node in
minFriendDist[node]
.then do DFS from the root. as soon as
distFromRoot >= minFriendDist[node]
, incrementans
by1
and return (stop exploring)Lets make some observations:
Clearly if a friend exists at some node $$$x$$$, any leaf in the subtree of $$$x$$$ is unreachable.
If there exists no friend in the subtree of $$$x$$$, if Ivan can reach $$$x$$$ without getting caught, he has effectively escaped.
Ivan always moves down the tree and so the time he takes to reach a node is its depth in the tree.
His friends always stay in place or move up the tree to intercept him (if he's below them he has escaped from them).
So with these, we just need to check for each node $$$x$$$, can some friend in the subtree of $$$x$$$ reach $$$x$$$ before Ivan can. If so he can protect this subtree alone and the answer for this subtree is $$$1$$$. Otherwise the subtrees of each of the children of $$$x$$$ with need to be protected separately and the answer is the sum of the answers for the child nodes.
To check if any friend can protect this node $$$x$$$ we just need to store the closest friend in the subtree and check if it is at most the depth of the node.
Code — 136900309
Do you know how to solve E2, if the given graph was not a tree (i.e., it is allowed to contain cycles)?
I thought of this because for my solution of E1 proof of correctness, most of the time you can just view the graph as a graph, so when trying to solve E2, I didn't think hard enough about using the tree property.
Noooo. I was 10 seconds away from submitting F :(:(:(
I think the risk/reward of all-problems-same-score rounds is taking a turn for the worse...
Today's B was 1538G - Gift Set in a past life... at least I'm consistent in my failure :P
How to solve B?
I did binary search for answer, but looks like it was an overkill.
Cool problems! Excited to see more contests from these new writers!
Enjoyed very much, Every Problem from B was a challenge in itself. Perfect Div.3 Round. Really loved C and D.
How do we do E1?
My approach was to 1. make a tree with 'par' and 'lev' vectors to store the immediate parent of each vertex and the level it is in — 1 is root note/vertex. 2. now, for each of the leaf nodes, calc their distance from the root node 1 (D), and from each node that friends are on (d1, d2, ... dk — for k friends). 3. if D < d1, d2, d3 ... dk — then I should be able to reach a leaf node from node 1 before a friend can intercept me. 4. to calculate d1, d2, ... dk, I tried to use LCA But i kept getting a TLE? Is this the right idea/algo to use?
My solution was using BFS
You only need 2 BFS runs: From a) Vlad and b) from your friends. Then just check all leaves (inDegree==1 && not root) if at any leave there is distanceVlad < distanceFriends -> Vlad wins.
O(2*(V+E)) = O(2*(V+V)) = O(V)
multi source BFS for finding out minimum distance of friends from each node. And then one DFS.
136904073
No, actually 2 bfs is enough - one for min dis from all friends - one for min dis from root node 1
what you did is called multi-source bfs
i want you to hack my b and c as i dont feel confident enough that they are correct.thanks
RIP puppy_bhai
LMAO
How to do F without using segment trees?
I used prefix sums and 2 pointers.
I did sliding window
why does sliding window works here?
dp, i think
While I got AC on the problem using sparse table, I suspect we can instead do this:
Process the subarrays in reverse order of their starting points ($$$n$$$ to $$$1$$$) and maintain a strictly decreasing deque(*) (or reversed vector since we only insert at the front) of the values in this range.
Now we can just binary search on this deque to find the first bad position rather than using some RMQ structure.
(*) — By this I mean we will store a strictly decreasing deque along with index which decreases at the first possible index. Like suppose for the array $$$[1, 3, -1, 0, 6, 4, -1, 3, -7]$$$, where (x, y) represents a tuple of (value, index):
At $$$i = 9$$$, we will have $$$[(-7, 9)]$$$
At $$$i = 8$$$, we will have $$$[(3, 8), (-7, 9)]$$$
At $$$i = 7$$$, we will have $$$[(-1, 7), (-7, 9)]$$$
At $$$i = 6$$$, we will have $$$[(4, 6), (-1, 7) (-7, 9)]$$$
At $$$i = 5$$$, we will have $$$[(6, 5), (4, 6), (-1, 7) (-7, 9)]$$$
At $$$i = 4$$$, we will have $$$[(0, 4), (-1, 7) (-7, 9)]$$$
At $$$i = 3$$$, we will have $$$[(-1, 3), (-7, 9)]$$$
At $$$i = 2$$$, we will have $$$[(3, 2), (-1, 3) (-7, 9)]$$$
At $$$i = 1$$$, we will have $$$[(1, 1), (-1, 3) (-7, 9)]$$$
So clearly in each stage it suffices to just binary search on this deque. As to how we actually maintain this, at position $$$i$$$ we simply pop all elements $$$\geq a_i$$$ from the front of the deque and push $$$(a_i, i)$$$
We can use two pointer, increase right until the subarray becomes bad, increse left until it becomes good again.
Aren't there cases where moving the left part forward will require us to move the right part back? How do we handle this with two pointer?
Well, if there is such a case...then I will get hacked :/
I doubt it would have passed pretests if it didn't work.
I suspect that it doesn't affect the answer since we only want the max, even if for some $$$[l, r]$$$ we don't actually count some $$$[l + 1, r - x]$$$ as good (for some arbitrary x), it won't affect the maximum. If we wanted to count the number of good subarrays this would have failed.
When L increases, R is not monotonic, but when R increases, L is monotonic, so we can use two pointers.
Let's say the current sliding window is $$$[L, R]$$$, we need to move $$$L$$$ immediately when $$$sum(L, R) < -s$$$, so when we need to move $$$L$$$, $$$(L, R-1)$$$ will be a feasible answer.
If somehow when moving $$$L$$$ we need to move $$$R$$$ backward, the corresponding subarray won't be better than $$$(L, R-1)$$$, so I think the cases you mentioned don't exist.
That's my thought, I am not quite sure though. Please correct me if I was wrong.
I implemented the exact idea you mentioned: my submission
I used a prefix sum + monotonic (decreasing) array + binary search
and after reading this thread I found simple sliding window works...
same question from me...
not a good idea to put 3 problems on tree for a div3! also problems are not sorted by difficulty ,, why is that ?
approach to solve D? I was able to solve E1 but got stuck on D.
Observe that the edges must be sorted so that we can build the tree starting at root, then add each vertex by add a child to some vertex in the tree.
Because else there will be a parent with bigger weight than a child, what is not possible.
So just add each vertex to the tree, and give the edge some weight so that the weight of the vertex is max so far.
got it, thanks!
On the topic of edge weights, here is an easy one — since we know that a child's position in a permutation is greater than its parent's we can just make the edge weight the difference in positions.
I didn't pay attention to it until the last 5 minutes, so I coudln't solve it.
But this is what I thought: the permutation has to start with the root or it is impossible. That is because dist(root, root) = 0, so, when sorting, it will always come out first.
Second, for a given vertex v, it has to appear in the permutation in the same order as the simple path from root to v, otherwise it is impossible. Why? since we are adding edge weights, an ancestor will have less edge weight than it, so, when the permutation is sorted, the ancestor must appear first.
If both these conditions are true, then it is sort of easy to assign weights.
This should be the correct observation, as I used similar observations for my solution
I solve F using binary search without calculate the exactly time complexity. Can anyone hack me or tell me the exactly worst time complexity? :) (here is my submission 136915199 )
Hey, Is there any hack penalty in Div.3 contests for those who are in rated range (< 1600)?
But if you hack some guy before you in the standing table, you migth raise one position.
O(n log n) probably, i'm guessing the check function is O(n)?
looks like O(n^2 logn) if all A is positive.
Can you explain your idea?
Just using binary search to find the biggest date which can satisfied.And brute force in checking.
Hacked. Your check function is $$$O(n^2)$$$
https://codeforces.net/contest/1611/hacks/772016
Thank you OleschY
and physics0523 :)
Was the criteria to put D after C just "D is tree related, C is array"? D is much easier than C in my opinion.
Depends on personal preference, obviously. For me C was quite easy as well, as long as you get the observation for C you can probably solve it in less than 2 minutes. It's just an array reversal.
anyway, tree is a data structure and needs knowledge to do DFS.
Funny thing is, you don't need DFS for D. Knowing the permutation and the ancestor is enough. You can just iterate all your nodes.
See here: https://codeforces.net/contest/1611/submission/136934916
This was a nice div 3 contest. Loved it.
Thanks for this round. My best ranking ever...
Can you write the implementation for F and E1 in short if possible ?
Hello, It's my first time participating. I'm Korean and I use a translator to write it down. I have a question. My code number B (wrong answer on test 2) : https://codeforces.net/contest/1611/submission/136932156 I don't understand. testcase 33 29 -> 14? Isn't this answer 15? 2 programmers, 2 mathematicians, 14 teams. 3 programmers, 1 mathematician, 1 team. The remaining number is programmer 2, mathematician 0. Total team 15...?
You failed on 19 11 ->7,you returned 6
The error code refers to the third test case which is
19 programmers and 11 mathematicians .
The answer for this case will be 7
6 teams of 3 programmers and 1 mathematician and 1 team of 1 programmer and 3 mathematicians
how problem's difficulties get determined? because even though problem B was way harder than C , difficulty of B is 800 and C is 1000. I mean the difficulties should be based on how hard the idea of the problem is. (it's just my opinion problem B may has been easier for you than problem C :") . but generally problem's difficulties doesn't make scene T_T )
You can see less participants solved C than B. That’s best proval.
Both there and there are easy ideas, but in my opinion there was a very simple idea for C, but it was difficult to notice it. You can see for how much I decided and for how much C
E1 was almost similar to cses problemset graph problem : Monsters. https://cses.fi/problemset/task/1194
If the CF predictor is right then this was my last Rated Div 3 ;)
Assuming I don't fall again
Subtract 10 points))) It's always
Carrot is better. +25
Can you share the link to this predictor?
https://chrome.google.com/webstore/detail/carrot/gakohpplicjdhhfllilcjpfildodfnnn
Problem C have ruined my contest ! :(
Problem E2 (using python): I get runtime error on testcase with n=20000 k=10000 136941508 Anyone has any idea what the problem might be ?
Python dislikes deep recursion beyond ~1000 calls deep which is probably happening with your recursive dfs. There are some workarounds documented here and there on this site, but I've tended to just do things iteratively (as long as it's not too entirely gnarly to do so).
I used a stack instead and it worked. Thank you!
Here are the video Solutions to problem A-F in case you are interested.
Can you please briefly explain the (segment tree + binary search) solution for F about which you talked in the video? TIA
Let me give you my version.
Firstly we define sum[i] as the prefix sum of a.
If a[l]+……+a[r]+s<0,sum[r]-sum[l-1]+s<0.
sum[r]<sum[l-1]-s.
Then to every l,we can get the nearest r that min(sum[l] to sum[r])<sum[l-1]-s.
r-1 is the last student l can service.
Two pointer may be a better solution than data structure.
For L=1,we move for the farthest R.
Then we just move L and minus it,if we can't get to a further R,we can't get a better solution than L=L-1,just skip it.
If we can,move R check if it is a better solution.
camy solution can anyone tell me why this solution doesn't work?
can anyone explain how to solve problem D?
I thought of an ad-hoc solution. Try to find a solution such that the first element on the permutation has dist 0 from the root, the second dist 1 from the root, the third dist 2, and so on.
Giving an example (same from the problem text)
5 3 1 3 3 1 3 1 2 5 4
You want the dist array to be [ 0, 1, 2, 3, 4 ] so dist(root, 3) = 0, dist(root, 1) == 1, dist(root, 2) == 2, dist(root, 5) == 3, dist(root, 4) == 4.
So, you have to notice one thing: it's impossible to have a node a such that dist(root, a) <= dist(root, father_of_a) since all the edges must have positive value. You need to check this before by seeing if the position of 'a' in the permutation is before the position of 'father_of_a' in the permutation, but there's also another way of doing it that I'm going to talk about below.
So now you know that dist(root, a) > dist(root, father_of_a)
This way you can build a constructive algorithm to find an answer
for the root, you know that dist(root, root) == 0 for the other nodes: dist(root, a) = w(edge from father_of_a to a) + dist(root, father_of_a) so w(edge from father_of_a to a) = dist(root, a) — dist(root, father_of_a)
Since you know the values for the distances (following that method in the beginning), you now know how to calculate w.
This value must be positive, since dist(root, a) > dist(root, father_of_a). If at some point you have a negative value, that's also an indication that finding an answer is impossible.
My solution, for reference: https://codeforces.net/contest/1611/submission/136944858
I know this will be pretty controversial, and though it is uncommon to say things like this about R1000 problems, but C was quite an interesting problem. It had probably been a very long time since I found a sub-1500 problem with an observation that can qualify as an "aha" moment, and this definitely meet the criteria. I guess I just want to say kudos to the problemsetters for coming up with such a nice easy problem.
https://codeforces.net/contest/1611/submission/136953503
I'm TLE(12). Can someone help me see how to optimize it?
about Problem F
I think using “Prefix Sum” ans “Sparse Table” in your check can lead to O(nlogn).
And you can use “Binary search on Segment Tree”,the Binary Search and check is O(nlogn).
But I suggest you to use Two Pointers,it's O(n).
Use dichotomous answers , How to O(n) check ?
By using Prefix Sum and Sparse Table.It's O(n)
I found that using the double pointer algorithm is very clear to solve this problem. It took me only 5 minutes to finish it.
https://codeforces.net/contest/1611/submission/136959303
Yes.I also used double pointers during the contest.It's convinient.
Above all,get the prefix sum of ai.
if a[l]+a[l+1]+……a[r]+s<0 it is sum[r]-sum[l-1]+s<0
=> sum[r]<sum[l-1]-s.
You can use binary search if there is a array up to len
for each l, just check the minimum of s[l~l+len-1] is lower than a[l-1]-s or not. If not ,a[l]~a[l+len-1] is ok.
Let's see your checker. It's up to O(n^2),your time complexity may be wrong.
A good round!
All of the problems are good,but I think I may see the F somewhere else.
(And the difficulty gap between E1 and E2 may be too low.)
Hello MikeMirzayanov,
Some contestant hacked problem A . But inside hacked solution code I found out that they intentionally kept a test case written inside the solution so that the solution can be hacked. It seems unethical.
These are the solution https://codeforces.net/contest/1611/submission/136954440 https://codeforces.net/contest/1611/submission/136948337 https://codeforces.net/contest/1611/submission/136939066
It was one of the best divs 3!
Yeah Nice and interesting problems :).
in problem E1 I used the following approach
1.Apply BFS from node 1 and calculate distance of each leaf node form node 1.
2.Apply multisource BFS from all the friend nodes, and calculate distance of leaf nodes
Please tell if there is anything wrong with the above approach.
Thanks in advance ^-^
Can someone tell me what on earth was these hacks???
Hack #772495
Hack #772489
Hack #772484
Hack #772482
Looks like an intentional hack. Although I don't understand why would someone do so
It might be possible that it his fake accounts and he/she is submitting just so that he can get hack points
Another intentional one 136921479
Can someone talk about how to solve F using binary search on Segment Trees? It'll be a big help thank you!
Take prefix sum array(lets name it dp) and build a segment tree for range minimum queries. Suppose you need to check if the segment from L to R is good, then all you need is to check if (s+the minimum inside that subsegment) — dp[L-1] is >= 0. Binary search from each index for max length good subsegment to maximize the answer.
Here's my submission : https://codeforces.net/contest/1611/submission/136905894
Thank you so much!
Why the ratings have not been updated yet?
Problemset was great. But I did feel that there were harder concepts (not problems) for a div.3 round.
I tried a DP implementation for Problem F which passed the first pretest, but gave WA verdict on the subsequent ones. Can anyone please help me out in finding what is wrong in the logic?
My submission: 136929173
Where are the ratings?
Help! why am getting WA for D. https://codeforces.net/contest/1611/submission/136977033 saying that expected d[p[i]] < d[p[i+1]] when i output d[p[i]] for all i it is sorted means condition is fullfilled!
Check distance of each node from root.
still not able to figure it out.
In test case 1, both nodes 4 and 5 are at distance 4 from root 3. Your dist vector maintains weights of edges, not distance from the root. You cannot use that directly. You can try using a vector that maintains distance of each node from root.
Ratings must have been updated till now
Tired of waiting for the rating...
I'm in full solidarity with you
As a stonk investor, I cannot secure my profit...
Hey!
When we will get Editorials?
Also ratings are not changed yet.
You just have 0 delta.
Can anyone help me? I actually submitted my code twice from two accounts which has led to a violation of rules.Can someone tell me what proof can I give for that and where?
Well, you used two accounts. What do you want to proofe now?
finally I got expert for the first time!
Congrats :)
Hello All! For a few hours, the rating got updated but now it vanished. Is it happening the same with others as well?
Yes!! I had the same confusion.
Does anyone have an idea why this happened?
Editorial ?? :)
We'll provide it tonight
Can someone help me,please https://codeforces.net/contest/1611/submission/137113575