Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

vovuh's blog

By vovuh, history, 2 months ago, In English,

1343A - Candies

Idea: vovuh

Tutorial
Solution

1343B - Balanced Array

Idea: vovuh

Tutorial
Solution

1343C - Alternating Subsequence

Idea: vovuh and MikeMirzayanov

Tutorial
Solution

1343D - Constant Palindrome Sum

Idea: MikeMirzayanov

Tutorial
Solution

1343E - Weights Distributing

Idea: MikeMirzayanov

Tutorial
Solution

1343F - Restore the Permutation by Sorted Segments

Idea: MikeMirzayanov

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +163
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +12 Vote: I do not like it

How Problem D can be solved using scanline algo?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +54 Vote: I do not like it

    Well, I can explain it rough. The thing is that there are $$$O(n)$$$ (actually at most $$$2n$$$) endpoints of these segments (the second case) and $$$O(n)$$$ (at most $$$n$$$) sums of kind $$$a_i + a_{n-i+1}$$$ (the first case). And the idea is that you are only interested in these $$$3n$$$ points (maybe with some adjacent points also). This is because in other points values of $$$pref$$$ and $$$cnt$$$ don't change at all. So you can compress coordinates and then just consider all segments as events going from left to right and changing the value of $$$pref$$$ correspondingly and store $$$cnt$$$ in some logarithmic data structure like map in C++.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I have implemented an O(nlogn) solution using compression here. For those of you who are confused, check it out!

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what exactly is pref adding up

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          pref[x] stores the number of pairs whose sum can be made equal to x with less than 2 operations (the same as editorial pref).

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I guess i over-killed the over-kill...

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      greetings! @vovuh can you suggest me any tutorial,book,pdf,blog etc from where i can learn some fundamental techniques like prefix sum or anything that are frequently needed in codeforces contest problems.Thanks in advance your editorials are very clear and easy to understand .thats why i choose those problems where your editorial exists.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you could always search for the cp3 (competitive programming 3) book pdf

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yeah .i have a hard copy of that .but there is no techniques on adhoc problems rather a list of problems

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      @vovuh any link for scanline algo? I can only find it for computer graphics. Is that the one?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I dont't know any good explanations of this "algorithm" because it's more likely approach than algorithm, but I found one tutorial about it, seems good enough.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    video editorial of D. Click here

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Because I think compared to the tutorials solution it is much simpler code here a link to a submission 77584565

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain your solution? Thanks

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it +2 Vote: I do not like it

        Vovuh did above. Every pair of values in our array can be splitted into 5 parts.

        Let be min the min of the two values in the array, and max the bigger.

        First part where x is so low that we must decrease both numbers, so if x is in this interval the pair contributes +2

        if $$$x>=min+1$$$ the pair contributes +1

        if $$$x==min+max$$$ the pair contributes 0

        if $$$x<=max+k$$$ the pair contributes +1

        if $$$x>max+k$$$ the pair contributes +2

        Then we create an array of size maximal possible x, and insert the above numbers. Then the prefix sum at position i of the array is the number of operations we need if x==i. So we choose the smallest of them as answer.

        Note that this runs in O(n), and if k would have had huge constraints, we would simply use a map instead of an array for evt.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          Yeah man, I used the same approach.
          https://ideone.com/1gdDsO

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah, highfive

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              What do you mean by events. Are these points or segments?

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                The word "event" comes from typical problems which are solved with this algo.

                In the simple version of the problem we want to find how much of a set of given intervals overlap at some point, or where is the point with most/less overlaps.

                Then there are two kind of events while we loop though the intervals, this is start of an interval, and end of an interval. At start we do +1, at end we do -1.

                We loop throug the sorted list of events. The body of the loop kind of looks like an event handler.

                Example tutorial

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Sire, please have a look at my BRUTE FORCE solution for D and tell me what's wrong in it. I'd be grateful:

          #include<bits/stdc++.h>
          using namespace std;
          
          int numberOfChanges(vector<pair<int, int>> v, int x){
              int sum= 0;
              for(int i=0; i<v.size(); i++){
                  if((v[i].first+ v[i].second)==x) sum+=0;
                  else if(v[i].first >=x && v[i].second >=x) sum+=2;
                  else sum+=1;
              }
              return sum;
          }
          
          int main(){
              int t;
              cin>>t;
              while(t--){
                  int n, k;
                  cin>>n>>k;
                  int A[n];
                  for(int i=0; i<n; i++){
                      cin>>A[i];
                  }
                  vector<pair<int, int>> v;
                  for(int i=0; i<n/2; i++){
                      v.push_back(make_pair(A[i], A[n-i-1]));
                  }
                  int count, min_count=INT_MAX;
                  for(int i=2; i<=2*k; i++){
                      count= numberOfChanges(v, i);
                      if(count<min_count) min_count= count; 
                  }
                  cout<<min_count<<"\n";
              }
              return 0;
          }
          
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Let's say you call for function numberOfChanges(v, i) for i =2*k and in function: in vector v , if a pair {1,1} exists then you are incrementing sum by 1 , but it has to increased by 2. Hope you got it, check you conditions for incrementing sum in function numberOfChanges(v, i) , otherwise it looks fine.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I used this same approach first as it's bruteforce but it gets TLE at test case 12.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hi, could you please tell the ranges for each of the 5 possible x values you mentioned? I understood the intuition behind using prefix sums, but I'm not able to understand the pair of indices that are incremented and decremented.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You can look at English commentary for problem D: Constant Palindrome Sum here

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thank you!!! I finally understood it!

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for the tutorial <3

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Question D is the overall complexity O(k(n+k))? Since the procedure needs to be repeated for each possible x

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Why? I'm precalculate three (actually two) parts on $$$O(n+k)$$$ time and then iterate over all possible sums in $$$O(k)$$$ with getting precalculated values in $$$O(1)$$$ time.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ohh I don't think I understand the editorial properly. Why are we calculating prefix sums?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Because you had to know for each point (sum) the number of segments (pairs) covering it. And this is the standard problem that can be solved with prefix sums.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        You can check my code (not much pre-computations required)
        https://ideone.com/1gdDsO

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    We first precompute the needed pref[] and cnt[] in O(n+k) so when we repeat the procedure for each possible x we can use the precomputed elements in O(1) making overrall complexity O(n+k)

    UPD: Just noticed the question has been answered by vovuh

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thank you so much vovuh for the great contest.... and thank you codeforces for bringing such contest so that we can utilize our time in learning and solving problems in this pandemic situation.... thank you

»
2 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Can anyone tell me what am I doing wrong in problem E? Here's my submission 77588849

