Kostroma's blog

By Kostroma, history, 3 years ago, In English,

572A - Arrays

In this problem one need to check whether it's possible to choose k elements from array A and m elements from array B so that each of chosen element in A is less than each of chosen elements in B. If it's possible then it's possible to choose k smallest elements in A and m largest elements in B. That means that in particular, k-th smallest element of A is less than m-th largest element in B. So, if A[k] < B[n - m + 1] then the answer is "YES" and if not, then the answer is "NO".

Problem author: zeliboba.

Problem developers: AlexDmitriev, Kostroma.

Solution code: 12873382.

572B - Order Book

First of all the problem may be solved for buy orders and sell orders separately.

The easiest soultion is to use structure like std::map or java.lang.TreeMap. To aggregate orders we just add volume to the corresponding map element: aggregated[price] += volume.

After that we should extract lowest (or largest) element from map s times (or while it's not empty).

Complexity of this solution is O(nlogn).

It is also possible to solve the problem without data structres other than an array. You should just maintain at most s best orders in sorted order and when adding another order you insert it in appropriate place and move worse elements in linear time of s. Complexity of this solution is O(sn).

Problem authors and developers: ArtDitel, yarrr.

Solution code: 12873385.

571A - Lengthening Sticks

Let's count the number of ways to form a triple which can't represent triangle sides, and then we subtract this value from — the total number of ways to increase the sticks not more than l in total. This number is obtained from partition of l into 4 summands (la + lb + lc + unusedl = l), or can be counted using a for loop.

Now we consider triples a + la, b + lb, c + lc, where la + lb + lc ≤ l, la, lb, lc ≥ 0. Fix the maximal side, for example it would be a + la. We'll have to do the following algo for b + lb and c + lc in the same way. The triple is not a triangle with maximal side a + la if a + la ≥ b + lb + c + lc. If we iterate over la between 0 and l, we have the following conditions on lb, lc:

lb + lc ≤ a - b - c + la, 
lb + lc ≤ l - la, 

lb, lc ≥ 0. So, non-negative integers lb, lc should be such that lb + lc ≤ min(a - b - c + la, l - la). If we denote this minimum as x than we can choose lb, lc in different ways (again we divide x into three summands: lb, lc and some unused volume). Also when we fix lb, there are x - lb + 1 ways to choose lc, so the overall number of pair lb, lc is

so we obtain the same formula.

To sum up, we need to iterate over the maximal side and over the addition to that side, then write these formulas, and subtract the result from the total number of different additions to the sides. The complexity of the solution is O(l).

Problem author: Kostroma.

Problem developers: Kostroma, AlexDmitriev.

Solution code: 12873406.

571B - Minimization

We can divide all indices [1;n] into groups by their remainder modulo k. While counting , we can consider each group separately and sum the distances between neighbouring numbers in each group.

Consider one group, corresponding to some remainder i modulo k, i.e. containing aj for . Let's write down its numbers from left to right: b1, b2, ..., bm. Then this group adds to the overall sum the value

We can notice that if we sort b1, ..., bm in non-decreasing order, this sum will not increase. So, in the optimal answer we can consider that numbers in each group don't decrease. Furthermore, in that case this sum is equal to |bm - b1|.

Now consider two groups b1, ..., bm and c1, c2, ..., cl, both sorted in non-decreasing order. We claim that either b1 ≥ cl or bm ≤ c1, i.e. segments [b1, bm] and [c1, cl] can have common points only in their endpoints.

Why is this true? These groups add |bm - b1| + |cl - c1| to the overall sum. We consider the case c1 ≥ b1, the other is symmetric. If c1 < bm, then swapping c1 and bm will not increase the values these groups add to the answer, since the right border of b group moves to the left, and the left border of c group moves to the right. So, c1 ≥ bm in that case, and the assertion is proved.

Now we know that the values in each group should from a continuous segment of the sorted original array. In fact, we have groups of size (so called small groups) and groups of size (so called large groups). Consider the following dynamic programming: dp[L][S] — the minimal sum of values added to the answer by L large groups and S small groups, if we choose the elements for them from the first elements of the sorted array A. There are no more than O(k2) states, and each transition can be made in O(1): we choose large or small group to add and obtain the number it adds to the sum by subtracting two elements of the sorted array. The answer for the problem will be in .

The overall complexity of the solution is . We can note that in pretests was quite small, and some slower solutions could pass, but they failed on final tests.

Problem author: zeliboba.

Problem developers: Kostroma, AlexDmitriev.

Solution code: 12873418.

571C - CNF 2

Firstly let's assign values to variables occurring in our fomula only with negation or only without negation. After that we can throw away the disjuncts which contained them, since they are already true, and continue the process until it is possible. To make it run in time limit, one should use dfs or bfs algorithm to eliminate these variables and disjuncts.

So now we have only variables which have both types of occurrences in disjucnts. Let's build a graph with the vertices corresponding to disjuncts, and for each varible a make an edge between the disjuncts that contain a and !a. Now we should choose the directions of edges in this graph in such a way that every vertex has at least one incoming edge.

We can notice that if some connected component of this graph is a tree, the solution is not possible: on each step we can take some leaf of this tree, and we have to orient its only edge to it, and then erase the leaf. In the end we'll have only one vertex, and it'll not have any incoming edges.

Otherwise, take some cycle in the component and orient the edges between neighbouring vertices along it. Then run dfs from every vertex of the cycle and orient each visited edge in the direction we went along it. It is easy to easy that after this process every vertex will have at least one incoming edge.

So, we should consider cases with the variables which values can be assigned at once, than construct a graph from disjuncts and variables and find whether each connected component has a cycle. If so, we also should carefully construct the answer, assigning the remaining variables their values, looking at the directions of the edges in the graph. The overall complexity is O(n + m).

Problem author: zeliboba.

Problem developers: Kostroma, zeliboba, yarrr.

Solution codes: 12873432 (linear solution), 12873446 (), 12873456 (matching solution).

571D - Campus

Let's suppose for each dormitory from Q query we already know the last raid moment.

When task will be much easier: we can throw away M and Z queries and to get right answer we should subtract two values: people count in dormitory right now and same count in a last raid moment.

On this basis, we have such plan:

  1. For each Q query let's find the last raid moment using M and Z queries.
  2. Find people count in two interesting moments using U and A queries.
  3. Calculcates the final answer.

Let's try to solve the first part.

We want to make such queries on disjoint sets:

  1. Merge two sets (M query).
  2. Assign value time for all elements in particular set (Z query).
  3. Get value for a particular element (Q query).

To solve this task we'll use a well-known technique: "merge smaller set to bigger".

We'll maintain such values:

  • elements — set elements.
  • set_id — for each element their set id.
  • last_set_update_time — last moment when assign operation has occurred for each set.
  • last_update_time — last moment when assign operation has occurred for each element.
  • actual_time — moment of time when last_update_time was actually for the element.

Let's focus on actual_time value.

It's obvious that when we merge two sets each element can have a different last assign moment. But after first assignment all elements from any set will have the same value. So the answer for Q query for element i from set s: If last_set_update_time[s]=actual_time[i] then last_update_time[i] else last_set_update_time[s]

For each Z query you should just update last_set_update_time array.

It's easy to maintain this values when you merge two sets:

Let's suppose we want to merge set from to set to. For each element from set from we already know last assign time. So just update last_update_time with this value and actual_time is equal of last assign operation for set to.

The second part of the solution is the same as first one.

O(n * lg(n) + m) time and O(n + m) memory.

Problem author: ArtDitel.

Problem developers: yarrr, gchebanov, Kostroma.

Solution codes: 12873477 (solution, described in the editorail), 12873469 (solution with treaps).

571E - Geometric Progressions

If intersection of two geometric progressions is not empty, set of common elements indexes forms arithmetic progression in each progression or consists of not more than one element. Let's intersect first progression with each other progression. If any of these intersections are empty then total intersection is empty. If some of these intersection consist of one element, then we could check only this element. Otherwise one could intersect arithmetic progressions of first progression indexes and take minimal element of this intersection. The remaining question is how intersect two geometric progression? Let's factorise all numbers in these two progressions and find set of appropriate indexes for every prime factor in both progressions. These progressions one need intersect both by values and by indexes.

Problem author: zeliboba.

Problem developers: zeliboba, yarrr, gchebanov.

Solution code: 12873480.

 
 
 
 
  • Vote: I like it  
  • +70
  • Vote: I do not like it  

»
3 years ago, # |
  Vote: I like it -30 Vote: I do not like it

Why you don't prepare editorial before contest?...But thanks at all... ;)

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by Kostroma (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Order Book: "You should just maintain at most s best orders" Why?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's what the problem requires. It requires the optimal orders.

»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

In the beginning it was pretty hard for me to think about how geometric progressions behave and how they can intersect etc., but when I thought about them as vectors in everything turned out to be obvious immediately :).

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

    Correct, it simplifies some considerations.

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

tks author, this is great contest. But i only solve 2 Pro :(

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

For problem 571A — Lengthening Sticks it looks like there is a typo, it should be (l+1)(l+2)(l+3)/6 not (l+1)(l+1)(l+2)/6.

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

In Div1-A, can anyone explain why the total number of ways to increase the sticks not more than l in total is C(3; l+3)?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    make l in x1,x2,x3 but it's seen that x1,x2,x3>=0,it's hard:( so,let's set y1=x1+1,y2=x2+1,y3=x3+1. then the question becomes:make l+1+1+1 in y1,y2,y3 but the difference is that y1,y2,y3>=1! and we can ues many ways to prove that is C(3,l+3) then the question is done,hope to help you =)

    "prove":There're (l+3) numbers,we want to split it into 3 (2 + 1) parts,and each part has at least 1 numbers.Imagine to put 3 clapboards in the (l+3)blanks,that's C(3,l+3)...

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

      and we can ues many ways to prove that is C(3,l+3)

      I think that's what ngoisao_93 is asking for, and your comment didn't explain this.

      And as explained on the other thread, you can use stars-and-bars technique to count such partitions.

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

    I can explain with multiset combinations.

    From wiki: There are Cn+k-1,k ways to choose k elements from a set of n elements if repetitions are allowed. See Multiset (https://en.wikipedia.org/wiki/Multiset)

    Using above formula for the number of multiset combinations: n is your l+1 (including 0), k is 3 and k elements are l1, l1+l2, l1+l2+l3 — note that repetitions are allowed. So your total number is Cl+3,3

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

571B... I almost solved it

I have to satisfy with 571A

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Will be authors solution?

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

Can someone help me to understand the solution of 571B - Minimization ?

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

    i am also not able to understand explanation of 571B — Minimization. Can some one explain in simple terms wit some sample examples.

    Thanks

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

C(3,l+3)=(l+1)(l+2)(l+3)/6?

but the Solution says C(3,l+3)=(l+1)(l+1)(l+2)/6? :)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    It's a Combinatorial mathematics formula.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hope the solution will correct soon :)

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Here is my solution for Div1 C. After construct the graph as you described above, then find a maximum matching in this bipartite graph. If the size of found matching equals to the number of disjucts the answer is YES, otherwise it's NO.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain your solution in more detail? i solved it like discribed in editorial, but i don't understand why this graph is bipartite and how to apply maximum matching to this problem.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The graph is bipartite because each edge join a literal and a disjuct.

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

    There could be 4.105 edges in the graph. What is your bipartite matching complexity?

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

My solution for Div2 C.Let's run a for loop from i=1 to l.Calculate s=(a+b+c+i)/2. Notice that a non-degenerate triangle is only possible iff length of all sides is strictly smaller than s(semi-perimeter of triangle). So now the question reduces to find the number of integral solutions of x1+x2+x3=(a+b+c+i) such that a<=x1<=s,b<=x2<=s,c<=x3<=s (if (a+b+c+i)%2=0 then decrease s by 1) which is nothing but finding coefficient of x^i in (1+x+x^2+.....+x^(s-a))*(1+x+x^2+....+x^(s-b))*(1+x+x^2+...x^(s-c)).

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I too was thinking it this way, but implementing this looked very cumbersome. I saw that people did it in less than 10 minutes, which meant that there existed a simpler solution. I spent all my time figuring what it could be, and unfortunately, failed miserably. :P

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Would you explain about last part please?

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

    Shouldn't it be a <= x1 < s instead of a <= x1 <= s, and same for x2 and x3? Otherwise it seems "non-degenerate triangle is only possible iff length of all sides is strictly smaller than s" is not fulfilled?

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

      Oh, understood after seeing the implementation. He said "if (a+b+c+i)%2==0 then decrease s by 1", which means if it is odd, it takes care of itself.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div-2 D / Div-1 B : Can anyone explain the proof of why values in each group should from a continuous segment of the sorted original array? Can't seem to get it from the editorial.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Each group is sorted and any two group can have common points only in their endpoints.

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

    Suppose not. Assume each group is in sorted order. Then as you can see in the pic, at least one of the end points of one groups, lays within the other group (The picture shows a particular condition of two groups. For any other situation a similar observation can be made).

    So in this case , let's move x6 (maximum) from group X to group Y , and y1 (minimum) from group Y to X. If you compare the total length of the narrower arrows which represent the "cost" of each group before and after the swapping of two elements, you'll see that this kind of change in the groups will always lead to a better answer.

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

      Nicely explained. Thanks! :)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What does author mean by the states ? And how is that O(k2)? Can you also explain how to implement the algorithm. I am stuck here. Thanks.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        "States" means "dynamic programming algorithm states". If you're not familiar with the concept, you can learn more about it and solve some easier problems Here (Number 24) first.

        Also make sure you have understood the part about big groups and small groups in the editorial (feel free to ask if you couldn't).

        The DP states in this problem are defined as this: We have chosen "i" small groups and "j" big groups, so dp[i][j] will be equal to the minimum "cost" for choosing such i "small" + j "big" groups. dp[0][0] = 0 is the only trivial case and dp[n][m] (where n and m are the total number small and large groups that need to be chosen respectively) will contain the answer after the execution of the dynamic programming algorithm.

        The dp transitions go like this : Suppose we're on state(i , j) now. We'll try to update states (i + 1, j) and (i , j + 1). In other words, on each step we are trying to choose either a small or a large group, until we reach the desired state which is (n , m).

        Based on my previous comment we know that each group is consisted of a contiguous segment of the input array in sorted order. Therefore in the dp transitions we'll choose numbers from the start of the list. That is when choosing numbers that are going to be placed in a small group( (i ,j) -> (i +1 , j) ), we will choose the first "al" numbers in the sorted array which are not chosen yet ("al" is the number of elements in a small group) and we will choose the first "bl" elements otherwise ( (i,j) -> (i , j + 1) ).

        But how do we know that how many elements of the array have been chosen ? Since the number of elements in each of the two kinds of groups is fixed, having i and j, we'll be able to find how many elements have been used, and we can choose "al" or "bl" elements from there. The extra cost choosing these elements adds to the total cost is the difference between the first and the last elements (in non-decreasing order) in the group. So the transitions would be like this if we are on (i,j) : (dp[i][j] is the minimum cost of choosing i small groups and j large groups , al is the size of the small groups and bl is the size of the large groups)

        if dp[i][j] + cost of choosing the first "al" elements starting at the index al*i + bl*j (which is the last chosen number) makes up for a better cost than the current dp[i+1][j], update it.

        if dp[i][j] + cost of choosing the first "bl" elements starting at the index al*i + bl*j (which is the last chosen number) makes up for a better cost than the current dp[i][j+1], update it.

        code

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you so so much. I just can't tell you how helpful this has been. I was stuck here for like over a day now.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            No problem. I hope you can solve it now.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I still don't understand how does it work. I understand that we need to look at all the combinations formed by sequence of small and large segments. If we encode them as 0s and 1s we should look for a combination like 1000101110101011 of length k that will minimize the sum. I do not understand, how are we skipping all these combinations...

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Note that swapping c1 and bm doesn't mean swapping these two elements themselves; it means inserting the element into another group. The group is always in non-decreasing order!

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

Div-2 C : How to convince or prove that, the procedure listed in the solution in exhaustive. That is sum of three inverse selection is indeed removing all the triangles with non-positive area.

»
3 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

MY EXPLANATION OF PROBLEM "LENGTHENING STICKS" the conditions for the triangle with sides a,b,c which can be increased by length La,Lb,Lc with the restriction that limit of combined increase should be less than equal to L having positive area is-

  1. a+b>c
  2. b+c>a
  3. a+c>b
  4. La+Lb+Lc <= L

we basically need to take two things in account to solve the problem

1) Calculate All Possible Combinations Of The Lengths Of Sides That We Can Have :: Mathematical formula of which and explanation can be found out here-
http://math.stackexchange.com/questions/192670/n-unlabelled-balls-in-m-labeled-buckets therefore considering the first testcase of 1 1 1 2 , total possible combinations of side lengths we can have is 10 = (2+1)(2+2)(2+3)/6 ;

2) start off with one given side and keep on increasing till the increase in its side becomes equal
to L because that's the maximum possible increase we can have.

let us take an example to understand this further- In above mentioned case we represent the sides by (1,1,1) -> (a,b,c). we start off with side 'a' of length =1; we first increase the size of this side by La=0;

now we look at our condition

1) a+La < b+c (1+0)<(1+1)

