Codeforces Round #703 (Div. 2) Editorial

1486A - Shifting Stacks

Solution using C++: 107892022
Solution using Python: 107892053

1486B - Eastern Exhibition

Solution using C++: 107892065
Solution using Python: 107892085

1486C1 - Guessing the Greatest (easy version)

Solution using C++: 107892097
Solution using Python: 107892140

1486C2 - Guessing the Greatest (hard version)

Kudos to Aleks5d for proposing a solution to this subproblem.

Solution using C++: 107892122
Solution using Python: 107892144

1486D - Max Median

Solution using C++: 107892153
Solution using Python: 107892163

1486E - Paired Payment

Solution using C++: 107892178

1486F - Pairs of Paths

Solution using C++: 107892186

• 9 months ago, # ^ |

  ← Rev. 2 →  

  -189

  The comment is hidden because of too negative feedback, click here to view it

  • 9 months ago, # ^ |

    Pls don't lol

• 9 months ago, # ^ |

  Great Contest !!! Nice Problems

• 9 months ago, # ^ |

  ← Rev. 2 →  

  +71

  Solutions were added. Thank you for participation, you guys are great.

  • 9 months ago, # ^ |

    The test for E is weak so that many people use fake algorithm AC it, I think it is unfair!

• 9 months ago, # ^ |

  ← Rev. 3 →  

  -11

  • 9 months ago, # ^ |

• 9 months ago, # ^ |

  Editorial with hints. Thank you very much.

• 9 months ago, # ^ |

  seems like bro loves binary search

• 9 months ago, # ^ |

  where are these things in C question solution "fflush(stdout) or cout.flush() in C++;". please include these and if not then why it is not needed

  • 9 months ago, # ^ |

    endl does cout.flush inside.

    • 9 months ago, # ^ |

      Thanks a lot

• 9 months ago, # ^ |

  Can you please explain C1?

  https://codeforces.com/contest/1486/submission/109003138

  This is the link to my submission. But I am getting wrong answer on test 3. I can't understand why. Please help me out :((

• 9 months ago, # ^ |

  think about 4 points : (0,0) (0,1) (0,2) and (0,100). If you are fixing the median between (0,2) and (0,100) the first 3 point will have to move to the right(0,x+1) and that's bad for the solution.

• 9 months ago, # ^ |

  Just imagine: there are n points in line. You are on the leftmost point and walk to the rightmost point. When you begin to walk, the sum of all distance will get smaller until you arrive at the median —— or 2 medians (if n is even, there are 2 medians and you will get a same summary between them)

  • 9 months ago, # ^ |

    ohhoo ..nicely explained .. thnx

• 9 months ago, # ^ |

  ← Rev. 6 →  

  +7

  It is because you want to minimize where . You have ; and "=" happens when . To make it valid for all , in the case is odd, must take the value of , otherwise, can take any value from to (the two medians).

• 9 months ago, # ^ |

  Another way to think of it: for any two given points, choosing any point along the line connecting them contributes the same summary distance, i.e. the distance between them. So taking all the points as a whole, you can ignore the left-most and right-most point. You now have a smaller set, and you can keep doing this, until you either have 2 points left (if initial set had an even number of points) or 1 point left. So if you have 2 points left, any point between them will contribute the minimum (the distance between them), as going outside of those 2 points will contribute more than the distance between them. And obviously if you only have 1 point left, that point will contribute 0, and anything else would contribute more.

• 9 months ago, # ^ |

  ← Rev. 2 →  

  +3

  I solved it using a similar approach. Here is my code. Hope it helps : )

  • 9 months ago, # ^ |

    ← Rev. 2 →  

    +8

    it's not, but thank you anyway :). I found my mistake. I didn't think about the case when we should use the same edge twice in a row like in this example :

    Spoiler

• 9 months ago, # ^ |

  what does overflow case mean?

  • 9 months ago, # ^ |

    Sum of numbers is greater than MAX_INT

    • 9 months ago, # ^ |

      It's literally in the sample case.

      • 9 months ago, # ^ |

        I didn't notice that. XD What I meant is a case that gives WA verdict for a submission that contains overflow like this submission 107786541

