NBAH's blog

Codeforces Round #367 (Editorial)
By NBAH, history, 22 months ago, translation, In English,

A

We know that time=distance/speed. For each car we should find timei, than if it is less than answer we should update it.

Time Complexity: O(n).

Solution

B

Consider c[x] the number of stores in which the price per drink is x. We calculate this array prefix sum. Then the following options:

1) If the current amount of money m is larger than the size of the array with the prefix sums than answer is n.

2) Otherwise, the answer is c[m].

Time Complexity: O(n+q).

Solution

C

We will solve the problem with the help of dynamic programming. dp[i][j] is the minimum amount of energy that should be spent to make first i strings sorted in lexicographical order and i-th of them will be reversed if j = 1 and not reversed if j = 0. dp[i][j] is updated by dp[i - 1][0] and dp[i - 1][1]. It remains to verify that the i-th string is lexicographically greater than (i - 1)-th (if j = 1 then we should check reversed i-th string, similar to (i - 1)-th). Then we update dp[i][j] = min(dp[i][j], dp[i - 1][0] + c[i] * j), dp[i][j] = min(dp[i][j], dp[i - 1][1] + j * c[i]). The answer is a minimum of dp[n][0] and dp[n][1].

Time Complexity: O(n+sum_length).

Solution

D

Let's store each number in binary system (each number consists of 32 bits, 0 or 1) in such a data structure as trie.The edges will be the bits 1 and 0, and the vertices will be responsible for whether it is possible to pass the current edge. To reply to a query like "? X" will descend the forest of high-order bits to whether the younger and now we can look XOR in the i-th bit to get one, if we can, then move on, otherwise we go to where we can go.

Time Complexity: O(q*log(10^9)).

Solution

E

Let's surround the matrix with the frame of elements. In each element of the matrix, and frame we need to store value, the number of the right element and the number of down element. When a request comes we should change only values of the elements along the perimeter of rectangles.

Time Complexity: O(q*(n+m)).

Solution

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

Comments Comments (108)
»
22 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Problem B can be easy solved using Binary search

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

    I think it's so classical binary search problem
    you can copy it's code simply from google!

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

    will it not be the case then complexity is more. log(n) for each search. so time complexity qlog(n), also for sorting nlog(n). so finally time complexity = max(nlog(n), qlog(n)).

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

      Yeah, but the idea is more obvious to some of us, and the code is really really simple, too.

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

        http://www.codeforces.com/contest/706/submission/19794976 Got tle using binary search !

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

          Binary Search in cpp worked just fine!

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

          The problem is here

          while(index >=0 && x.get(index)==p+1)
    index--;
          → Reply
          • »
            »
            »
            »
            »
            »
            22 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            What if there are multiple values for key in binary search ( java) ?? What does the method return ? ( i assumed any one of those values)

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

              It randomly returns any index of the number you are currently searching for

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

                So there is no workaround for finding the end range of a value other than lineaely traversing in one direction after bin. searching ????

                → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            i tried it with binary search but whhhy only 4 tests there is help ?

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

      shouldn't the complexity be n * log(n) + q * log(n) ?

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

    Yes.I think so.

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

    data aint sorted :|

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

    I don't even have to implement binary search. Just straight using sort() and upper_bound() function in c++.

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

    No , i tried to solve it by binry search and I got TLE.

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

      I got accepted with binary search on bits.

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

        Yes i just saw an answer solved by binary search. I was actually using simple iteration to check how many elemants were equal to the given query because of which i was getting TLE.

        → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Your hands are crooked.

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

        Excuse me, why would you say that?

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

          I mean that if your solution with binary search gets TL, you do something wrong.

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

            Yes, I already said that in one of my above comments.

            → Reply