so this condition holds true, so even if we increase the lengths of 'b' and 'c' the condition will
remain true so this will never result in any non-positive area(degenerate) triangle.therefore we further increased 'a' by 1 .Therefore La=1 and again look at our condition

2) a+La >= b+c (1+1)>=(1+1)

This does not satisfy our condition of positive area triangles. now since we have satisfied one condition of degenerate triangle we look further into different possibilities of Lb and Lc with the
restrictions that degeneracy should be maintained and total combined increase should be less than equal to L.

This gives rise to two more conditions

1) a+La >= (b+Lb) + (c+Lc) ( lb + lc<=a+la-(b+c) (in our case this equals to 0 (1+1-1-1) ) )

2) la+lb+lc<=L ( lb+lc<=L-la ( (in our case this equals to 1 (2-1) ) )

taking both into account we get lb + lc<=min(a + la- (b + c) ,L-la);

let the minimum be x (in our case this equals to 0) again using our combination knowledge we get that equal (x+1)*(x+2)/2 (in our case this equals to 1) this way we got all possibility of degenerate triangles with side 'a' as '2' (a+la). now we subtract
this from our total combinations.(10-1=9) Now we further increased the length of a by 1 so that a becomes '3' (a+La=1+2) and again look at our conditions

3) a+La >= b+c (1+2)>=(1+1)