• 9 months ago, # ^ |

  What else should it error as?

  • 9 months ago, # ^ |

    Something like Query Limit Exceeded.

    • 9 months ago, # ^ |

      In interective problems u can use assertion on number of queries to make sure whether it is wrong ans or query limit exceeded

      • 9 months ago, # ^ |

        Could you please tell me something about how to use assertion to konw whether or not my submission is query limit exceeded.

        • 9 months ago, # ^ |

          Here is an article on assertion article Here is my yesterday code, although it failed still u can see how I used assert. Code link

    • 9 months ago, # ^ |

      IMO this gives too much information, like in constructive problems if you print the wrong length you don't get a custom result.

    • 9 months ago, # ^ |

      Maybe add if(totalQueriesMade>40) sleep(5) and purposely get TLE (assuming your code won't TLE otherwise). Hack-ish, admittedly.

• 9 months ago, # ^ |

  Test with this:

• 9 months ago, # ^ |

  You need to read the entire line, even if you find sum < 0.

  • 9 months ago, # ^ |

    Thank you!! I will cry in a corner now:)

• 9 months ago, # ^ |

  You break possibly before reading the input. I suggest read all the input before solving the testcase.

• 9 months ago, # ^ |

  ur code fails on 3 3 0 0 1 3 0 1 0 3 1 0 0 answer is NO , NO , NO I guess your code guess a different answer. Refer https://codeforces.com/problemset/submission/1486/107870392 the function solve2

  • 9 months ago, # ^ |

    sorry I stopped taking input when i got the answer so it messed up further inputs...

• 9 months ago, # ^ |

  Hi,the logic is no8t making any sense to me. Consider this sequence 0 1 2 2 8 9 20. Do you think your solution will give correct output? Even though h-i is negative at i=3, still the sum becomes positive. But do you think in this case a solution is possible?

  • 9 months ago, # ^ |

    the logic is correct, I am checking for every input...I broke when I found the ans...didnt take all the inputs, thats why it gave wrong ans

• 9 months ago, # ^ |

  I have the same mistake as you and wa on test2. Fortunately, I solved it.

• 9 months ago, # ^ |

  What do you mean by "fake" solutions?

  • 9 months ago, # ^ |

    ← Rev. 2 →  

    +20

    many O(n^2) brute force solution got accepted during system testing. I hacked some submissions, but there're too many... just like: 107844532 107866549 107865668 107840161 107832126

  • 9 months ago, # ^ |

    The system tests for problem E are weak

• 9 months ago, # ^ |

  I agree with you. There are about 50 slow solutions was hacked, why you are can't retest and redistribute the rating?

• 9 months ago, # ^ |

  you get the max median of subarray of length exactly k not at least k

  • 9 months ago, # ^ |

    can you explain why length k is not optimum, i think length k should be optimum

    • 9 months ago, # ^ |

      n = 3 k = 2

      • 9 months ago, # ^ |

        Thanks

    • 9 months ago, # ^ |

      With array and , the only possible median for subarrays of length is , but the best possible median is attained when we consider the entire array.

ll mid = lo + (hi - lo) / 2;

ll mid = lo + (hi - lo + 1) / 2;

ll find_left(ll secondMaxIdx)
{
	ll lo = 1, hi = secondMaxIdx - 1;
	while (lo < hi)
	{
		ll mid = lo + (hi - lo) / 2;
		if (ask(mid, secondMaxIdx) == secondMaxIdx)
		{
			lo = mid;
		}
		else
		{
			hi = mid - 1;
		}
	}
	return lo;
}

• 9 months ago, # ^ |

  While hi = lo + 1, like lo is equal to 2 and hi is equal to 3, mid calculated by (lo + hi) / 2 is 2. In this point, you'll get stuck by lo = mid because lo will never change.

  • 9 months ago, # ^ |

    I see, thanks for pointing it out

• 6 months ago, # ^ |

  See topcoder binary search tutorial.

  • 6 months ago, # ^ |

    Yeah, I learned to understand when to return lo and hi, rather than just memoziring it. Thanks!