»
22 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Don't understand the approach for E ! Can someone explain it better ?

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 3   Vote: I like it +53 Vote: I do not like it

    This problem is an exercise in Linked Lists: store the matrix as a 2D array of elements each of which has links to its upper, lower, left and right neighbours. To swap two rectangles you only need to consider their borders. Tear the rectangles off from the matrix by erasing the needed links (i.e. erase all upper neighbour links to tear the upper border of a rectangle) and stitch them back in each other's spots. Note that you lose the ability to ask for a cell in (r, c) by a 2D array lookup but should instead start from the upper left corner and walk r down and c right links.

    To avoid null pointers, surround the matrix by a frame of fake cells, as the editorial suggests.

    Example solution: http://codeforces.com/contest/706/submission/19808792

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    One thing to note about swapping submatrices is that the actual submatrix "structure" doesnt change, take a look at the following masterpiece (orange is left neighbour, red is right, blue is up, and green is down).

    so say i swap the top left 2x2 submatrix(1,2,5,6) with bottom right 2x2 submatrix(11,12,15,16). the INTERNAL arrows never change, because the actual submatrices still have the same elements. However, the perimeter arrows change, because we now have new neighbours due to swapping matrices. In order to fix the structure, all we have to do is swap the corresponding perimeter arrows, so for example 15 green arrow will point at 9, 12 red arrow will point at 3 etc.

    hope that helps!

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

    Help with solving E needed, I got TLE on test 10 all the time, could anyone explane why does it give TLE? Check the last submission pls http://codeforces.com/submissions/GuralTOO

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

      Got rid of TLE, by simply using scanf/printf now have trouble with WA..

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

        Check your nested for loops, some of them are for looping n then n, rather than n then m (which explains why you get WA on that testcase, because its the first one where n<m, so some ids arent assigned).

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

          Man, thank you a lot, was typing fast, so didn't notice.. that fault, thank you again

          → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why this submission: 19811194 gets memory limit exceeded?? It's memory complexity is O(q lg MAXa) which is ok for this problem!

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

    i am not sure but maybe this is the reason :

    you are right about O(q*logMax) but here you have a constant like 2*5=10. 2 because of creating both nodes at each step not just one. 5 because of struct size (pointer size is 32 bit).

    → Reply
»
22 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Thanks for a really awesome problem set. Really enjoyed the contest.

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

Isn't complexity of D just O(q)? That log factor is constant.

Btw, u can solve D without any data stucture, finding bits from most significant one with lowerbound on set. The main idea is the same, but u don't have to know trie. Here's my code — 19807490, complexity is O(q*log(q)).

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

    please be more specific on your binary search on set please?

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

      Ok, look. First of all we have l = 0, r = maximal value of unsigned int. y = bitwise negation of x — best-case scenario for xor, our reference point. We look over bits of y from 31th to 0th.

      If pth bit is set (y & (1<<p)), we'd like to set that bit in our answer. We can use lowerbound to find out if set contains at least one number in range [l+(1<<p), r]. It can't be less than l+1(<<p) or greater than r, because we have to satisfy assumptions about more significant bits we've made before (l, r), and also we want pth bit to be set (1<<p). If we satisfy that condiotion, then [l, r] becomes [l+(1<<p), r], otherwise it becomes [l, r-(1<<p)].

      If pth bit of y is not set, we don't want to set it in our answer. We use lowerbound to check if set contains some elements in range [l, r-(1<<p)]. If it does, we set r to r-(1<<p), otherwise l becomes l+(1<<p).

      After loop we have l = r, and we output this number xor x.

      → Reply
»
22 months ago, # |
  Vote: I like it +4 Vote: I do not like it

In the explanation of problem D, what does RRF mean?

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i have problem with time complexity analysis of problem C. let us do worst time complexity analysis. for each case say we have to reverse . reverse function has linear time complexity and for each case we are reversing hence time complexity should be O(n^2) or 10^5 * 10^5 = 10^10.i think then this algorithm should get time limit exceeded verdict in test case where reverse permutation of a string of length close to 10^5 is used.

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

    From the problem statement: The total length of these strings doesn't exceed 100 000.

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Yeah: the reverses and comparisons will alltogether be O(n), or amortized O(1).

      Also imagine that your worst case was possible, it would mean that each string has 10^5 characters, which means you couldn't even input the input without getting TLE.

      → Reply
»
22 months ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

I have a solution for problem C that does not need DP 19812078:

It basically "tries" both the string and its reverse against all possible previous choices.

class Choice(String s, Long cost)

choices := List.of(new Choice("", 0))