In the graph, I am calculating the minimum distance from a to b, and then b to c. During this, I am storing the frequency of the edges I will visit, and then later assigning the least price to the edge with the highest frequency.

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    You have not handled the case like, when a==b or when b==c. Edit: My bad. Its working fine.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No sir, all those cases are working perfectly fine, when a == b or when b ==c or when a==b==c .

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think that you are missing the case when there can be two ways to go from B to C and one of the ways has the repeating edges from the path A to B and thus you can reduce cost by visiting from that way.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I couldn't figure that out so long, thank you !

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    your code will WA answer for the test case 1 5 5 3 1 5 10 5 6 100 80 3 2 1 2 1 4 5 4 5 3 answer is 32 your code is giving 101 means that here you will go from a to b then from b to c via a that will give minimum answer

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice I have done same mistake.then What is the solution for E?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here a test case that resembles the graph of 2nd example in the problem.

    1 7 9 1 5 7 3 3 5 10000 10000 10000 10000 10000 10000 1 2 1 3 1 4 3 2 3 5 4 2 5 6 1 7 6 7

    The optimal output should be 1->7->6->*5*->6->7 then you assign these prices 5,3,3 to get the answer as 5 + 2*(6) = 17.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    You cannot do the question on basis of only considering shortest from A to B and then shortest from B to C separately. Consider smallest path from A to B(length s)and there is another path from A to B(length s+1)which has only one more edge then the smallest one.Suppose that path contains C, so that is more advantageous and we need only smallest s+1 prices while with the shortest path we will need then s+k prices (k distance of B from C).

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thank you everyone for helping me figure out my mistake. I really Appreciate it

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain me solution to problem E in simpler words.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone why my code didn't got accepted..??

https://codeforces.com/contest/1343/submission/77549512

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess,it is because of the data type the value overflows so try using long long.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For E why would the optimal path only have 1 or less intersection?

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Finally solved one question after joining here few months back in rated. Yaay. Small step forward.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

In problem F, why would the permutation be unique?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Since the segments have endpoints at $$$2$$$, $$$3$$$, ..., $$$n$$$, at each iterative step you are actually picking the segment that is with endpoint $$$1$$$ greater than the segment you previously picked. There is exactly $$$1$$$ valid segment in each step, which means the reconstruction is unique if an valid permutation exists for you fix of first element.

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Why is the blog of the solution called Editorial in this blog but called Tutorial here in the contest?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the tutorial. But I don't understand the tutorial of problem E, can anybody help me please?(Please explain me in simpler words) Thank u very much!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    here we follow the path: a->x->b->x->c

    for every vertex x <= n, find the shortest distances from a to x, b to x, and c to x

    since b->x is common, we should distribute minimum weights along this path. Let prefix(i) be sum of i smallest weights.

    So the answer will simply be prefix(distance(a to x) + distance(b to x) + distance(c to x)) + prefix(distance(b to x))

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody explain problem F I am not able to understand the tutorial

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    don't go for F now just focus on A,B,C of div2 and A,B,C,D of div3... i am saying this because of my experience in compi beleive me or not i am saying this for your good... keep it up mate....

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any Suggestion , what can be wrong in my logic for question D .

My code

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Why do we need to convert to binary representation, while we can just add 2^0 to (2^0 + 2^1 + ... + 2^(k-1)) = 2^k :D

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    It is another correct way, I used this way too :D

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

In Problem D, Can anyone explain why (n/2) — prefix(x) is needed for calculating part 3 of the solution?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    See for any particular sum(say x), prefix[x] is having number of pairs that need at most 1 element to be changed. Since for any pair we can make any sum(ofc less than 2k) by changing both the elements so if we have n/2 pairs in total and prefix[x] is number of pair that need at most 1 change so n/2 — prefix[x] is number of pairs which needs both the elements to be changed.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's because the ones we calculated prefix for are the ones who can reach that x by replacing one element. Thus by subtracting prefix(x) from n/2 and multiplying it by 2 gives us those pairs where we have to change both elements.

    Have a look at my submission. I have added comments.

    https://codeforces.com/contest/1343/submission/77603570

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Part 3 includes those pairs in which we have to change both values to get the desired sum. Since prefix(x) contains the count of pairs in which we have to change one or none value, hence (n/2)-prefix(x) gives the third part.

»
2 months ago, # |
Rev. 4   Vote: I like it +2 Vote: I do not like it

In problem E, my approach is —

  1. Find the set of nodes that lie on the shortest path from a to b, stored in res1.

  2. Find the set of nodes from lie on the shortest path c to b, stored in res2.

  3. Find the common nodes (if any) that lie from b, let this be equal edges

  4. Find the distinct edges, let this be diff edges = res1.size() + res2.size() — 2 * equal.

Then I assign the min values to common edges and the next min values to other diff nodes.

I am getting WA on Test-4. Can anyone tell me where I am doing wrong ?

I get — wrong answer 320th numbers differ - expected: '4', found: '6'. How to see the 320th tc ?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I did the same mistake and got the same WA on the same test case :D. The problem is that you are assuming that the shortest path from a->b->c will comprise of shortest path a->b and shortest path b->c, which is not true..

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why it is not true?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Well I haven't worked it out mathematically, but if you think intuitively, you have to maximize the number of repeating edges while also minimizing the total distance traveled. So it is possible to construct a graph in which a longer path gives you more number of repeated edges, which reduces the total cost, as compared to the shortest path consisting of all distinct edges.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Hey, this is one such case in which this method produces wrong answer — This has been pointed out by someone in the comments above —

        1
        5 5 3 1 5
        10 5 6 100 80
        3 2
        1 2
        1 4
        5 4
        5 3
        

        The optimal answer to this will be 32.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You also have to check with the set of nodes present in the shortest path from a to c.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the D problem. How did we get the value (n/2)-prefx and the final equation also?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Since each element of the array lies between 1 and k, the range of values [min(a[i],a[n-i+1])+1,max(a[i],a[n-i+1])+k] will include the pairs for which the sum equals x as well. Hence pref(x) represents the pairs for which AT MOST 1 needs to be changed. n/2 is the total. Subtract pref(x) from it, we will get the ones which require both elements to be changed. Final equation we need number of changes = (at most 1 change required — no changes required) + 2*(number of pairs which require both elements to be changed)

    Last term multiplied by 2 because 2 elements are changed.

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

removed

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

my solution for prob B is:

let n = 2k (since n is always divisible by 2) 1) check if (n % 4 == 0); if yes, continue below, else there exist no solution.