• 9 months ago, # ^ |

  Can't we solve this for general weight. Means we can construct a new graph in which there is an edge between u and v iff there is exactly one vertex z between u and v in original graph s.t. u-z and v-z are edges in the original graph and weight of uv in new graph will be as defined in the problem. Now simply we should run Dijkstra on this new graph.
  What is wrong with this method? Can you please point it out.

  • 9 months ago, # ^ |

    In the worst case, the new graph will consist of edges.

    • 9 months ago, # ^ |

      I have solved it for generic weight : https://codeforces.com/contest/1486/submission/108202408

      Let me know , if you feel there exist a test case which can hack this solution.

      Time complexity looks good to me to pass within the time limit.

• 9 months ago, # ^ |

  I don't understand the meaning of the word "relaxed" here. Can you please explain Ji_Kuai

• 9 months ago, # ^ |

  Thanks for commenting your code for today's C. It helps.

• 9 months ago, # ^ |

  okwedook Please answer the spookywooky comment, I have same doubt. I find difficulty in understanding the editorial of Problem E.

• 9 months ago, # ^ |

  Hey, Can you share the link to binary search by Errichto? On youtube, I am able to find only one video.

• 9 months ago, # ^ |

  To debug such scenarios, you can stress test your solution as well.

  You can write a bruteforce for this problem very easily. e.g.

  1. Generate random permutation A.
  2. Take your query into a separate function. Answer it by using the array A. You can find second max in O(n) easily.
  3. In the end, match the maximum element position returned by your program with actual maximum element position.

  Keep doing this for many iterations till you find a counter case. This kind of stress testing strategy helps a lot in many problems. You can see my submission for some hints regarding implementing this bruteforce. The code is really messy and unpolished, but I have attached it for reference anyway.

  • 9 months ago, # ^ |

    Hey, thanks a lot. Found my mistake! Also, am I not supposed to post solutions in the comments or something? Since I got a lot of negative feedback? If no, then I'll delete the comment.

    • 9 months ago, # ^ |

      Don't post the solution as it is in the comment. Instead, post a link to the submission or use a spoiler tag

• 9 months ago, # ^ |

  The comment is hidden because of too negative feedback, click here to view it

  • 9 months ago, # ^ |

    I don't think they are added . Still O(n^2) submissions are getting AC

• 9 months ago, # ^ |

  It seems that every interval like will cost 1 query and the number of those intervals is . In addition, there are other intervals that will cost 1 query.

• 9 months ago, # ^ |

  I tried but it gives TLE on test 5, and I don't think it can be optimized further.

• 9 months ago, # ^ |

  how are you making sure that you always travel two edges at once?

• 9 months ago, # ^ |

  The binary search asks the question: is there a subarray of some length with a median of at least 1?

  So we replace all elements that are 1 or more in the array with a 1, and those that are less than 1 with a -1, resulting in [1, 1, 1, 1, 1]. We can find a subarray of length at least 3 with the median 1, so it follows that the answer is 1 or more.

• 9 months ago, # ^ |

  I'm not sure what the official solution is, but I can try to explain my solution to F. Consider a vertex , and say we want to count all pairs of paths that have as their unique common vertex. First arbitrarily root the tree at . We break the paths into types:

  • up paths: paths that start at and go towards the root
  • through paths: paths that contain the parent of , , and another node in the subtree of
  • down paths: paths that have as the LCA of the endpoints and are not strictly up or down the tree
  • vertex paths: paths that are from to

  For a fixed , we can take care of all pairs of paths that contains vertex paths easily, so we ignore those. We can pair any up path and down path. We may also pair through paths and down paths that do not overlap. We may also pair a down path with a down path if they do not overlap. We can easily count all these quantities using Heavy Light Decomposition and LCA.

  Submission link

• 9 months ago, # ^ |

  n=3 array=[1,2,3]

• 9 months ago, # ^ |

  107905723 In line 150, you are initializing p with INT_MAX, it should be zero because if you don't consider any element ie prev sum, the value of p should be 0.

  • 9 months ago, # ^ |

    Yeah, I got that. Thanks though.