for (cost <- costs) {
  s := readInput()
  r := s.reverse()
  current := List.of(new Choice(s, 0), new Choice(r, cost))
  next := new Map<String, Long>() withDefault Long.MAX

  for(c1 <- choices) {
    for(c2 <- current) {
      if (c1.s.isEmpty || c1.s <= c2.s) {
        next[c2.s] = min(next[c2.s], c1.cost + c2.cost)
      }
    }
  }
  choices = next.map((k, v) => new Choice(k, v))
}

if (choices.isEmpty) print(-1) else print(choices.values.min)
→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    So you only store the last row in your DP

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

      Exactly: it's still the same logic as the regular DP.

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
        ← Rev. 2   Vote: I like it -13 Vote: I do not like it

        Ah, you are right — now I see the similarity. Atleast when I was writing the code, I did not think I was doing DP :)

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

          Brute force would be if you also went all the way back to the first string when trying an option for the current one. Using the fact that the previous string is enough (and storing the corresponding scores) makes it DP :))

          → Reply
»
22 months ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

Hi, last night I misunderstood the problem C:

  • they said "total length of the strings <= 100 000"

  • but I thought "length of each string <= 100 000"

So I came up with the idea "how to compare 2 strings only in O(log(length(string)), and we also don't have to reverse it in O(length)", based on binary search. Thus, the general complexity is O(qlog(length))

So I wrote a "compare(string s1, string s2, int type)" function:

  • type = 1: compare non-reverse s1 and non-reverse s2

  • type = 2: compare non-reverse s1 and reverse s2

  • type = 3: compare reverse s1 and non-reverse s2

  • type = 4: compare reverse s1 and reverse s2

Then I submitted and got WA, so I hope somebody could take a look at my submission and point out what I was wrong. I'm sure I got wrong in my "compare" function because when I use standard "compare" and "reverse" functions of C++, I got AC ( of course the complexity now is O(length) ).

Ty in advance.

My submission: 19808155

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

    Binary searching like this is wrong, because comparing the middle of two strings doesn't tell you anything about the characters before it or after it. You should compare entire prefixes of the strings, and to do so efficiently you'd need hashing, but that means that before the binary search you'd already do O(length) operations for the hashing.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How do we prove the solution to B is correct ?

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

    By greedy, you want to buy the X-cheapest items available anyways.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is RRF in problem D?

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C: I have one doubt.

Let's suppose the given order of string is : Let's call them by name A, B, C A B C