2) now we have array of 2k numbers , k numbers should be even and other k odd. lets assume that we take first half array made of first k even natural numbers i.e [2,4,6,8...2k] and second half made of first k odd natural integers i.e [1,3,5,7... 2(k-1)-1, 2(k-1)]. The sum of first half is k*(k+1) of 2nd half is (k^2), which is minimum for any k distinct numbers in their respective cases. (and always k(k+1) > K^2 )

3) so now we have to just make sum of k odd distinct integers k(k+1) (since we cannot make sum of distinct even integers less) which is always possible since K^2 < K(K+1) and k and k(k+1) have same parity.

4) now just follow steps for Finding K distinct positive odd integers with sum N. (https://www.geeksforgeeks.org/find-k-distinct-positive-odd-integers-with-sum-n/)

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone tell how can the solution is found out because i am not getting ++pref[] part code and further code so can anyone explain how the results are generalized..? Problem D

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is an optimisation. Instead of incrementing all elements in a range, we increment the start of the range [a,b], i.e., position a and decrement the end of the range +1 position, i.e., b+1, to indicate that all the elements in the range [a,b] have a count of +1 due to the current sum of x. Then we iterate over the pref array to get the actual counts.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It is on of the popular techniques, it can update in O(1) time and changes are accumulated at the end by calculating the prefix sum.

    The range is updated using the index bounds. Consider you want to update the range [l,r] then that can be done adding the +1 to the left bound and -1 at the right corner. So whenever you would be calculating the final results, the following thing happens -:

    1. The +1 is propagated in the range [l, r] since you are adding the previous element to the present element.

    2. The -1 handles the stopping case at r + 1 and now the +1 is neutralized by -1.

    Once this array pref is generated, you are now with sum values which would require just a single modification to reach sum.

    Since the answer for this overall problem will be :

    1. The number of pairs in which both elements need to be changed.
    2. The number of pairs in which a single element need to be changed.

    For the 2nd one, cnt[i] (already having the sum of i beforehand) — pref[i] (which need one element modificationto reach sum i)

    For 1st one, the remaining pairs will be the one with 2 modifications, (n / 2) (Total pairs) — pref[i] (sum with one modification to reach i).

    Multiplying it by 2 since two modifications are required.

    Now try to calculate minimum by iterating over all the possible values of sum [2, 2k].

    Sorry for the bad representation. I hope it helps.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hey can anyone tell me why are we doing --pref[max(r1, r2) + 1] in problem D? also why are we calculating prefix sums?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for any pair a[i] and a[n-i-1] we can make it equal to some sum x by changing at most one element a[i] or a[n-i-1] if sum x is in range min(l1,l2) to max(r1,r2). but as sum goes to max(r1,r2)+1 we need to change two elements

    we are calculating prefix sum because above argument follows for all sum values that are in range min(l1,l2) to max(r1,r2)

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Video editorial of D. Click here

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you! the solution of D is great.my solution is LTE:(

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is a solution with Explanation for D (Check Here)In case anyone is interested

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i got the idea of d and u i.e ranges starting and ending before and after x but can u please explain how did u conclude get =min(d,u)

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if u is starting points whom are before x and d is ending points after x then the number of lines where x lies is min(u,d) for example say the ranges are (1,5) , (3,12) (4,8) suppose x = 7 the u=3 and d = 2
      So x lies in two ranges which correct i.e. (3,12) and (4,8)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution of D using Difference Array https://codeforces.com/contest/1343/submission/77550669

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem E, can anyone tell me what should I do if a point is visited again? how would I know if I have assigned an edge some weight more than once? Thanks in advance.

  • »
    »
    2 months ago, # ^ |
    Rev. 6   Vote: I like it +1 Vote: I do not like it

    You can ignore overestimates, because it can be shown that vertices that cause overestimates are never the optimal choice for intersection.

    A very rough "proof": if the editorial's algorithm assigns more than one cost to a set of edges and thus overestimates the cost, it means that at least two paths among $$$x \rightarrow a, x \rightarrow b,$$$ and $$$x \rightarrow c$$$ overlap. The overlapped edges would form a path from $$$x$$$ to some other vertex $$$y$$$. In this case, $$$y$$$ is always a better choice of intersection.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why my submission is not showing and also final standing not showing I have solved first 4 qus

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is in queue, wait for the system testing to get over.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How can we use binary search in problem D?? It has tag of binary search. I found out that for making sum of pair from 2 ..... 2*k does not yield a function that has one global optimum...so how we can use binary search on it??

Here is one of some possible arrangement :
n=10 k=5
array=1 4 2 3 5 2 3 1 4 2
sum  = changes required
2       = 8
3       = 5
4       = 6
5       = 5
6       = 4
7       = 4
8       = 6
9       = 8
10     = 9

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I built a vector that holds the minimum value every pair can take with one change, and a vector that holds the maximum value every pair can take with one change. Fix a target 1 <= x <= 2k that you want every pair to equal after your changes. The number of pairs whose min is > x will require 2 changes, as will the number of pairs whose max is < x. You can binary search for the number of pairs that fulfill these conditions, using something like lower_bound(mins.begin(), mins.end(), x). You'll can also see that a pair cannot fulfill both of these conditions simultaneously, so we don't double count.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yeh thanks.. now i see we use binary search as our intermediate step and not a primary one. Thank you for explanation!

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In Problem D, I used similar approach, created 2 arrays Krise and Kfall. let both numbers be ai and bi. Sum ai+bi needs zero replacements, 1 replacement needed from ai+bi+1 to max(ai+bi)+k. above it we need to replace both numbers. similarly store for x < ai+bi in kfall array. Then I used prefix sum of both and calculated minimum replacements required by iteration over all x. All sample test cases passing but there is a minor mistake in final submission, help me out.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define m 1000000007
typedef vector<ll> vll;
typedef pair<ll, ll> pll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll t = 1;
    cin >> t;
    while (t--)
    {
        vll a;
        ll n, k;
        vll krise, kfall;
        cin >> n >> k;
        if (n <= 2)
        {
            cout << 0 << endl;
            continue;
        }
        a.resize(n + 2, 0);
        for (ll i = 1; i <= n; i++)
            cin >> a[i];
        kfall.resize(2 * k + 9, 0);
        krise.resize(2 * k + 9, 0);

        for (ll i = 1; i <= n / 2; i++)
        {
            ll ai = a[i], bi = a[n - i + 1];
            krise[ai + bi + 1] = 1;
            krise[max(ai, bi) + k + 1] = 1;
            kfall[ai + bi - 1] = 1;
            kfall[min(ai, bi)] = 1;
        }
        for (ll i = 3; i <= 2 * k; i++)
        {
            krise[i] = krise[i - 1] + krise[i];
        }
        for (ll i = 2 * k - 1; i >= 2; i--)
        {
            kfall[i] = kfall[i + 1] + kfall[i];
        }
        ll mini = n - 2;
        for (ll i = 2; i <= 2 * k; i++)
        {
            mini = min(mini, kfall[i] + krise[i]);
        }
        cout << mini << endl;
    }

    return 0;
}
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I still have some questons in D

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

New to codeforces here, can anyone tell me yesterday I solved 3 problems here but now RED is showing on B and C (even though code is same as editorials) WHY?

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone suggest more problems like D? The prefix sum approach seemed very cool

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E why are we checking dist(a,x)+dist(b,x)+dist(c,x)≤m ?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    we have our prefix sum array of size M it is practically impossible to have more than M distinct edges weights so This condition is applied to control indexing error If You don't apply it will give you an out of index error for some cases :)

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Because it would be stupid to travel an edge 2 times except x->b.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If someone knows how to solve Problem D using Scanline Please mention your code or any good resources to learn it will be appreciated :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain the segment tree or BIT based approach in problem D that would be helpful??

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain what problem c actually meant?? still didnt get the problem clearly. thank u.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The given array will consist of some positive and some negative elements. An alternating subsequence will consist of alternating elements (pos,neg,pos,neg... or neg,pos,neg,pos.... and so on). you need to take the max length of alternating sebsequence and find its sum. Remember there could be multiple such subsequence of max size but you need to print the max sum among all.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for D, we can also just check for only those sums that the pairs already make instead of checking all values from 2 to 2*k.In worst case,the maximum value will be n/2, when one element from all the pairs have to be changed.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    In the example {6 1 1 7 6 3 4 6}, K = 7. the sum values are 12, 5, 4, and 13. But you get minimum when u make x as 7 or 8 or 9 or 10. So the logic of only checking for sum fails.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In worst case(for example this one),the answer can be at most n/2.I have initialised answer with n/2.whenever x comes out to be anything other than the sums,the answer has to be n/2.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Yeah that is correct, n/2 is the max changes you need to make, but then checking for sum pairs will not suffice.

»
2 months ago, # |
  Vote: I like it -37 Vote: I do not like it

typedef long long int ll;

include

include <bits/stdc++.h>

include

include <math.h>

include <string.h>

using namespace std; int main() { int t; cin >> t; while(t--) { ll n; cin >> n; ll arr[n]; ll brr[n]; for (ll i = 0; i < n;i++) { cin >> arr[i]; if(arr[i]>0) brr[i] = 1; else brr[i] = -1; } ll sum = 0; for (ll i = 0; i < n;i++) { ll lar = arr[i]; ll j = i; int val; if((brr[i]*brr[j])==brr[j]) val = 1; else val = 0; while(j<n && val==1) { lar = max(lar, arr[j]); j++; } sum = sum + lar; i = j — 1; } cout << sum << "\n"; } }

Whats wrong in my code ITS FOR QUESTION C

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    do you like want downvotes or something? Please format your code

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain how to do problem D with binary search, i tried but couldn't find a way to do it

»
2 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Can anyone please explain D to me in simple terms? Would be really grateful as I'm understanding parts of the solution but not whole. Thanks.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why my solution to Problem C was accepted during the contest but now shows wrong answer on TestCase 14?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because your code fails during System testing on that test case

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In contest, I got Accepted at the problem D, but when the system tested I got TLE on test 8, but in contest it passed :(. The only thing that I changed today was instead of long long I put int and passed. Why that happened?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    During the contest, not all test cases are run. You would have got the correct answer for the tests that were run during the contest. After the contest was over, when all test cases are run, there must be some test cases in which your code didn't run in time. Changing long long to int would have solved the problem because computation on integers takes about half as much time as computation on long long integers. This is because in some machines, the size of the CPU register is 32 bits and long long takes 64 bits. I think it is also dependent on the compiler but not sure.

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Question F can be solved in O(n^3) without the log factor. And according to my solution, once we got the permutation, we need not check it again whether it satisfies with the input segments. My submission

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do we get solution of these in java as well??

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1343/submission/77564353 This is my solution for D which I submitted during contest. It gave me TLE in system testing on TC11. Now i copied exactly the same code and submitted it after the contest(and after the system testing) https://codeforces.com/contest/1343/submission/77619357. This is the link for the same. It is Accepted by the system. moreover i have submiited the same code 3 -4 times after contest it is showing AC every time. Now can somoene please explain to me why is all this happening and if my code is AC will i get marks for it??

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    plz organizers revert to this vovuh[user:vovuh]

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretty good editorial!!!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

when will the ratings be updated??

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

when will rating changes update??

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody state and explain a binary search algorithm for problem D?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

include<stdio.h>

int sign(int a,int b) { if((a<0&&b<0)||(a>0&&b>0)) return 1; return 0; }

int max(int a,int b) { if(a>b) return a; return b; } int main() { int T; scanf("%d",&T); while(T--) { int n,i; scanf("%d",&n); int a[n]; long int sum=0; for(i=0;i<n;i++) scanf("%d",&a[i]);

for(i=0;i<n;i++)
{
    int cur=a[i];
    int j=i;
    while(j<n&&sign(a[i],a[j]))
    {
        cur=max(cur,a[j]);
        j++;
    }
    sum+=cur;
    i=j-1;
}

    printf("%ld\n",sum);
}
return 0;

}

for question 3 code in c

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone please tell me why I am getting wrong answer on test case 4 in problem E

My Approach :-

  1. Find all the edges on shortest route from a to b using bfs

  2. Find all the edges on shortest route from b to c using bfs

  3. Sort the price array

  4. Assign lowest prices to common edges in path from a to b and b to c

  5. Assign lowest prices among the prices left to remaining edges in routes

Code Link :- https://codeforces.com/contest/1343/submission/77562702

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This algorythm simply does not give the optimal assignment.

    You would not have to find the shortest route from b to c, but instead the shortest path from any vertex in path from a to b, to c. But considering that the part from that vertex to b counts twice. So you end up with the turorials solution.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you please explain a little more why my method is not giving optimal assignment. Or give any test case on which it does not give optimal solution.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Assume graph, with edges a-x, x-c, x-x1, x1-x2, x2-b, and some path from b to c which is not the one over x, but one element shorter than that path.

        With your algo you find cheapest assignment of all nodes in path a-b-c. But assignment for path a-x-b-x-c can be better, depending on p[] values.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Okay! I got it now. I didn't considered the case when there are multiple shortest path from b to c. Thank you very much for taking out time to clear my doubt.

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Why aren't editorials posted here?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Video Solution For problem A , B , c and D is in this playlist : Your text to link here...

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me to understand Problem C statement in a simple way? Thanks in Advance :)

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It asks you to find a subarray of a, the subarray should be like "positive number, negative number , positive number, negative number ......" or "negative number, positive number, negative number , positive number ......", you wanna find the longest subarray of a, but the longest subarray may be multiple and you have to find the longest subarray with maximum sum.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In 1343A why if I place break statement after if loop it's not working??

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For E i tried running bfs from a to b and then b to c and marked the used edges in a map and then counted edges having frequency two = repeated_edges and added these many least weighed edges twice and others once from the weight array but it is failing on tc — 4 case 320 can someone please point out the error.

https://codeforces.com/contest/1343/submission/77633200

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    use this test case draw on paper and think why it failed. I was facing exactly the same issue.

    1
    6 6 1 5 6
    1 2 3 4 10000 20000
    1 2
    2 3
    3 4 
    4 5
    2 5
    2 6
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for replying but my code is giving correct output for the test case u gave.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

vovuh IN problem: (F) Restore the Permutation by Sorted Segments

for last test case
5

2 2 5

3 2 3 5

4 2 3 4 5

5 1 2 3 4 5

why 1 4 3 2 5 is wrong answer (correct as per test case:2 5 3 4 1)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got it. sorry i bothered you

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you explain in detail why the permutation is wrong?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you have to choose some r between 2 to n according to that 5 can not occur at last position as it is part of every segment

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        My approch was to find element with frequency 1 in all segments that could be the last elemnet of our permutaion(if only one element than it is last for sure)

        remove that segment keep repating this until we get array of n-2

        and I have to check for the order of last 2 remaing elements some how which will be our first and second

        but I cound't figure it out

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Actually I can not solve the problem independently. So I am so sorry that I can not help you.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E I used bfs from a to b and stored all the edges in this path , similarly, I did a bfs from b to c and stored all edges in this path. Finally, since I had all the edges count from a->b and b->c I simply sorted the count of these edges and gave the least edge weight possible to edges with most repetition. I don't realize what is wrong is this approach, it's giving WA. Here is the link to my code. Please if someone can explain what is wrong in this approach.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone please tell me what is wrong in my BRUTE FORCE (quadratic) solution of Problem D:

#include<bits/stdc++.h>
using namespace std;

int numberOfChanges(vector<pair<int, int>> v, int k){
    int sum= 0;
    for(int i=0; i<v.size(); i++){
        if((v[i].first+ v[i].second)==k) sum+=0;
        else if(v[i].first >=k && v[i].second >=k) sum+=2;
        else sum+=1;
    }
    return sum;
}

int main(){
    int t;
    cin>>t;
    while(t--){
        int n, k;
        cin>>n>>k;
        int A[n];
        for(int i=0; i<n; i++){
            cin>>A[i];
        }
        vector<pair<int, int>> v;
        for(int i=0; i<n/2; i++){
            v.push_back(make_pair(A[i], A[n-i-1]));
        }
        int count, min_count=INT_MAX;
        for(int i=2; i<=2*k; i++){
            count= numberOfChanges(v, i);
            if(count<min_count) min_count= count; 
        }
        cout<<min_count<<"\n";
    }
    return 0;
}
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

min(ai,an−i+1)+1;max(ai,an−i+1)+k , why is the left side not mini(ai,an -i + 1) — 1, why +1

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    let {a[i],a[n-i+1]} be the pair of elements, then whats the minimum sum of this pair possible by replacing at most 1 of the two elements so the operation cost is 1, so we will take the minimum of the two pair unchanged and will change the maximum of the pair to 1 as the minimum number we can replace to is 1. So it becomes min(a[i], a[n-i+1])+1. Hope it helps.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone (maybe vovuh) please look my solution of D and help me hack this solution, if its possible!

Idea is very simple: Just try some values of sums (i.e. x) close to K, along with some most frequently occuring sums.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please help me what is wrong in my solution for D (Brute Force), I'd be grateful:

    #include<bits/stdc++.h>
    using namespace std;
    
    int numberOfChanges(vector<pair<int, int>> v, int k){
        int sum= 0;
        for(int i=0; i<v.size(); i++){
            if((v[i].first+ v[i].second)==k) sum+=0;
            else if(v[i].first >=k && v[i].second >=k) sum+=2;
            else sum+=1;
        }
        return sum;
    }
    
    int main(){
        int t;
        cin>>t;
        while(t--){
            int n, k;
            cin>>n>>k;
            int A[n];
            for(int i=0; i<n; i++){
                cin>>A[i];
            }
            vector<pair<int, int>> v;
            for(int i=0; i<n/2; i++){
                v.push_back(make_pair(A[i], A[n-i-1]));
            }
            int count, min_count=INT_MAX;
            for(int i=2; i<=2*k; i++){
                count= numberOfChanges(v, i);
                if(count<min_count) min_count= count; 
            }
            cout<<min_count<<"\n";
        }
        return 0;
    }
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      your function counting the changes is incorrect:

      eg. K(as per given in problem) = 3, v[i] = {1, 1}, k = 5. Here, changes required are 2(i.e. {1, 1} -> {2, 3}), but your function counts only 1 change.

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Yes, figured that out. Can you please tell me the correct conditions for counting changes? Are these correct:

        if((v[i].first+ v[i].second)==x) sum+=0;
        else if((v[i].first >=x && v[i].second >=x) || (x>(max(v[i].first ,v[i].second)+k))) sum+=2;
                else sum+=1 
        
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You can refer my solution for the correct conditions.

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

What is the proof for E, that the optimal path always looks like this :a→x , x→b, b→x and x→c ?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let the paths $$$a = v_1 ... v_n = b$$$, $$$b = v'_1 ... v'_m = c$$$ be optimal. Choose minimal $$$i$$$ such that $$$v_i \in {v'_1 ... v'_m}$$$, say $$$v_i = v'_j$$$. $$$i <= n$$$ since $$$v_n \in {v'_1 ... v'_m}$$$. Let $$$P_1 = (v_i, ... ,v_n), P_2 = (v'_1 ... v'_j)$$$. Let $$$rev(P)$$$ for path $$$P$$$ be the reverse of that path.

    There are cases:

    $$$P_1 \not = rev(P_2)$$$. WLOG say the length of $$$P_1 \geq $$$ length of $$$P_2$$$. Then we can replace the $$$ab$$$ path with $$$v_1, v_2 ... v_{i - 1}, rev(P_2)$$$. This new $$$ab$$$ path is not longer then the old $$$ab$$$ path so we can do this.

    $$$P_1 = rev(P_2)$$$. Then take $$$x = v_i$$$ and we have paths $$$a \rightarrow x$$$ is $$$v_1 ... v_i$$$, $$$x \rightarrow b$$$ is $$$v_i ... v_n$$$, $$$b \rightarrow x$$$ is $$$v'_1 ... v'_j$$$ and $$$x \rightarrow c$$$ is $$$v'_j ... v'_m$$$.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good editorial

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hey can anyone explain the editorial of problem E in detail?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1343/submission/77590860 problem D, can anyone tell me an anti-testcase?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

(if dist(a,x)+dist(b,x)+dist(c,x)≤m). can anybody please explain this line to me in editorial of problem E?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I post a reply to someone below. Hope you work out the problem after seeing my post. Thanks very much.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you also tell me some kind of proof that why this a→x , x→b, b→x and x→c path is always optimal, in the editorial it's written that this is it no proof given, if iam missing some points please highlight (vovuh)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally reached expert...Thanks for the contest.. Qestion D was really nice ..

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem E:why is the condition dist(a,x)+dist(b,x)+dist(x,c)≤mnecessary?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because the length of p is m, so the length of the array containing prefix sum of p is m. You may get runtime error if dist(a,x)+dist(b,x)+dist(c,x) is greater than m

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      got it,ty!

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How can we be sure that dist(a,x)+dist(b,x)+dist(c,x) is not the answer?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If we can find a smaller dist(a,x')+dist(b,x')+dist(c,x'), the current dist(a,x)+dist(b,x)+dist(c,x) is not the answer. so just for each point update the minimum and print it.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          Finally, I know why we should ignore da[x] + db[x] + dc[x] > m case. Because we assume x the first point where path a->b and b->c intersects, which means that path a->x, b->x, c->x don't have common edges. so the sum of their length can't be longger than the total edge number m. If da[x] + db[x] + dc[x] > m, then it cann't be the intersection point we need to find

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks! That is right. You get a deeper understanding than me!

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I created a test case which hacked the solution in tutorial. Is the std wrong or my test case illegal?
the test case: 1 6 2 1 3 3 1 3 4 2 1 4 2 2 5 2 2 6 The std output nothing. Thanks very much for testing my test case

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I was thinking the same about problem E. But I was and still in doubt that How we can assure that path a -> x and x -> c will not have any common edges.

As the tutorial is saying: "like three straight paths with one intersection point x", I am not getting this, How can we assure about three straight paths always?

Could somebody help me with this? Thanks!.

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    x->c can have edges which are common with x->a or x->b . If it's x->a, then we have 2 cases: 1) x->c has all edges from x->a (path is x->a->c and common edges are the edges from x->a) or 2) there is some point y in between 'a' and 'x' such that the edges from x->y is common (i.e x->y->c, a->y->x and common edges are the edges from y->x). In the first case, if 'x' is not 'a', then having x=a will always give better answer as x->a +x->b + x->c will be smaller and you have a longer prefix x->b. In second case, you can have x=y which will give a smaller answer because of the same reason mentioned above. Similarly, you can work out for edges which are common to x->b. The point is that the algorithm will find surely find the optimal answer (x=a or x=y in above case) if there exists one.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As a matter of fact, they will have cwommon edges. I saw a comment above which called these "extra" common edges -'over-estimations'. It can be seen intuitively, that if you choose an intersection, which has these 'over-estimations', that can never be the optimal answer. Take the second test case from the problem statement. If we choose node '4' as the intersection point, then the path will become, (1-->4), (4-->5), (5-->4), (4-->7). Here the path (4-->7) has a common edge with the path (1-->4). Oh and all these are the shortest paths between any two nodes BTW.

    Now why isn't node 4 an optimal intersection? It's because, if you try and see things intuitively, we're using some edges which are more than necessary. The path in common has two nodes, 1 and 7. If you study this clearly, you'll see that using either 1 or 7 as the intersection has a more optimal result than choosing 4. It's plainly because, these nodes are being chosen more than necessary when node 4 is chosen as the intersection. This is the same case for all the nodes, which if chosen as an intersection — has these 'over-estimations'. Making the nodes which lie in the common path, a much more suitable option for an intersection.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone please explain me problem C,i think the problem says to first find the maximum length subsequence and of those return the maximum sum possible, soo in 3rd test case of problem -2 8 3 8 -4 -15 5 -2 -3 1 the maximum length subsequence is -15 5 -2 i.e. 3 therefore answer should be -12 but its 6

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How can problem C can be solved using dynamic programming

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I have implemented a solution of problem D in O(nlogn). Here's the link here It is lot more efficient(both logic wise and memory wise) than the method described in the tutorial. It does not depend on K. Most importantly if the constraint on k was 10^9(which can easily be the harder version of this problem), then this would still work in the same time, whereas the one in the tutorial will fail miserably. This is because if k is in 10^9, then you cannot make an array of the size 2*k.

My solution takes palindrome sums in an array and then sorts it. Then I check for the range of each pair which can be obtained by a single replacement. Now, I find all the sums which lie in this range using upper_bound and lower_bound functions(which is binary search basically). It takes O(logn) to do that. I mantain another prefix array parallel to the sorted array of the sums. After all the pairs are done, we process the prefix array. Then its just the usual calculations. We loop through all the sums and check the no. of pairs that needs 0,1 and 2 replacements to achieve that sum. We find the minimum of those replacememts, keeping in mind that the answer cannot be greater than n/2.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the following code in Problem C — auto sgn = [&](int x) { if (x > 0) return 1; else return -1; }; how auto keyword is used here and materials to read to understand this code. Please!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please explain why I am getting WA on E Submission Link

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Final ab & bc paths not always necessarily shortest paths between a-b or b-c. One of the longer paths could have more vertexes in common thought better weight sum. Plus, Dijkstra has o(n*ln(n)) complexity and should fail on big inputs since, as stated in the editorial, for this problem it is sufficient to make liner 5 passes.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have actually calculated shortest paths from a-b ,b -c, a-c , if path from len(a-b) = len(a-c) + len(b-c) then c occurs in one of the shortest path from a to b and that path should be considered for optimal soln. otherwise the path from a-b (shortest ) and b-c shortest is considered .Though due to TL the soln might get TLEd but I want to know If the above approach is incorrect!! :)

      BTW, Thanks for the reply !!

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        Yep, it is incorrect. Shortest a-b path does not always appear in the best possible solution. If you have p[weights] = {1,..(9 ones)..,1,100,100,100...} and graph: 1-(5edges)-6-(5edges)-11, and from vertex 6-(6edges)-x=a,c (x connected to both a and c by 1 edge each), then a,b,c = 1, 6, 7. Shortest paths a-b and b-c are 5 vertexes each. But since you have only 9 ones, your result with the shortest paths would be 109. But if you'll go through point x, your result ould be 1+6*2+1 = 14. Or through the point a with result 12.

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Or imagine rhombus with vertexes a,b,c,x. With 10 edges between a and b, 10 between b and c, and with 6 edged between each pair: a-x, b-x, c-x. If you have only 19 ones and a lot of hundreds among edge weights, your cheapest path would lay through point x, and it has no common edge with either of shortest paths a-b or b-c.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Got your point !! Thanks for the detailed explanation !!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice editorial! I really enjoyed the problems.
Here is a submission for problem F with comments. I think it's clear and easy to understand . But if there are questions feel free to ask. https://codeforces.com/contest/1343/submission/77673993

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
#include<bits/stdc++.h>
#include<cmath>
using namespace std;
#define long long int
int power(int y,int x)
{
    int p=1;
    for(int i=0;i<x;i++)
    {
        p=p*y;
    }
    return p;
}

int32_t main()
{
    int t,p=2,i;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for( i=0;i<=n;i++)
        {
            if(fmodl(n,(power(p,i)-1))==0)
            {
                cout<<n/(power(p,i)-1)<<endl;
                break;
            }
        }
    }
}

