dalex's blog

By dalex, 5 years ago, translation, In English
  • Vote: I like it
  • +170
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

A merchant in Baghdad sends his servant to the marketplace for provisions. Soon afterwards, the servant comes home white and trembling and tells him that in the marketplace, he was jostled by a woman, whom he recognized as Death, who made a threatening gesture. Borrowing the merchant’s horse, he flees at great speed to Samarra, a distance of about 75 miles (125 km), where he believes Death will not find him. The merchant then goes to the marketplace and finds Death, and asks why she made the threatening gesture to his servant. She replies, “That was not a threatening gesture, it was only a start of surprise. I was astonished to see him in Baghdad, for I have an appointment with him tonight in Samarra.”

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

I felt like problem D is the hardest, so I was very surprised that relatively many people solved it. How to solve this?

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

    Take the LCA of all blue nodes (bLca) and the LCA of all red nodes (rLca). Now iterate over every blue node b and if rLca is on the path from b -> bLca, then you can say for sure that you can't disconnect the blue and red nodes (since b has to cross over rLca and every red node also has to cross over rLca).

    Do the same logic for every red node (check if bLca is on the path from r -> rLca) and if that occurs for any blue or red node, the answer is no, otherwise yes.

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

    Here's what I did:

    Find the lca of the red set (say, u) and the lca of the blue set (say, v). Note that all red nodes are in the subtree of u, and all blue nodes are in subtree of v.

    If u = v, obviously it's not possible.

    If u is ancestor of v, then check whether v is ancestor of any red node. If yes there's a problem, if not it is possible.

    Similar case for v being ancestor of u.

    If none of the above (so lca(u, v) != u or v) then it's possible.

    How did you solve G?

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

      G seems to be a DP problem.

      Sort the initial array and Take the DP states to be dp(l,r,depth) and try breaking the state at all i between l to r.

      taking min of all dp(l,i,depth+1) + dp(i,r,depth+1) should works.

      I have not coded this solution but i think its correct.

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

      After getting u and v.

      For u, I am checking Is there any blue node in subtree of u by using IN-OUT time array ( I mean IN[u]<=IN[node] && IN[node]<=OUT[u]) If yes, then I will set flag for this case.

      Similarly for v.

      If both flags are set then answer is NO, else answer is YES.

      Is there any wrong in doing this ? Beacuse I am getting WA on tese case 3.

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

        Nothing wrong.

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

          Could you please provide test case 3 ?

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

            No. Find your mistakes by yourself. It is a useful skill on programming contests.

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

How to solve problem I?Just get wa on test 11.

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

    You move in a spiral path!

    In each move initially you keep painting new b squares. So initial uncoloured= a*a-b*b.

    Also finally you will be left with a a%b*a%b square in middle while in spiral.

    so in first type of move... (a*a-b*b-(a%b*a%b)) cells are covered with b per move.

    Then you can cover the middle of the spiral in a%b moves,

    My code...
    void solve(){
    	lli a,b;
    	cin>>a>>b;
    	lli left=(a%b);
    	a=a*a-b*b-left*left;
    	cout<<(a+b-1)/b+left<<endl;
    }	
    
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Move in a spiral inwards, instead of zig-zagging down.

    A small case where zig-zagging fails is 5 2 — you get 12 while the actual answer is 11.

    To (kinda) see why spiralling works, look at it this way — in each move, try to maximize the number of new squares you colour. For a while this will be b with both methods, of course, but when you spiral it reduces from b only when you reach the absolute center, whereas when zig-zagging you hit this for the entire last row.

    Not exactly a proof, just some intuition of why it might work.

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