• 9 months ago, # ^ |

  ← Rev. 2 →  

  0

  Worst case needs O(n) queries. Try: [7 6 5 4 3 2 1 8]

  • 9 months ago, # ^ |

    But I am always halving the search space? Can't seem to figure out the error in my logic.

    • 9 months ago, # ^ |

      mid==l is possible, and when you call binarysearch(mid+1, r), you are decreasing the search space by size 1, not halving it.

      More importantly it sometimes gives wrong answer. Try 4 5 6 1 2 3

      • 9 months ago, # ^ |

        Oh I got it. I made 2 variables mid and and middle and got confused between them :(

• 9 months ago, # ^ |

  ← Rev. 4 →  

  +1

  Let's consider the case when smax<maxpos (the first while loop in the code). The loop invariant property is that the range [l,..,r] always contains both,2021-02-19 smax and maxpos. It is beneficial to break the loop just when l and r become adjacent (i.e. when r - l > 1 becomes false) because now the only way for the above property to hold is that l==smax and r==maxpos, and we can immediately output r (or r+1, in case of 1-based indexing).

  • 9 months ago, # ^ |

    why is it like the range[l...r] will contain both smax and maxpos like in the example: 1 4 3 2 5 the loop will break at l=3 and r=4 whereas the index of smax is '1'(0 indexing).

    • 9 months ago, # ^ |

      Oops.. the claim about containing of smax is not true at all.. Feeling stupid now.

• 9 months ago, # ^ |

  I think it because you need to do query at l,r where l!=r

  • 9 months ago, # ^ |

    yeah, it is fixed thanks a lot!

    • 9 months ago, # ^ |

      Would anyone be able to find out what was wrong in this submission?

• 9 months ago, # ^ |

  Can you please explain problem E, not able to get what the editorial says.

  Spoiler

• 9 months ago, # ^ |

  see my submission, here d is 1 for right direction and -1 for left direction.

• 9 months ago, # ^ |

  You get the max median of subarray of size exactly k not at least k so you bug on 3 2 2 1 2 Your answer is 1 true answer is 2

  • 9 months ago, # ^ |

    oh got it, I missed the at least part. Thanks a lot man!

• 9 months ago, # ^ |

  Cause it's the first element to get the needed answer as written in the editorial

  • 9 months ago, # ^ |

    Ok got it, thank you for the very fast response

  • 9 months ago, # ^ |

    Can you please tell the logic behind using r-l>1 instead of usual l<r in binary search in the editorial solution?

    • 9 months ago, # ^ |

      I use binary search with subsegment , so it means I look at elements . This is called a half-interval (in russian at least). That's why contains only one element.

      • 9 months ago, # ^ |

        ← Rev. 3 →  

        0

        Thanks! If i use l<r, the program stucks in infinite loop like in the sample test case 5 1 4 2 3 it goes like:

        
        5
        ? 1 5
        3
        ? 1 3
        3
        ? 2 3
        2
        ? 1 3
        3
        ? 1 3
        .....

        why so?

        • 9 months ago, # ^ |

          Well, because l is always less than r. That's the beauty of half-interval.

          • 9 months ago, # ^ |

            Can it be generalised that when we should use l<r and when l+1<r in binary search or is it just for this specific problem?

            • 9 months ago, # ^ |

              I always write binary search this way. Just use half-intervals and you'll be happy. Consider it like this: l is minimal possible value and r is the first value, that is most definitely working out for you. You can rotate the problem (make segment and code wouldn't change at all (only checks and output).

              • 9 months ago, # ^ |

                ok,thanks a lot!

              • 9 months ago, # ^ |

                Thanks for your explanation, really appreciate it!

                It would be really great, if you could elaborate on these points —

                Consider it like this: l is minimal possible value

                Minimal with respect to what condition?

                and r is the first value, that is most definitely working out for you

                You mean the first True value?

              • 9 months ago, # ^ |

                If the answer is in range you would use or . That easy, just add 1 (or -1) when needed and cover all the possible answers. Actually should work fine too.

      • 9 months ago, # ^ |

        What are the initial conditions for l and r, in case I use your half-interval technique?

        • 9 months ago, # ^ |

          You can refer to this comment.

          • 9 months ago, # ^ |

            Okay, got it, my bad :)

• 9 months ago, # ^ |

  Check whether l == r. The length of a range should be more than 1.

  • 9 months ago, # ^ |

    ← Rev. 2 →  

    0

    I was just using too many queries, my bad!