if we needed to reverse B (rB) to be lexicographically smaller than or equal to B, then we can't check for B with C, we need to check for rB with C only. I.e. we can't reverse the reversed string for next comparisions. How is this case handled in the dp solution? Can anyone explain please?

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    That is the reason why we have to add the "state index" 0/1 to our dp array (that's what I call it)

    As you said, dp[i] is not enough, because we would not know if (i-1)-th string is reversed or not to calculate exactly dp[i].

    But everything will be easier if we have the state for each string we're considering:

    • dp[i][0] means the minimum result if we don't reverse i-th string

    • dp[i][1] means the minimum result if we reverse i-th string

    Thus, the (i-1)-th string will also have 2 states: reversed or not. dp[C][0], dp[C][1] will be calculated based on dp[B][0] (B) and dp[B][1] (rB)

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I still dont understand prob C. Is the dp actually like brute force? wont it take O(2^n)?

also, in prob D I tried something like putting in integer form in list. I dont understand what the editorial says when it says to put in binary.

(I am new to codeforce!!)

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

    dp isn't brute force. You update dp[i][0] and dp[i][1] in O(s[i].length). So total complexity is O(sumLength).

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

    The point of dp is to memorize previous choices that won't be affected by later choices, so that we could save the time for computing the previous choices again when we proceed to later choices.

    In problem C the states store the value of previous computed strings, since it is guaranteed that it all the previous strings have been ordered in lexicographical order (or just set the value to INF if it is impossible to do so), you only have to compare the latest string to the reversed or the original string to check the minimum costs of following the lexicographical order.

    For problem D I can't find your submission so I don't know what exactly got you, but I suppose that you have completely no idea of what the editorial is doing.

    The solution is to build a tree/trie, that stores integers in binary form (eg: 5=101(2), 7=111(2) ). You have to maintain the amount of values in the subtree in order to answer the value.

    If you don't know about Trie, or even some other tree structures like BIT(fenwick tree), read them before solving this problem, or else you will have absolutely no idea what I am explaining.

    After building the trie of the multiset, you have to check 1. if there is an edge to the left child(0) and the right child(1), and if the left/right child is empty (cnt==0). Make the optimal steps upon visiting each nodes, and sum up the values of xor for the query results.

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

I'm still learning DP, so confused about problem C.

We both know if we want apply DP to some problem, the problem must meet several conditions.One is that it must have optimal sub-structure. One is that the sub-problem has non-aftereffect property.

So here is my question, if we already solve the first i query, but the i+1 th string is smaller than the i th but the cost c[i+1] is too big, then we should not reverse the i+1 th but modify the first i string, how's that meet the optimal sub-structrue and non-aftereffect property? Because the i+1 th string has a big influence on the answer we've already calculated before.

I don't know where I get wrong, thanks for your help.(sorry for poor English

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have solve C using dp , but getting wrong answer. Can someone help me to debug.... I use dp1[] for reverse string and dp[] for simple string. ~~~~~ ..

#define For(i,st,ed) for(i=st;i<=ed;i++)

const ll mod=1000000007;

//Main

int main() { ios_base::sync_with_stdio(false);cin.tie(0); int test=1,i,j,n,tt;

//cin>>test;

For(tt,1,test){
    cin>>n;
    string st[n+1];
    ll dp[n+1],dp1[n+1],a[n+1];
    string s,s1;
    ScanA(a,n);
    dp[1]=0;
    dp1[1]=a[1];
    For(i,1,n)
       cin>>st[i];
    For(i,2,n){
       s.assign(st[i]);
       s1.assign(st[i-1]);
       reverse(s1.begin(),s1.end());
       dp[i]=dp1[i]=-1;
       ll x=-1;
       if(s.compare(st[i-1])>=0 && dp[i-1]!=-1)
         x=dp[i-1];
       if(s.compare(s1)>=0 && dp1[i-1]!=-1)
         if(x!=-1)
          x=min(x,dp1[i-1]);
         else
          x=dp1[i-1];
       dp[i]=x;
       x=-1;
       reverse(s.begin(),s.end());
       if(s.compare(st[i-1])>=0 && dp[i-1]!=-1)
         x=dp[i-1]+a[i];
       if(s.compare(s1)>=0 && dp1[i-1]!=-1)
         if(x!=-1)
          x=min(x,dp1[i-1]+a[i]);
         else
          x=dp1[i-1]+a[i];
       dp1[i]=x;
    }
    ll x=mod;
    if(dp[n]!=-1)
       x=dp[n];
    if(dp1[n]!=-1)
       x=min(x,dp1[n]);
    if(x==mod)
       x=-1;
    cout<<x<<endl;
}
//end of test

return 0;

}

~~~~~

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

    Change const ll mod=1000000007; to const ll mod=100000000000007; A bigger number so to say. As the sum of the numbers in the dp array can exceed 10^9+7.

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

    Side note: My personal way to set the INF for long long is (1LL<<60), I have also seen some pretty good ways such as "1234567890123456789012345LL"

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

      Or just use scientific notation, eg: 1e9 + 7 or 1e18. I think it's more understandable and not as much error-prone as "1234567890123456789012345LL"

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

        1e9+7 and 1e18 are without doubt great ways to do it too, it's just a personal preference after all. =D

        → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Explain prob D more properly plz . Whats RRF?

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 4   Vote: I like it +7 Vote: I do not like it

    19825442 is my commented solution(C++) for you. You can do it easily with map. Time Complexity: O(q*31*log2(10^5)).

    more explained submission: 19825804

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain the D solution in more detail or from another perspective?

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What does the announcement mean ? "The lexicographical order is not required to be strict, i.e. two equal strings nearby ARE ALLOWED."

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

    That means it's still ok if s1<=s2 , it's not required for s2 to be strictly than s1 (i.e. s2>s1) to be considered as being ordered lexicographic-ally.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Link for Solution of problem C gives error

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

    click top-right link!!

    → Reply
»
22 months ago, # |
  Vote: I like it -25 Vote: I do not like it

include <bits/stdc++.h>

using namespace std;

int main() { int n; scanf("%d",&n); int a[n]; for(int i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); int q; scanf("%d",&q); while(q--) { int m; scanf("%d",&m); int ans=int(upper_bound(a,a+n,m)-lower_bound(a,a+n,a[0])); printf("%d\n",ans); } }

//My solution using C++ STL .

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution for D with std::multiset: just like in solution with trie, for the ith bit, first we try to get 1, if it's not possible we will get 0. But we can check this using lower_bound.

Code: 19826426

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The solution for problem E is just beautiful :)

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
These are the first few lines of Test #7
100
? 1
+ 1
+ 4
? 5
...
My code prints
1
4
But judge prints
1
5