this does not satisfy our condition of positive area triangles. now since we have satisfied one condition of degenerate triangle we look further into different possibilities of Lb and Lc with the
restrictions that degeneracy should be maintained and total combined increase should be less than equal to L.

This gives rise to two more conditions

1) a+La >= (b+Lb) + (c+Lc) ( lb + lc<=a+la-(b+c) (in our case this equals to 1 (1+2-1-1) ) )

2) la+lb+lc<=L ( lb+lc<=L-la ( (in our case this equals to 0 (2-2) ) )

taking both into account we get lb+lc<=min(a+la-(b+c),L-la);

let the minimum be x (in our case this equals to 0) again using our combination knowledge we get that equal (x+1)*(x+2)/2 (in our case this equals to 1) this way we got all possibility of degenerate triangles with side a as '3'(a+la). now we subtract
this from our total combinations.(9-1=8) Doing the same thing for the 2 more sides we get the number of degenerate triangles=6(2*3)

THIS IS BASICALLY WHAT WE ARE DOING IN OUR CODES.

NOW WE NEED TO LOOK AT TWO MORE IMPORTANT THINGS-

1) All Degenerate Triplets are Unique - since for degeneracy (a'=a+la, b'=b+lb, c'=c+lc) 1) a'>=b'+ c' (a'>=b' and a'>=c') 2) b'>=a'+ c' (b'>=a' and b'>=c') 3) c'>=a'+ b' (c'>=b' and c'>=a') the second condition part in brackets of all three conditions can only be satisfied simultaneously if triplets are unique.