• 9 months ago, # ^ |

  You need to read all n numbers

• 9 months ago, # ^ |

  When you're incrementing with the extra rather decrementing extra from .

• 9 months ago, # ^ |

  If n = 5 and inputs are 2 1 1 1 1, then for loop breaks in the fourth iteration and the last one is acting as n for next test case.

  • 9 months ago, # ^ |

    How did you debug so fast... I'm a beginner and often unable to find out mistake in my own code and often waste much time finding out mistakes, please tell how to do that

    • 9 months ago, # ^ |

      I had done the same mistake in a round.

• 9 months ago, # ^ |

  ← Rev. 4 →  

  +15

  I have considered based indexing of nodes to save memory.

  Since weights of all edges is between and . For each node say , create nodes say ,,,.....

  Now for each edge as input , make edges and as shown in following code since edges are bidirectional.

  add edges

  Let's understand how Dijkstra will work here with example :

  consider nodes . Suppose edge length between and is and edge length between to is . Thus distance between and is by using definition in question.

  First we will insert to priority queue . Since is connected to with edge length , will be inserted in priority queue. Also is connected to with edge length , thus will be inserted to priority queue .Hence distance between and is .

  Now try to scale above example to any number of vertices and it will be clear why it works.

  priority queue based implementation : 107975317 set based implementation : 107975265

• 9 months ago, # ^ |

  I guess it wasn't necessary

• 9 months ago, # ^ |

  When your function returns for some value , it does not mean that there will be a subarray with median , it means that the median is atleast .

• 9 months ago, # ^ |

  The answer will only exist for an arbitrary number in if there's an subarray of size in the prefix array with .

• 9 months ago, # ^ |

  ← Rev. 2 →  

  0

  So you are strong enough:)
  Actually, I have written a pretty neat data structure to get RMQ in O(1) online (so it can handle LCA online of course).

  • 9 months ago, # ^ |

    I didn't understand why you praised me until I actually read your editorial. :)

    I am not going to show off. However, I would like to add my little bit to nowadays's problem approaching style.

    In my opinion, the (nearly)-linear algorithm is the easiest to implement, without using any heavy data structure. Back in to the old days, the people who know HLD / LCT is the true master. XD

    • 8 months ago, # ^ |

      Would you mind explaining how you obtained the triples (lca, subtree1, subtree2) in linear time (if you remember the problem by now and are willing lol)? I'm too lazy to read code, especially for a problem with such a long implementation.

      I did it for each vertex pair by computing the th ancestor of , and the same for . So I couldn't get rid of the log factor :(

      • 8 months ago, # ^ |

        The problem is that given and where is an ancestor of , we would like to know in which subtree of that lies.

        We can perform a DFS on the tree, and keep track of an array , which is the current subtree of the vertex we are in. When reaching the vertex , is what we need.

        This approach is conceptually simpler than what I had done in my code, and the only drawback is that we have to do DFS twice. One for LCA and one for the subtree query.

        My code is more complicated as I solved LCA and subtree query in one DFS as I remember.

        • 8 months ago, # ^ |

          Ah, I understand, thank you so much! I suck at using the idea that you can maintain an array of size during the dfs, it just makes my brain explode for some reason lol.

          A similar idea is that while visiting vertex , maintain a stack consisting of the vertices along the path from the root to (in order). Then is equivalent to . I think the latter idea seems more intuitive to me, but maybe it's just because I've seen it before.

• 9 months ago, # ^ |

  ← Rev. 2 →  

  0

  Why do you think the answer should be 3? The answer is 1(only 8).

  1. for 6: the sum of distance is 16.

  2. for 7: the sum of distance is 14.

  3. for 8: the sum of distance is 12. Cleary, The minimal distance is for 8 only.

  • 9 months ago, # ^ |

    oh, ok. Got it. Thanks

• • 8 months ago, # ^ |

    Nope, I couldn't. But seems like you figured it out. What was the issue?

    • 8 months ago, # ^ |

      The issue is with the initialization of the minimum vector, it should begin with zero value. See the difference in these two submissions for clarity:

      https://codeforces.com/contest/1486/submission/112135909 (WA 10th case)

      https://codeforces.com/contest/1486/submission/112136806 (Accepted)