Please explain how output is 5 for second line.
I got 4 by computing: max(5 XOR 1, 5 XOR 4) = max(4, 1) = 4
Thanks in anticipation.
→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    5^0 = 5

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

    "You are given q queries and a multiset A, initially containing only integer 0"

    the set initially has a 0 and 5 XOR 0 = 5

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone is interested in practicing problems similar to problem D, here is a question I realized that the solution is quite similar to problem D.

282E — Sausage maximization

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

I just want to make something sure about problem E. a)Swapping two rectangles like the red and green one is not allowed, right?

b)And if such an operation were allowed, would there be an efficient method to solve this problem?

update: solved it. So, I am clear about (a). So if anyone could tell me about (b)...

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

    I have never implemented this but I think this may work.

    1) Keep two vectors of coordinates of the perimeter, ordered corresponding to their position.

    2) When swapping, check if the block next to the swap is occupied by another block. If no, just do the operation required for E. If yes, check for the corresponding position in the original block, and link it to it.

    Keeping the difference in position of the blocks should help speed up the look-up process to O(1), so the whole algorithm should work in O(n).

    This is not applicable for overlapped blocks though.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There is error shown by hosting site . Please rectify it .

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

Does anyone have an idea for problem E in O(qnlogn) ? With data structures like segment tree?

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The solution link for C seems to be broken. Can you fix it?

→ Reply
»
22 months ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

For the 1-dimensional version of Problem E, is there a solution with faster than linear time swaps?

So in the 1-dimensional version, instead of swapping rectangles in a matrix we're swapping ranges in an array: each task is (a, c, w) and we want to swap the values in [a, a + w) with the values in [c, c + w).

And with n items and q swap queries, we want an O(q * logn + n) algorithm, or just anything faster than O(qn).

With the linked list solution in the post (which is super cool to me!), in the 1-d case it takes O(n) to find the rectangles, even though it's an O(1) swap after finding

I was trying to do something with a binary search tree: each range corresponds to <= logn nodes in the tree, so maybe you could swap ranges by swapping only those logn nodes somehow, and their sub-trees would automatically come with them.

The problem is that the ranges don't "line up": I somehow managed to convinced myself this wasn't really a problem, but I was totally off, and it is a serious issue, as far as I can tell.

Anyway, yeah, is there a quicker solution to the range-swapping problem? I.e. like an O(n) size data structure on n items which supports fast range swaps?

EDIT: answer to question = yes treap