2) They Cover all the Possibilities since for every side we starting from its original length and going till maximal possible length we are covering all its possibilities and since we are doing this for all three sides we are
getting all possible triplets

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please a bit more on how the degenerate triplets are unique. Maybe with an example.

    Thanks!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can't there be a situation when 2 triplets come to be same ? Like if first we have a and then we increase b; and in another case where we first have b and then increase a. Won't the triplets be equal?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain tutorial of Minimization with an example, so that it can be more clear ??

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

I div1/E 1st test case:

2

2 2, progresion 2,4,8,16,...2*2^x=2^(x+1)

4 1, progresion 4,4,4,4,...4*1^x=4

I'm not realy clear how is answer 4.Have I misunderstood something?

I got it now... f(x) is needed not x ...

»
3 years ago, # |
Rev. 6   Vote: I like it -12 Vote: I do not like it

Solution for Div 1 B is wrong isn't it?

For example, for this case

13 7
-1 -1 0 1 1 1 1 1 1 1 1 1 1

Clearly, we can see the solution is from segment [0, 1] and [2, 12], which give result = 0, but if we assume that all groups should belong to a continuous segment (as stated in the solution), so we can only obtain result = 1, which is wrong.

The permutation for correct result should look like:

-1 1 1 1 1 1 0 -1 1 1 1 1 1
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    If N=13 and K=7 the permutation -1 1 1 1 1 1 0 1 1 1 1 1 -1 leads to an answer of 4, because and other terms are equal to 0.

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

      Sorry, wrong permutation, updated. It should be:

      -1 1 1 1 1 1 0 -1 1 1 1 1 1
      
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The solution described in the editorial will lead to exactly the permutation you provided. Here's how.

    We want to split all these numbers into 6 groups of size 2 and 1 group of size 1. All these groups are going to be independent because they are not going to intersect with each other in the final permutation.
    The described DP solution leads to the following partitioning: [-1, -1], [0], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1].

    If we want to construct the final permutation from this partitioning, we would first put 0 into position 7, because that's where the group of size 1 starts. We'd then fill out the rest of the groups of size 2:
    [-1, -1] into positions 1 and 8, [1, 1] into positions 2 and 9, and so on.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div1-E,