why isnt the code working?? (A.Candies)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

HI I have a question related to Problem A:

geometric sequence tells that = 2^(k-1)

but in the tutorial you said: ((2^k)-1)

anyone please explain???

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How Problem D can be solved using Binary search?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I built a vector that holds the minimum value every pair can take with one change, and a vector that holds the maximum value every pair can take with one change. Fix a target $$$1 <= x <= 2k$$$ that you want every pair to equal after your changes. The number of pairs whose min is > x will require 2 changes, as will the number of pairs whose max is < x. You can binary search for the number of pairs that fulfill these conditions, using something like lower_bound(mins.begin(), mins.end(), x). You can also see that a pair cannot fulfill both of these conditions simultaneously, so we don't double count.

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Can anyone please make a video tutorial on problem E ?? It can be helpful for many of us...

Thanks in advance.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please explain how to solve the problem in java

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

auto sgn = [&](int x) { if (x > 0) return 1; else return -1; }; what does this code do ?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    If x is positive return 1,else if x is negative return -1. You can read more about it here.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Let's make +1 on this segment using prefix sums (make +1 in the left border, −1 in the right border plus one and then just compute prefix sums on this array)

what do you mean by this? Please elaborate

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone check why my solution is getting wrong answer in test 3 for problem E
https://codeforces.com/contest/1343/submission/77693562

