Автор BledDest, история, 7 лет назад, перевод, По-русски

Привет, Codeforces!

21 сентября в 18:05 по Москве начнётся Educational Codeforces Round 29.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Раунд будет нерейтинговый. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной готовили Михаил awoo Пикляев, Владимир vovuh Петров и Михаил MikeMirzayanov Мирзаянов.

Удачи в раунде! Успешных решений!

  • Проголосовать: нравится
  • +172
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

For a joke, How to solve the terrible problem A?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    As what I said, HOW TO SOLVE THE TERRIBLE PROBLEM B??

    My idea is: priority_queue make all the value of (abs(w[a]-w[b]) (1<=a,b<=2*n,a!=b)) into the queue, and choose the national w[a] — w[b], then the (n-1) pair of (w[a] — w[b])'s sum is my answer

    Is'it something wrong with my idea? I need all of your help,thanks!

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      You have n*(n-1)/2 ways to pick single guys. So for every combination calculate new value and take the minimum.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      There is open-hacking for 24 hours, please don't discuss problems before this phase ends.

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +49 Проголосовать: не нравится

        i think we should discuss the problems because we can get more ideas for hacks. It is not rated anyways,so i don't see any problems

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The idea is wrong.because the value “a” or “b” will be chosen more than once. However,a man only belongs to one ship. In fact,we should try to pick two people out and do not consider them. Now we have 2n-2 people.we sort the array by weight. After sorting .the answer is the sum of whose index is even plus the sum of whose index is odd.

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        But i marked both whose diff is minimum...but still showing error...?? as shown: (a[i]-a[j],{i,j})

        if(!(vis[i] || vis[j]) ans+=a[i]-a[j]

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          Maybe you should try to think about this example. N = 3 1 5 6 20 1000 2000 And ans should be 18

          Your output is 20?

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            TvT...I should first choose two single.And choose double two by two, Igot it now, thank you!

»
7 лет назад, # |
  Проголосовать: нравится +167 Проголосовать: не нравится

uwi be like :

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    If uwi is in hacking mode, we will not need system testing after the round.

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Another ROUND!!!!where u can relax about Rating.The more u dont want to care about ratings the more u start to care....Why rating is so cruel!!!!!!!!!!!

»
7 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Is it rated?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    No, the Educational Codeforces Round is based on ACM rules, so it is unrated.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      Pardon me, but how do those two go together?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится

        All the rated rounds are based on Codeforces rules, so if the round isn't based on Codeforces rules, it's often unrated.(Maybe I was wrong,it is unrated just because it's an Educational round).

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +69 Проголосовать: не нравится

This question is for uwi and halyavin.

Just out of curiosity, hacking solutions is a way to learn something new or you guys just pass your free time by hacking hundreds of solutions in Educational rounds ?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +53 Проголосовать: не нравится

    not much time needed, it's probably a script that automatically download source code , compile and run it , they only need good hacking tests , or if you feel lazy just randomly generate some tests and compare the output to a non hackable solution ,you can check TLE/RE errors too.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      That's a legend thinking approach !

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Wait, I never realised you can download solutions in text form during educational rounds! Well, well, well...

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +60 Проголосовать: не нравится

    I do learn new things while trying to hack solutions. This type of thinking helped me to construct the worst test case for my own contest problem recently.

»
7 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

I need to check the rules of ACM-ICPC. Can anybody send the link?

»
7 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

i hope someday , somebody write a contest about DOTA 2 it would be so nice :D

»
7 лет назад, # |
  Проголосовать: нравится +60 Проголосовать: не нравится

Getting Hired.. uwi mode

»
7 лет назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

When is this and is it rated?

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Hi , This will be my first Codeforces contest !

»
7 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

The days are gone forever when our enemies could blackmail us with nuclear bombs.

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Time to BOMB test case #3 of Problem B

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

Test 14 in E?

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

What is test 14 in E?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

    If you are compressing the values, you should add (r[e] + 1) to the values to compress, at least I did this and passed

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can we solve that questions using Compression and BIT ???

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I probably wrong , but i don't think so, we can't get the minimum of a range with BIT and do range updates at the same time.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        My solution is:
        suppose the elements l[e], r[e] <= 105
        If you add 1 to every element in the range [l[e], r[e]] for every e , you can check if a range is good checking if the minimum element in the range is 1.
        Because if the minimum is 1 after deleting that range we gonna have at least a 0, what means that the number of moments increased.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Any reason why compression with l[i],r[i],l[i]-1,r[i]+1 works?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Basically, you have to see that some number may be 'lost', what I mean is that when we are compressing we are not considering the elements l[e] < X < r[e], for every e, so we can create a case were there is more that an range loses one of it's elements and after this our algorithm gives the wrong answer, but actually we don't have to take exactly all the X, if this situation gonna happen is because of there is two ranges with some intersection, so the values that matters are the borders of the ranges, it's not a good answer, but if it's not clear I can try to explain in a better way

  • »
    »
    7 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +14 Проголосовать: не нравится

    this is a test like it

    3

    1 3

    5 7

    2 6

    correct answer:-1

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E? (and why i'm getting RTE with a simple segtree?)

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    the seg tree dimenison is too little,it should be 4*2*MAXN

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Oh, i see, thank you :)

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I tried to solve it using segment tree with range sum updates and range min query first i do coordinate compression and then i will update from 1 to n all queries with +1 to their corresponding range and then i will start from 1 to n and at an i th position i will remove that update by adding -1 to that range and check if in that range iam getting any 0 if NO THEN that is a valid ans as it is not affecting others's //(using range min query ) but the problem is i was unable to implement it in time .and also can't we implement a segment tree with range sum updates and range min queries??

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You don't need range min queries. What you need to know — is there any element on range equal to 1. Just access each element of your tree and build an array of prefix sums with amount of 1's on prefix, like this: prefixSum[i] = prefixSum[i-1] + (tree.get(i)==1). Then some segment [l; r] is an answer if prefixSum[r] - prefixSum[l-1] == 0

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          tnx , cool idea to solve that question(we don't even need a segment tree we can use partial sum trick ) . btw i have a doubt in general not regarding this question but can we code a segment tree with lazy propagation such that we can do range sum updates (i.e we can add a value v from l to r ) and we can do range min queries (i.e we can find minimum in that range from l to r ) in logN time .

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I tried to solve D using treap, I think it is an overkill but it should work! I got RE on test 10 and 11 ... it's weird

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    I'm not sure, but it might be because you put the priorities as rand () (up to 32000 on CF compiler). If you extended the set of possible values, the possibility of two priorities being equal on adjacent positions (which most treap implementations consider 0) would dramatically decrease. I use treaps with rotations and in that implementation in function erase, if you have two neighboring nodes having the same priority and do not pay special attention to the case, you might end up with a loop. Let alone that such small values cut off the idea of normal distribution, so even if you hadn't gotten RE, you would've gotten TLE. Try to switch that line of the code with something like p = (rand () << 15) + rand ().

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      You are right! It worked. I completely forgot about that detail.

      I must say, I have been very lucky because I have always used just "rand()" in these kind of problems.

      Thanks!!

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Actually, I did the same overkill :)

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How can you reverse the segment using treap?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      Each node should contain a bit which indicates whether you need to flip it or not. To flip a segment, split the treap into three parts (propagating the flips as needed), change the flip bit on the middle part, and then merge the parts.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +58 Проголосовать: не нравится

      Another approach is to build two treaps. One for the initial array and another for the reversed array. If you have to reverse a segment you swap the corresponding segments in these treaps.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

very interesting problemset.

»
7 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

I laughed so hard when I saw SPFA_THE_BEST_ALGORITHM's nickname, knowing it is part of the solution to problem F :D

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Simple solution to problem E, no data structures needed (other than array) 30592259

PS: I hope nobody hacks it !

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    just found a little hack, if you fix it I would try again, although the solution approach seems kinda correct to me :)

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

      Sure ill try to fix it later (order needs to be x increasing then y decreasing), i also believe it to be a correct approach, but i seem to be unable to code without bugs lately.

      Edit: fixed version, with the change previously described 30727493

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there solution for D easier than treap solution?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    Do the operation backwards. For every b, do the operations in reverse to find where the number would have started. Then print that number. Complexity is O(m * q).

»
7 лет назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

Hi guys, I did join this website yesterday. and I am really happy for this. Few minutes ago I did submit my attempt to solve the problem A but I see runtime error on test1.

I am quasi sure that my solution is working well. I did use java. should I stop using things like demanding the user to enter an input "java.util.Scanner" ? please help me!

The solution is bellow :

package javaapplication7;
import java.util.Scanner;
public class JavaApplication7 {
    public static void main(String[] args) {
        //Reading user's number and adding leading zeros 
        Scanner s = new Scanner(System.in);
        System.out.println("Enter the number please");
        Long in = s.nextLong();
        String in_to_str = in+"";
                
        int in_last_index = in_to_str.length()-1;
        String sub_str_to_add = "";
        while(in_to_str.charAt(in_last_index)=='0'){
            sub_str_to_add=sub_str_to_add+"0";
            in_last_index--;
        }
        in_to_str = sub_str_to_add + in_to_str;
       
        //testing whether it's a palindromic or NOT
        int in_len = in_to_str.length();
        int ind_diff=-1;
        for (int start=0,end=in_len-1;start<in_len/2&&end>in_len/2;end--,start++){
            if(in_to_str.charAt(start)!=in_to_str.charAt(end))
            {
                ind_diff = start;
                break; 
            }       
        }
           
        /* the second part of the if condition [in_len==2&&in_to_str.charAt(0)!=in_to_str.charAt(1)] 
        is to treat the case of a number composed of two digits which is not included in the previous test */
        if(ind_diff<in_len/2&&ind_diff!=-1||in_len==2&&in_to_str.charAt(0)!=in_to_str.charAt(1))
        System.out.println("The number "+in+" is NOT quasi-palindromic");
        else 
        System.out.println("The number "+in+" is quasi-palindromic");            
    }   
}

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    Remove "System.out.println("Enter the number please");" and see if it goes away

    Also you are supposed to output only "YES" or "NO".

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

how should i approach problem E? Thank you.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Create a map m which will compress the indices. The interval [l, r] will be transformed to m[l], m[r + 1] - 1. Now either

    • Use a lazy segment tree to add to a range and query the minimum along a range. A TV is redundant iff the minimum number of TV's at any integer point in time from l to r inclusive is greater than 1. This works well if you already have a template prepared. :)
    • Create a cumulative sum table, which will allow you to determine all points in time where exactly 1 TV is working. Now for each TV you can query if any of these points are inside [l, r] with a set. If none of them are inside, then this TV is redundant.
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      There is a simplier solution without indices compression and segment tree:

      The main idea, that TV (l, r segment) is redundant if it fully overlapped by one or two consecutive segments (proof is pretty easy). So algorithm looks like:

      1. Sort all segments in ascending order of r (for equal r in desc order of l)
      2. Iterates over segments, lets look to the set of the segments that already viewed and pick segment with maxL, and segment with maxR (this segments must be different), so segment with max L is redundant only if it overlapped by current segment or by current segment & segment with maxR.

      30588470

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you please explain why indices left — 1 and right + 1 are compressed along with left and right?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I followed the exact same approach but somehow I'm getting a WA. I have used a BIT for the cumulative sum. Getting WA on 16th test case. Here is a link to the code. https://code.hackerearth.com/0ec204e?key=4b7fb07878fac98d3c5bcc41899f3436

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hey! I am new to codeforces. Can anyone guide me ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Start solving problemset starting from Div II A, B. Learn some algorithms and DS and then jump to Div I. Participating in contests is a must. Read other people's solutions and be most important be optimistic.

»
7 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

Because hacking others' solutions is too mainstream.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve the problem D?I have no idea on data structure,could someone give me a little help?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

    Consider the number of queries is smaller in 100, we can calculate for every single query for the operations but not the whole sequence. As we are given the ending position of the number, we can calculate it's beginning position. For the operations,we can consider it in reverse order.

    Let's call the position of the query is now x,and consider the operation done before it become x.

    First. the operation reversed [l,r],then if the x is in [l,r] it should be l+r-x before this operation.

    Second. the operation shift [l,r] ,then if x is in [l,r] it should be x-1 before this operation. but if it's l exactly it should have been r.

    So you can solve the problem in O(nq).

    Sorry for my poor English, if it's still not clear, you can ask again.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      @pb0207, can you give me explanation sample test case for problem D?Problem statement aren't clear to me.Specially first operation isn't clear to me.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        The first operation is a cylic shift which is that all the numbers in the interval [l,r] goes right except the number on the position r which goes to l.

        That means for the array [1,3,2,4,5,6,7,9,8] if we do the first operation to the interval [2,5] , it would be [1,5,3,2,4,6,7,9,8]

        The second operation means to reverse the interval.Which means if you do this operation to the interval,then you can find the previous interval by reading from right to left. And for more formal explanation the number on position l would be equal to number on r,and l+1 equal to r-1 ,etc.

        And for the array [1,3,2,4,5,6,7,9,8],if we do the second operation to the interval [3,7] , it would be [1,3,9,7,6,5,4,2,8]

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          pb0207 Thanks for your time ,consideration and forthcoming response. Sample testcase; - 6 3 5 - 1 2 3 4 5 6 - 2 1 3 - 2 3 6 - 1 1 6 - 2 2 1 5 3

          • for 2 1 3 array would be 3 2 1 4 5 6
          • for 2 3 6 array would be 3 2 6 5 4 1
          • for 1 1 6 array would be 1 3 2 6 5 4
          • for 2 2 1 5 3 answer would be 3 3 1 5 2 Isn't it?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      This helps a lot thanks!

      I was confused with this problem but now i get it! :')

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    As for data structure, you can learn Treap or Splay which can reverse the array.And you can calcultate the final array in O(logn) for each operation.

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Hi pb0207 Do you know a good reference about treap and its reverse operation?? I've read a couple of pages about treap but they don't mention that!

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For problem B, can any body explain why this approach is wrong:

iterate over all pair and find the pair with minimal absolute difference between weights, then delete them and repeat the process.

This gives a WA, any proof why it's wrong.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I also don't understand how to prove these approaches wrong.I know this is an old post but maybe anyone can help as I usually get stuck on these types of wrong approaches.

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

When will be editorial published?

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

For problem E,why segment tree is not able to solve this problem?(I have change the array a for discretization) but I got WA on test 14.

The main idea I do is to add 1 in segment[l,r] and query the minimum value in this segment after all the add operations are done.Then if there is a segment whose minimum value can be greater or equal to 2 ,then this TV set is not needed.

It's that my fault in writing segment tree?But I'm so sure I could at least write a segment tree correctly...This is code...Please tell me what's wrong or just point out the solution itself is not correct...Thanks in advance...

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    i too taught segment tree. but seeing values of array, i solved it in another way. i used binary search. 30619432

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you for reply...But is there any monotonicity for binary search in this problem?I just think it's asking about whether there has a segment which have been covered by other segments completely...

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

        Yes and you can search that segment using Binary search by doing some preoprocessing. let me explain it.

        example:

        3

        1 2

        2 3

        3 4

        lets sort this segments by l and if same then by r.

        array = (1, 2) (2, 3), (3, 4)

        now we will create new vector where we will store working time of tv's based on previous tv.

        for example : (1, 3) (2, 5) as you can see the second segment (l2) is lying inside 1st segment. so we can write this as (1, 3), (4, 5). so here we converted the 2nd segment l to new time which is equal to r1 + 1.

        if r1 + 1 > r2, this means that second tv is totally not needed so we can output this as answer. for example: (1, 3) (2, 3).

        after building this new vector for out previous example it will look like this:

        array = (1, 2) (2, 3) (3, 4)

        newtime = (1, 2) (3, 3) (4, 4)

        now for each segments in newtime find how many segments are there in array. if there are more than one then this segment is not needed. for this use binary search, find the leftmost segment and then find the rightmost segment. count = (rgt — lft) + 1.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone please tell me how to approach the problem B i tried all possible solutions from my side

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

When will the editorial be posted? Hacking phase is over already.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I need editorial of problem F.Can anyone please explain how to model flow network for this problem.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve G?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Sorry for the late editorial, it is published now.

»
7 лет назад, # |
Rev. 8   Проголосовать: нравится 0 Проголосовать: не нравится

anyone can help check whats wrong with my solution for problem E, got RTE for 16th test case. http://mirror.codeforces.com/contest/863/submission/30694287

  • »
    »
    7 лет назад, # ^ |
    Rev. 6   Проголосовать: нравится +5 Проголосовать: не нравится

    The problem is in cmp function. Your comparator must always be like: if cmp(a, b) then !cmp(b, a).

    UPD: And one more mistake is in if-statement in main function.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is there answer?