How to solve G?

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

    Problem G is actually not difficultest.

    We can think about binary tree that each question divides into two sets (left child = "yes" person, right child = "no" person).
    Let $$$d_1, d_2, d_3, ..., d_n$$$, the depth of binary tree with $$$n$$$ leaves. Here, we should minimize $$$a_1 d_1 + a_2 d_2 + ... + a_n d_n$$$. If the minimum value is $$$Z$$$, then the answer will be $$$\frac{Z}{a_1 + a_2 + ... + a_n}$$$.

    Assuming $$$a_1 \geq a_2 \geq ... \geq a_n$$$, the optimal answer will hold $$$d_1 \leq d_2 \leq ... \leq d_n$$$. Then, we can say that node of person $$$l, l+1, ..., r$$$ will divide into $$$l, l+1, ..., k-1$$$ and $$$k, k+1, ..., r$$$.

    This observation will turn to simple DP problem, where recording $$$dp(l, r, d)$$$ the minimum sumproduct of node $$$l, l+1,..., r$$$ and current depth is $$$d$$$. The time complexity will be $$$O(n^4)$$$ and it passed.
    Also, if we think little more, we can erase $$$d$$$ from dimension in DP and the time complexity will be $$$O(n^3)$$$. (Sorry, this $$$O(n^3)$$$ solution was false...)

    P.S. Similar to Optimal Binary Search Tree Problem, this problem can be solved by $$$O(n^3)$$$ with Monge DP speed-up.

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

      You can do $$$O(n^3)$$$ with Knuth optimization:

      Let's $$$opt[l][r][d] = k$$$ is optimal index where we should divide $$$[l..r]$$$:

      $$$dp[l][r][d] = f(dp[l][k][d + 1], dp[k][r][d + 1])$$$.

      You can see that $$$opt[l-1][r] \le opt[l][r][d] \le opt[l][r+1][d]$$$.

      So for fixed $$$l$$$ and $$$d$$$ we could calculate all $$$dp[l][r][d]$$$ in $$$O(n)$$$ with two pointers technique.

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

        Yeah, that's what I meant by "Monge DP speed-up".

        By the way, this problem is Huffman Tree Problem when $$$depthlimit = \infty$$$, and it can be solved by $$$O(n \log n)$$$ in this case. So, in my intuition, we can speed-up faster than $$$O(n^3)$$$ in general case, but I did not come up with it yet...

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

      You say we sort an input array. Higher probability — lower depth. It's fine. But how does that imply we must divide any segment [L,R] to two segments [L,M] and [M+1,R] somewhere in the middle? Why can't any other division be better?

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

        Okay, so, let me explain. Let $$$d_i$$$ the depth of leaf $$$i$$$, and let's assume $$$d_1 \leq d_2 \leq d_3 \leq ... \leq d_n$$$.

        Note that $$$2^{-d_1} + 2^{-d_2} + 2^{-d_3} + \cdots + 2^{-d_n} = 1$$$ is the necessary/sufficient condition to be a binary tree. Let $$$d_1, d_2, d_3, ..., d_k$$$ already decided, and let $$$R = 1 - 2^{-d_1} - 2^{-d_2} - 2^{-d_3} - \cdots - 2^{-d_k}$$$. Here, since $$$d$$$ is an integer sequence which is non-decreasing, we can say that all $$$1-2^{-d_k}, 1-2\times 2^{-d_k}, 1-3\times 2^{-d_k},..., 1-R$$$ will appear in $$$s_l = d_1 + d_2 + \cdots + d_l$$$ for some $$$l$$$.

        That's why it is enough to split $$$[L, R)$$$, into $$$[L, M)$$$ and $$$[M, R)$$$, as long as $$$a_1, a_2, a_3, ..., a_n$$$ is sorted.

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

      Problem G can be solved in $$$O(n k)$$$ with Optimal Length-Limited Huffman codes. My submission, ideone

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

        dmkz used not the best implementation of the algorithm.
        Of course I have better 54980849.

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

        Is there an article where I can get familiar with that approach?

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

          I readed first article from searching in google by «Optimal Lenght-Limited Huffman codes». Huffman codes were developed for minimizing $$$\sum_{\text{letter}} \text{frequency}[\text{letter}] \cdot \text{codelength}[\text{letter}]$$$ so these codes solves problem by definition.

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

Will be there be an editorial put up?

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

    No. Better ask your questions here. Someone will answer.

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

How to Solve E?Getting wrong on TC 13.

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

    I am pretty confident that I solved problem E with different way to other people.

    Let's think about directed weighted graph $$$G$$$ with $$$m+1$$$ vertices, where vertices numbered $$$0, 1, 2, ..., m$$$. We will add edges as follows:

    • We will add edge from $$$a_i-1$$$ to $$$b_i$$$ with cost $$$1$$$.
    • We will add edge from $$$j$$$ to $$$j-1$$$ with cost $$$0$$$. ($$$j = 1, 2, 3, ..., m$$$)

    Then, we only have to search the shortest path from vertex $$$0$$$ to $$$m$$$. We can do with 0-1 BFS in $$$O(n + m)$$$ time.

    However, the constraints says $$$m \leq 10^9$$$. So, we will get Runtime Error (or Time Limit Exceeded) on Test 13. We can solve this issue by doing coordinate compression, and $$$m$$$ will be at most $$$2n+2$$$. The bottleneck of time complexity is the time of coordinate compression, so this problem can be solved by $$$O(n \log n)$$$ or $$$O(n \times \lceil \log_n m\rceil)$$$ with radix sort.
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I think this is the simplest solution:

    It's pretty clear that the greedy strategy works. Say the lowest id function you need is id x. Consider all intervals that contain x. Of those, include the interval which ends latest.

    To implement this efficiently, sort the intervals by their start time. Now process all intervals which contain the next program you need and choose the one that ends latest. You need just a few integers for state: the current interval you're considering, and the next program you need. This runs quickly, just a sort in O(nlogn) and a linear scan.

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

      Can you explain a bit more on how to consider all intervals that contain x?

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

        Sure. As I said in my answer, process all intervals in order of their start. An interval is a candidate if its left bound is <= x. Of all candidate intervals, take the one with the maximum right bound. Keep a pointer in the list of sorted intervals to know where to pick up for the next x. Maybe my code will be more clear? https://pastebin.com/N1PHuedG

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

          Thanks! I actually had problems maintaining the pointer to know where to pick up for the next x in sample test case 2. After choosing the first interval, next x became 6. Now 6 lies in second interval but not in the third interval. But now I am thinking that we can actually ignore those types of intervals because they won't contribute to the answer anyways.

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