»
2 months ago, # |
Rev. 5   Vote: I like it -10 Vote: I do not like it

In problem F the permutation is not necessarily unique! In general, if all given intervals are of length 2 the permutation can be reversed and still be correct. Those should be the only 2 possible permutations

One can also reconstruct the array from the last element to the first: The last element can only occur in one segment and there can be at most two elements which occur only once (the last and maybe the first). So if there is only one element it has to be the last. If there are two we can just test both but fixate the other one as the first element. If the first element is fixed we will only find one other element which occurs only once at every moment so we will find at most two permutations (those are the only two possible permutations). We can check both for correctness and print the right one.

My Implementation: 77696766

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I said that the permutation can be uniquely restored if the first element is fixed. Reread the editorial please. I didn't say that there is only one possible answer.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it -8 Vote: I do not like it

      Thanks for the clarification, though I don't get why someone would downvote MZienni. This sentence: "One interesting fact: if such permutation exists then it can be restored uniquely." really bear some ambiguity.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks in advance. can anyone tell me why my code gets TLE for problem E (in test 2). my code complexity is O(mlog(m)) per test case . idea is i calculated shortest path from a to b and from b to c . and in this shortest path i counted the frequency of the edges.then sorted based on the frequencies .and provided lowest number to the most frequent edge and so on. code : https://codeforces.com/contest/1343/submission/77705696

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem, 1343E — Weights Distributing, am getting wrong answer on test 3, Error says: 35th numbers differ — expected: '4', found: '3' Any idea why? Not able to get the failing test case as it was too long My solution link

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This initialization of ans=cost[-1]+1, what does it do? In C++ we would need to initialize it with ans=1e18

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thanks for spotting the issue. I took the last index of prefix sum array and added one assuming that would be the max possible value, but did not consider the fact that there were 2 prefix sum additions in the answer. Did submit a fix, and it passed the 3rd test case, but got a TLE at 19th TC. Thank you !

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why difficulty of problem F is 2800? lol, it is strange, who set difficulties?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the significance of this statement "It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 (∑n≤2⋅105)"

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Since all testcases must be finished within the timebox of one second it is important to know how much data must be processed. Without that statement the sum of n over all test cases could be up to 1e5 * 1e4 == 1e9 which is significantly different.