weaker guarantees than with treap i'd guess, but i think a skip-list would work too with high probability. You can find ranges quickly and then edit O(# lists) = O(log N) pointers.

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

    Treap makes swaps in O(logN)

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
      ← Rev. 6   Vote: I like it 0 Vote: I do not like it

      EDIT: I'm not sure if what I said below really even makes sense actually; I'll think about this for a bit/try to understand treaps better.

      EDIT2: Okay I sort of get how the treap might work, although I'm still not sure how it'll necessarily stay balanced after lots of swaps (with high probability I guess? or it happens only after many swaps, so you can amortize any rebalances if they're needed or something).

      Thanks a lot for the response! I didn't know about treaps, they're really cool!

      But I don't see how a treap would do it though. This is how I imagine a treap approach would go:

      You construct a treap on [0, n), say as a balanced BST (and then assign the corresponding priorities).

      And then on a query (a, b, w) with a < b, you split the treap into 5 smaller treaps, t1=[0, a), t2=[a, a+w), t3=[a+w, b), t4=[b, b+w) and t5=[b+w, n)

      Then we merge them back together in the order t1, t4, t3, t2, t5.

      Splits and merges are fast, so this should be fast..

      But: naively, in order for the treaps to be merged correctly, you'd need to update the priorities of every node in t4 & t2, which would take linear time.

      Maybe there's a way to store these updates to the priorities in a more succinct/clever way, but I don't see it. (of course I might be missing something!)

      → Reply
»
22 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Hello friends ! :D I would like to talk with you about problem D which i found very interesting as i've learned new data structure(trie)... I've failed on task 9 for some reason even tho i am pretty sure my logic is good.

I wrote it in C language and i will explain to you what i've did to solve this problem in hope that someone will help me find flaw in my logic...

http://codeforces.com/contest/706/submission/19910611

I've constructed an trie,for every input,31 bits,i do not "re add" numbers that are already there which i track using a self made map.In structure i have int "cnt" which helps me with knowing how many unique inputs are there in specific node which will help me later when i delete a node from trie.The way i find the answer is that im trying to locate(if exists) an node that has different bit from the one i am looking at atm for example number 11011 i would start by finding a bit different then 1(0) etc etc. untill i reach the end(i think this part of logic is fine).But the tricky part comes when deleting the specific number..The way i solved it is that i kept track of how many specific numbers i added with '+' command,after i use '-' command i act only if the number in set == 0. In that case i traverse trough the trie using that number's bits,the same moment i reach the node that has "cnt" == 1 which means that the node is being used only by that unique number,i just release it from the trie with everything connected to it (as it was everything connected to the number i wanted to delete).

Thanks so much ! Cheers !

UPD: I found out bug,the problem was that if for example trie is like this | | | / \ And if if first stub belongs to first and second number and if i want to remove 2nd number i remove right most node but when it is time to remove the first one i only remove the left most one as i did not mark that i am finished with main stub(as cnt of it should be 1 instead of 2).

Thanks anyways.

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

Why this solution of problem D got RE? Help me, please.

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

problem D :
more clear code : http://codeforces.com/contest/706/submission/19944188
this post is awesome : https://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems

→ Reply
»
22 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

edit : found my mistake

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi guys, I have implemented problem E by Python, anyway got TLE at test 10, can anyone help on this

http://codeforces.com/contest/706/submission/19963732

Thanks in advance

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hey guys I'm getting WA on test 91 in problem D and i have no idea why. can anyone help me? this is my submission http://codeforces.com/contest/706/submission/20033141 i would really appreciate it

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

Hello everyone!

Can you help me why I get TLE for Problem D? Here is my submission : http://www.codeforces.com/contest/706/submission/20083814 I used binary search between lo and hi, which are iterators that contains maximum values. But it got TLE on test#2. I think it's because of case when lo > hi, but I can't find out when.

Thanks in advance

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    std :: lower_bound works in linear time for multiset\set so use s.lower_bound(x).

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

      Oh! I didn't know that! Really appreciate your answer _index :)

      → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please fix problem D solution!!

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution links to problem C and D broken. Any fixes? Please tell.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved D but when I submitted it in the system it told me that i got a wrong answer on test 1 . It told me my answer is '0 0 0 0 ' but in my computer it runs well. Why?....

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice Editorial :)

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have encountered pastie.org to be unavailable a number of times.

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

Can some help me with the tutorial of problem D? I don't seem to understand this statement,

"To reply to a query like "? X" will descend the forest of high-order bits to whether the younger and now we can look XOR in the i-th bit to get one, if we can, then move on, otherwise we go to where we can go."

Thanks in advance.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I wrote about Problem C in this post here. It's an enjoyable DP question.

→ Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

please someone help me to get what is wrong in my approach with problem C. link to my code.. [(http://codeforces.com/contest/706/submission/39018222)]

→ Reply