Let's factorise all numbers in these two progressions and find set of appropriate indexes for every prime factor in both progressions. These progressions one need intersect both by values and by indexes.

What does it mean to "intersect both by values and by indexes"? How to do it? How to combine progressions from primes?

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

    Finally AC. The tests are very good, catched so many different bugs:

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Kostroma (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem D in Div2. why we have K-(n mod K) groups of size n/k (so called small groups) and (n mod k) groups of size (n/k+1) (so called large groups)? please explain anyone ....

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

Any idea why C can be solved like this: 12659862

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hm, taking smallest clause and assigning first variable to satisfy it. There should be counterexample..

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't feel like reading that code, but what I can tell is that it is probably doing something smarter than what you've described, because that way this would be a counterexample:

      4 3 2 1 2 2 2 3 2 3 1 3 -1 -2 -3

      but custom invocation says it is not.

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

        If it is possible to use a variable (and is negation) more than twice, a simple 2SAT example can make this fail: 3 2 2 1 2 2 2 -1 2 -1 -2

        But I have no test case to break the solution with the original constraints. I store the clauses increasing size and assign true to the first variable of the smallest clause, then erase its negation. I found a few more submissions using this approach (store clauses in a priority_queue instead), it would be nice if someone can prove this.

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

          Actually it makes sense. In the view of the editorial's solution, this algorithm strips nodes with degree 1 first, until there are no such nodes. After that there are only cyclic parts left and then we can direct any edge in any direction. And repeat the algorithm

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It removes the opposite occurences of the assigned variable from other clauses.

        So after checking the first two clauses, there will be

        (-3)^(3v1) -> assign -3 -> (1) -> assign 1 (it was already assigned but it's ok).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the Minimisation Part-> I didn't understand from here: "There are no more than O(k2) states, and each transition can be made in O(1): we choose large or small group to add and obtain the number it adds to the sum by subtracting two elements of the sorted array"

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain me the implementation of the Minimization problem with an example. Please. I am stuck for over a day now

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

For the problem Div1C, I think the statement “It is guaranteed that each variable occurs at most once in each clause.” is confusing. One may consider a variable can appear several times as long as it appears at most once in every clause.

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

    I was not carefully reading the pre-statement "We know that each variable occurs in at most two clauses", but concentrating the last sentence, that'why I'm confused. Maybe the problem itself could be more clear.

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

I don't understand solution of problem div 2D/ div1B . I understand that there would be two groups, but how to prove that there will be (n mod k) and k — (n mod k) elements respectively and theirs sizes will be n/k and n/k + 1 ?

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

For problem 571D - Campus, my solution is constructing a tree for Military Offices and Universities and segment trees for queries. You can read my solution if you're interested.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, we had such solution, it's quite nice but we decided to publish another solution in the editorial, supposing it is less standard and easier to code.

    Those who interested — can look at my solution.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Kostroma (previous revision, new revision, compare).

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Fortunately, I have found a way to publish links to submissions so that they are visible not only for admins of the round, thanks to I_lost_my_handle. Now you can look at author's solutions of our problems.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice. I didn't know about this trick and I participated virtually in my contest to publish solutions.

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

never mind

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know what method is used to solve CNF problem here?

I find this code much more comprehensible than the ones in the editorial and I'd like to see the big picture behind this code (the general theory). If all it represents is just the problem specific solution, then it's not as valuable as the editorial's solutions (because they allow me to practice the general widely used graph algorithms, like the matching algorithm), but I hope that there are some things to learn :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, it would be grateful, if anyone can explain me how to derive formula and solve DIV2 C using stars and bars or another approach. Thanks in advance.