»
2 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

What's wrong with B problem editorial explaination?
In Editoral vovuh wrote that->(This array is almost good except one thing: the sum in the right half is exactly less than the sum in the left half. So we can fix it easily: just add n/2 to the last element.)

But in tutorial code this line is look like ->
(cout << 3 * n — 1 << endl;)

How (3*n — 1 == n/2)?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    For the other elements the output is cout << i * 2 - 1 << " ";

    So, adding n/2 for the case that i==n/2 we get cout << 3 * n - 1 << endl

    Note that n is devided by two earlier.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, in problem C, vovuh has something called sgn, is that a function or something else? Could someone explain it or what it is called so I could find a tutorial?

Thanks in advance

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's short for sign: +1 or -1. And code is there too:

    auto sgn = [&](int x) { if (x > 0) return 1; else return -1;

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the reply, I have seen the code, but I have never seen this syntax, by this I mean [&] being in front of (int x), because this does not seem like a function.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

1343E - Weights Distributing Can anyone help me in my code it says wrong ans for test 4 https://codeforces.com/contest/1343/submission/77737942

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

For problem E, why can we ignore dist(a,x)+dist(b,x)+dist(c,x)>m case? Don't say array index out of range, we can use other methods compute this

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    What do you mean? We can't ignore it: a, b, c (and x) can all be even the same point. And 0 <= m is the solution.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      oh, some typo. I mean dist(a,x)+dist(b,x)+dist(c,x)>m case

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        We can't ignore it either: for graph 1-2-3-4-5 (m = 4) in case a=c=1, b = 5 the answer is sum(dist()) = 2*m > m.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          but in the sample code:

          if (da[i] + db[i] + dc[i] > m) continue;
          
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh, this means that point x is too far from a,b,c to be solution and pref[da[i] + db[i] + dc[i]] index would be out of range.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
              Rev. 2   Vote: I like it +1 Vote: I do not like it

              Finally, I know why we should ignore da[x] + db[x] + dc[x] > m case. Because we assume x the first point where path a->b and b->c intersects, which means that path a->x, b->x, c->x don't have common edges. so the sum of their length can't be longger than the total edge number m. If da[x] + db[x] + dc[x] > m, then it cann't be the intersection point we need to find

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Did anybody solve D using Segment Tree, is it possible?. UPD Found

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried to solve D using Segment Tree, but got tle on 2nd test case.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, I found out why I got TLE. At first I used memset function instead of build_tree to init seg tree. The array is very large(4e5 * 4) so it took too much time to init.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I implemented a java-based segment tree solution to D.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me about assert function more deeply? this function is being used by editorial solution maker??

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In c++ assert is a function-like macro. It is used for early error detection: if assert() fails — there some logical mistakes or misspell.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem A?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    x+2x+4x+⋯+2^(k−1) x = n. Here if u take x as common then 1+2+4+⋯+2(k−1) = n; for left side 1+2+4+⋯+2(k−1) = 2^k — 1; so from here you can easily find x by iterating over k

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't understand the tutorial of F. Any help would be appreciated.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First number in permutation would always be in 1 and only 1 segment of size 2. Grab all elements from 2-sized segments and check if there can be formed permutation if it would be the first element: first, exclude it from every segment where you find it — after this, there must be only 1 segment with size "1". This will be the second number. Take this number and exclude it from every segment, now there must be only one segment of size 1. This will be the third number... and so on. When found sequence — check it. If it's good — output, else search next number to be first.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the solution of D, can anyone explain why he's making the following assertion?

assert(max(l1, l2) <= min(r1, r2));

Thank you in advance!

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem E, I was doing bfs from a to b, and then b to c, and storing the edges in vector along with maintaining the frequency of each edge in a map.
Then I just keep assigning the lowest cost to the edge which occurs most times.
But it failed on the 4th test case.
Can anyone help, why this approach fails?
Or the approach is correct and I might be making some noob implementation mistakes?

Here is the solution, if anyone needs a look through it.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone did problem D ? with binary_search approach?..please help

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why pref means at most 1 replacement instead of exactly 1 replacement in Problem D?

I've tried to understand it for three days.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because when we increment one in the segment: [min(a_i, a_{n-i+1}) +1, max(a_i, a_{n-i+1})+k )

    We are also incrementing the position a_i + a_{n-i+1} and the x made by a_i + a_{n-i+1} we already have for free.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, I totally understand! Thank you very much!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give me the python code to make the prefix array for problem D?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You should really google it — it's a basic concept — it's basically a string of simple code.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah...I googled it and funally realized it :D

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody tell me why I am getting TLE in question E.

I am new in c++ so maybe some kind of optimization is required ? time complexity of this code is under constraint i think so . Please can anybody look into it.

. . . .

include<bits/stdc++.h>

define u_map unordered_map<int,int>

define forr(i,a,b,c) for(int i = a ; i < b ; i += c)

pragma comment(linker, "/stack:200000000")

pragma GCC optimize("Ofast")

pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

pragma GCC target ("avx2")

pragma GCC optimization ("O3")

pragma GCC optimization ("unroll-loops")

using namespace std;

void bfs(int a, vector graph[], bool visited[], vector &mapping) {

list<int> queue;
queue.push_back(a);
visited[a] = true;
int iter = 1;
while(!queue.empty())
{   

    int front = queue.front();
    queue.pop_front();
    for(auto k : graph[front])
    {            
        if(!visited[k])
        { 
            mapping[k] = mapping[front] + 1;
            queue.push_back(k);
            visited[k] = true;
        }
    }
}

} void bfs_setup(int a, vector graph[], int n, vector &mapping) { bool visited[n+1] = {false};

bfs(a, graph, visited, mapping);

} int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while(t--) { int n,m,a,b,c; cin >> n >> m >> a >> b >> c ; deque weights(200005,0); forr(i,0,m,1) { cin >> weights[i]; }

    vector<int> graph[200005];
    forr(i,0,m,1)
    {
       int u,v;
       cin >> u >> v;
       //u--;
       //v--;
       graph[u].push_back(v);
       graph[v].push_back(u);
    }

    vector<int> a_map(n+1,0);
    vector<int> b_map(n+1,0);
    vector<int> c_map(n+1,0);

    bfs_setup(a, graph, n, a_map);
    bfs_setup(b, graph, n, b_map);
    bfs_setup(c, graph, n, c_map);

    sort(weights.begin(), weights.begin() + m);

    forr(i,1,m+1,1) weights[i] = weights[i-1] + weights[i];
    weights.push_front(0);


    int ans = INT_MAX;

    forr(node,1,n+1,1)
    {

       if(b_map[node] + a_map[node] + c_map[node] <= m) ans = min(weights[b_map[node]] + weights[b_map[node] + a_map[node] + c_map[node]], ans);
       else continue;
        //cout << node << " " << ans << " " <<  b_map[node] + a_map[node] + c_map[node] << endl;


    }
    cout << ans << endl;

}
return 0;

}

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Got it.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why Problem E can't be solve with two bfs? one bfs from a to other nodes and other bfs from c to other nodes and then I can simulate the junction point of a and c with this two distance, but it is showig WA

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem Constant Pallindrome, I am finding range of x(on condition that atmost one element of pair can change)[L,R] and storing frequency of sums of pairs. Sum with max frequency which lie b/w [L,R](which equals f) is the final x. Therefore answer will n/2-f. But getting W/A :( Does approach have some fault?

To find the range:

minn=min(minn,max(arr[i],arr[n-i-1])); maxn=max(maxn,min(arr[i],arr[n-i-1]));

l=1+maxn r=k+minn;

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the Problem E, it says:"There are no loops or multiple edges in the given graph". Does the "loops" here actually mean "self loops"? In my opinion, the second example contains "loops". Am I wrong ?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, the meaning is "There are no self loops or...". Of course, there are loops in the graph.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Easy implementation of F

78569543

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me why are we doing +1 on the left border and -1 on the right border?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the 373th TestCase of Test 2 ?

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Wouldn't the complexity of solution provided for F be O(n^4*logn) as comparing sets take linear time? MikeMirzayanov

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i can not understand the following line of problem c. i tried to realize for the last couples of days , is there any kind soul to explain with some examples please

changing the order of the remaining elements.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem D, I've implemented the author's solution but with more comments and verbosity. In case it helps anyone. https://codeforces.com/contest/1343/submission/79363150

»