Can anybody explain why the sample case 2 of problem G's answer is 2/1? Thank you

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

    You have to guess one of 4 people in 2 questions in worst case. You must ask the first question about any two people. With any other strategy, there could be a situation when 2 questions are not enough.

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

What's the mathematical proof behind C, I see everyone just looping until min(n, p (sometimes 2*p or 4*p) )?

Also can someone give a hint for problem L?

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

    In C, note that every number we mark is of the form $$$0+1+2+...+i = i(i+1)/2$$$, modulo p.

    If you substitute i = 2p, this is 0 (modulo p), and then the pattern just repeats because 2p+1 is 1 mod p, 2p+2 is 2 mod p, ... so you won't mark anything new from there.

    L is just geometry — since the circles are guaranteed to have exactly 2 points of intersection, the region of intersection is going to look something like a lens (bloated towards one side, maybe, depending on the radii). The point you want is the midpoint of the line joining the top and bottom of this 'lens', and the radius is the distance of this point from either circle (note that any point on this line will be equidistant from both circles)

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

      nishank.suresh do you mean the line that is between the two centers?

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

        The midpoint will lie on that line, yes, but it will not (necessarily) be the midpoint of that line as well.

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

          https://mirror.codeforces.com/gym/102215/submission/54724829 that is what i did here but i got a wrong do you know why?

          i simply got the four intersection points with the two circles and got the middle two.

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

            You don't need to find any intersection points.

            Hint 1

            btw, cool link: https://csacademy.com/app/geometry_widget/

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

              but we will have to find C and D which result from the intersection of the circles and the line between the centers.

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

                No.

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

                  and then we can scale any center by that distance to get C?

                  another thing i want to see test case 7 (the one that gets WA) do you know how?

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

                  =======================

                  Man, after these 3 hints it become trivial. Get your pen and paper and find what you need.

                  If you don't know how to divide a segment with a given proportion, read about it.

                  Test 7 contains some zeroes, I think you divide by zero.

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

                  thank you

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

                  dalex.can you send test case 7?

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

      Why did I get TLE on test 4? Can someone explain? https://ideone.com/hJpngs

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

        Change unordered_set to vector/array of 1e7 elements.

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

          Thanks, got it AC now, but can you explain why unordered_set would not work in this case?

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

How to solve problem K? Does a greedy solution work?

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

    You can iterate over all possible permutations of result (RGB, RBG, GRB and others).

    For each permutations next greedy approach works:

    • color 1 to the first deck;

    • color 3 to the second deck;

    • color 2 to the second deck, if there is only color 2; otherwise to the first deck.

    After all cards were processed, you need check that the first deck is consistent (it should be exactly 1...12...2).

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

    I thought K is top2 or top3 easy problem (along with I), but all participants started chasing yellow guys who solved problems in more or less alphabetical order. I think they just didn't read problems in the end till 2nd hour.

    Solution for K
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the Problem J? Thanks.

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

    You can represent every Jedi with the sum of it's three parameter to use the dark force

    Then you should represent it again with the sum of the two smallest parameter.

    Then sort the second representation and for every one in the first array do a binary search on the second array for the number of elements that smaller than it by 2 (to be strictly greater in two parameters ), there only one check that if the sum of Jedi is greater than it's min 2 parameters by 2 then you must subtract one from the binary search result.

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

      Thanks for your solution.

      I just now realized the real problem description instead Jedi only can use once dark force.

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

How to solve F and H?

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

    In H you can just ask for every bit and generate the number. firstly, ask for the first bit in all the elements and count the number of Integers from 0->n that have one in this bit and you can simply know the bit of the required number and the elements that have the same bit then count again number of ones in the next bit and also have the same previous bits like the required one by this way you can know every bit in half questions from the previous one .

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

      Thanks for your help.

      I think problem H is just like Power Arrangers from GCJ Round 1C.

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

        Problem H is taken from the old edition of the Cormen's book (the name Thomas was not just a random name!). Interestingly, this problem was removed from newer editions.

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

    In F you can sort the input twice (two different arrays) the first time by the attack the second is by hit point in increasing order and for every one in the first array you see from the second one the elements that have hit points less than or equal to it's attack point and keep track of the largest two attack points from the second array and you sure you can attack it and then you must check if it can attack you There only one case so you track two integers is that if you can attack yourself so if the largest attack point is like yours so you take the second Integer (both Integers can be the same).

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

Can Yo please tell me the solution for problem M?? It's okay if you just show me a code Thank you for this great contest