Блог пользователя Errichto

Автор Errichto, 3 недели назад, По-английски,

You can download my codes to all problems here.

I will write a full editorial in the next few days. Now you can read hints and short solutions.

750B - New Year and North Pole

hint

750C - New Year and Rating

hint1
hint2

750D - New Year and Fireworks

hint1
hint2
solution

750E - New Year and Old Subsequence

hint1
hint2
hint3
hint4

750F - New Year and Finding Roots

part1
part2
part3
part4
part5

750G - New Year and Binary Tree Paths

hint1
hint2
hint3
hint4
hint5
hint6

750H - New Year and Snowy Grid

hint1
hint2
Разбор задач Good Bye 2016
 
 
 
 
  • Проголосовать: нравится  
  • +168
  • Проголосовать: не нравится  

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

It is deleted

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

Didn't get the last part "solution" of editorial of E-problem. If someone can explain it again with an example it would be great :)

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

    Consider the regular expression .*2.*0.*1.*7.* and build its automaton:

    It's evident that if the requested (sub)string matches this expression, then it contains the "2017" subsequence. Now we are to delete some letters from it to exclude the "2016" sequence.

    Weigh the automaton transitions: W(0 -> 0 with '2') = 1, W(1 -> 1 with '0') = 1, etc — to stay in the current state when receiving a letter which moves us to the next one, we should delete this letter. Also, W(3 -> 3 with '6') = 1 and W(4 -> 4 with '6') = 1 — if we've already taken "201" or "2017", we must drop every '6' we encounter. Other edges not mentioned above have weight of 0.

    Define a 5x5 matrix m for a string s, such that m[i][j] (i <= j) is a minimal cost to get from state i to state j, feeding the automaton with s's characters.

    Suppose we have two strings, p and q, and their matrices, mp and mq. We can easily merge them, obtaining a matrix for their concatenation (looks similiar to Floyd's algorithm).

    Notice that matrix merging operation is associative. So, we can build the RMQ on it.

    When using segment tree, we gain O(n*log n + q*log n) time and O(n) space solution, online.

    23454158

    It could be improved up to O(n + q) using RMQ to LCA conversion and some O(n)/O(1) (precalc/query) LCA algo (e.g., Schieber-Vishkin).

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

      thanks :)

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

      Hey , I have a doubt , have a look http://pastebin.com/TwgNC70X

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

        For "1", the matrix should look like:

        __|_____________
          |  0 ∞ ∞ ∞ ∞
          |  ~ 0 ∞ ∞ ∞
          |  ~ ~ 1 0 ∞
          |  ~ ~ ~ 0 ∞
          |  ~ ~ ~ ~ 0
        

        For "6":

        __|_____________
          |  0 ∞ ∞ ∞ ∞
          |  ~ 0 ∞ ∞ ∞
          |  ~ ~ 0 ∞ ∞
          |  ~ ~ ~ 1 ∞
          |  ~ ~ ~ ~ 1
        

        And for "16":

        __|_____________
          |  0 ∞ ∞ ∞ ∞
          |  ~ 0 ∞ ∞ ∞
          |  ~ ~ 1 1 ∞
          |  ~ ~ ~ 1 ∞
          |  ~ ~ ~ ~ 1
        
        result[i][j] = min(a[i][k] + b[k][j] for k in range(i, j + 1))
        
    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I implemented the idea as per your explanation, but getting TLE. 23502332. Any suggestions?

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

        It seems that you store too much data at a single node of the segment tree. There are only 14 numbers need to be take care of. (Pay attention to the constraint j>=i)

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

          15, actually. However, it is possible to get AC even without this optimization.

          Seems that you allocated too few nodes. 1 << 19 < 4 * 2e5.

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

            I guess number of nodes in segment tree is at most 2^(ceil(log2(n))+1) = 2^19. Please correct me here.

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

              Oh, you are right! Always thought that the upper bound is 4 * n. Thank you!

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

        There are plenty of ways to optimize your code.

        1. As tt.anhquynh suggests, you may use 1-dimensional arrays of size 15 instead of 2-dimensional 5x5 matrices.
        2. Replacing vectors with arrays (std::array or just plain arrays wrapped with a struct) will prevent your program from using dynamic memory. Heap manager would be just happy.
        3. Get rid of loops in matrix merging. Yes, it will speed up greatly. And yes, it will look ugly.
        4. Switch to non-recursive segment tree implementation.
        5. Add cin.tie(nullptr); at the beginning of main to prevent from flushing stdout whenever you read something.
        6. Submit under GNU C++14. It will use GCC 6.2 which has a bit better optimizer.

        I suppose using any of these (probably, except the last one) should be enough to get AC. Applying all these techniques together, I managed to get AC in less than 400 ms: 23491398.

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

          Thanks, got AC with applying 1 and 2. 23512670. Also, it was the first time, I heard of non-recursive segtree. Thanks for that too!

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

      Nice solution! Help me a lot! Thank you very much!

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

Can C be solved using Binary search ? If YES , then how ?

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

    Yes

    Binary search over the rating before first round

    Check if it's possible to have that rating without problems/conflicts in divisions at the start of all contests

    if no problems try bigger numbers

    if there are problems like:

    1: rating is < 1900 and we are supposed to be in div1 in current contest: try bigger numbers

    2: rating is > 1899 and we are supposed to be in div2 in current contest: try smaller numbers

    The answer is infinity if all contests are in div1

    Solution Link

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Hi [user:Errichto],
For problem D, isn\'t the solution you have suggested is of O(2^n*k) ?
that is., for each of the state (x,y,dir,level) processing time would be O(k) and there would be O(2^n) such states since for each level i, we would have O(2^(i-1)) different values for (x,y,dir)
  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    The tricky thing here is the upper limit on t-s.

    Since the firework cannot fly further that |kt| from the startpoint after k iterations, you'll find yourself in the (2nt)^2 square that is equal to 300 * 300.

    Hence O(n * 2^n) turns to O(n^3 * t^2)

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

    I tried to implement his solution. It's giving me the right output of course but I am getting TLE on higher recursion levels since as you have pointed out, it's exponential(at least my code). Can someone help me out?

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

      There can be at-most 2^29 particles after N explosions. If you consider a state of the particle in terms of Grid,Level,Direction (X,Y,T,Dir) from Pigeon Hole Principle there must exist (at some point 2^k > 321^2 * 30 * 3^2) two or more particles starting in the same Grid, moving in the same direction at the Same level. For these kinds of particles, you only need to track one instance of it. By this way you wont be keeping track of more than 321^2 * 8 particles at an instance.

      This leaves you with a complexity of O(Height*Breadth*Levels*Distance*Directions) O(N^2 * 30 * 5 * 8) O(N^2)

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

In a way, I had a very similar solution to the intended solution for E. Instead of a segment tree storing a 5*5 matrix, I implemented a sparse table to the same effect (23455422). As a result, the memory limit acted and I had to make a last-minute compression to take out the cases where i>j. I wonder if the memory limit was imposed to prevent the sparse table solution.

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

I can't figure out what's wrong with my submission for C : 23443890

Where is the mistake in the code ?

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

    lower must be -inf

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

      Thanks a lot. My bad — I thought ratings couldn't be negative. Figures. If ya think ratings are low now — they can always go lower. Reminds me to read the question properly and never take anything for granted.

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

Still can't understand E.. How by removing digits we can get longer segment? (about T[i][j]).

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

    I understood it as while merging segments, T[i][j]= min(left.T[i][k]+right.T[k][j]); So T[i][j] for some segment represents the minimum chars to be deleted to produce substring i+1..j of 2017. This also means that the 0..i part of 2017 will be taken from the left of this segment.
    Look at my submission to see the assignment of matrix for leaf nodes. Lets say we encounter a 0, then mat(1)(2) becomes 0 as if we are taking 2 from left side, then this segment can provide 0 to complete 20. If we skip this 0, then it allows 2 to be taken from left side of this segment, and to skip 0, mat(1)(1)= 1. It wasnt very clear to me in beginning how its working but give it some time and then it would be clear.

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

    Perfect example would be something like 20110667.Here optimal solution is to remove the zero at second place.For the segment(20) in the tree t[0][1]=1(we will have to delete 0).Although t[0][2]=0 but when it propogates upwards it is not optimal because we will either have to delete 2 1's or 2 6's

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

thanks!

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

In problem E, I stored another kind of information in the segment tree.

Suppose we have some string s1 ("2017", for example) and some other string s2 ("2016", for example). We want our current segment to contain s1 as a subsequence and do not contain s2 as a subsequence. What is the minimum number of deletion we have to make?

This information could be updated using the answers of the node's children in the segment tree.

For example, let s1 = "2017", s2 = "2016".

Then we have to consider the following values:

  • AnswerOfTheLeftChild("", "2") + AsnwerOfTheRightChild("2017", "2016")

  • AnswerOfTheLeftChild("2", "20") + AsnwerOfTheRightChild("017", "016")

  • AnswerOfTheLeftChild("20", "201") + AsnwerOfTheRightChild("17", "16")

  • AnswerOfTheLeftChild("201", "2016") + AsnwerOfTheRightChild("7", "6")

  • AnswerOfTheLeftChild("2017", "2016") + AsnwerOfTheRightChild("", "6")

I generated all of such pairs (s1,s2) ad figured out, that there are only 14 of them. So it is possible to store 14 values in the segment tree node.

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

I managed to solve problem C with a different approach.

Keep two variables: from denoting the smallest possible value for the rating, and to denoting the highest possible value for the rating.

if at some point you were in a div2 contest and your smallest possible rating is larger than 1899 print Impossible, or if you were in a div1 contest and your highest possible value is less than 1900 print impossible.

Otherwise, if you are at a div2 contest then to = min(to, 1899), or if you are at a div1 contest then from = max(from, 1900), then increase (or decrease) both variables by the amount of points you earned at the current contest. If at some point from was higher than to print Impossible.

At the end, the rating is equal to the highest possible value which is to.

Unfortunately, during the contest I was hacked because I forgot that the initial rating can be negative :(

Accepted Code

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

I have an alternative solution for problem C. For the most part of the contest, I simply missed the simple solution.

Here's what I did instead.

Thread separately the cases when I have only one type of divisions (either div1 or div2). (Actually, solving the case when I have only div2 contests should have given me a huge hint for the simple solution earlier in the contest, but I had a bug in my logics).

Now, there will be at least one contest when I'll change my division (from div2 to div1 and vice-versa). Let's take the first one and suppose I changed from div1 to div2 (the other case is identical). Then, rating[i — 1] + change[i — 1] = rating[i].

But rating[i] <= 1899, so rating[i — 1] + change[i — 1] <= 1899. So rating[i — 1] <= 1899 — change[i — 1]. (change[i — 1] is negative, since I fall in div2, so no problem here). rating[i — 1] will be between 1900 and 1899 + abs(change[i — 1]).

But abs(change[i — 1]) <= 100, so actually rating[i — 1] can take maximum 100 values. After I know that rating[i — 1] has a certain value, everything else is uniquely determined, so I can just simulate the values.

This gives me a O(max(changes) * n) solution. The implementation is pretty painful, but this is the price I payed for missing the simple solution: 23459419. Lesson learned, next time spend more time thinking for something simpler, it will pay off :) Good to know retrograd still loves me despite my newbie performances. <3 <3 <3

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

An alternative solution for D:

We again use the observation that only cells within 150 can be coloured so there are at most 300*300 cells to keep track of.

Suppose we are finding which squares are coloured by some firework of depth k, and we already know which squares are coloured by everything in the right 'subtree' (note there are at most 300*300). Then to get which squares are coloured by the left subtree, we can simply reflect them about the line formed by the the current firework.

Thus we can colour any single path in the 'firework tree' (for example we could just dfs, recursing on only the right subtree every time) and then reflect the tree as we go back up.

Then, the complexity, where S is the grid size, is O(S^2 * depth).

A last detail is how do we do the reflection? There are only 4 types of flips depending on which way the current firework is going: up/down, left/right and the two diagonals. So we can just do some slight case bashing with the coordinates...

Code: http://codeforces.com/contest/750/submission/23437226

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

I stucked and tried to solve third problem C "New Year and Rating" in the competetion. However, I couldn't solve. My codes reach 100 lines, but when I look the top-tier programmer from Final Standings, they solved about 10-15 line of code. It is clear that I have a trouble in way of thinking.

So, I wanna ask, why I couldn't? Do I need to work some algorithm design topics or just is it about experience?

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

    This one's quite ad-hoc to be honest. With this problem, you should go by the concept of intersecting ranges, which are determined by the inequalities x <= 1899-c[i] or x >= 1900-c[i]. If you go by that concept, your code should be very short like the top tier guys. Not to toot my own horn, but my code for this problem was also around 10-15 lines ;).

    Most of this ability to think of simpler solutions comes from experience and practice. The more problems you've done, the more likely you will have seen the techniques used in a contest problem.

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

    I felt the same after the contest.
    I wanted to ask about it in a blog post, but I think this is a good place.

    Does anyone know any similar problem that is solved with min / max?

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

Can someone explain me this testcase of problem B(New Year and North Pole). 1 80000 South. Answer for this case is NO. But as for me we start at North Pole, go south 40k,implying we are at North Pole,again go south 40k, we end up at North pole Right.

Thank you.

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

    First, you have to go 20k, when you reach the South pole. However, you can't go south from the South pole.

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

    "If at any moment of time (before any of the instructions or while performing one of them) Limak is on the South Pole, he can move only to the North." So after having completed 20000 km of journey, Limak is now at South Pole, but from South Pole you can only go North, but the instruction had said about going South, thus the description is no longer valid. So answer will be NO.

    The important thing which many of us missed is to also check the validity of the instructions.

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

Hi, Please anyone help .. My submission on Problem E is getting Runtime Error.. here is my code

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

very good style of editorial

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

Can someone explain the problem G? It is not clear. Thanks in advance.

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

http://codeforces.com/contest/750/submission/23469026

Can someone please spend some time and help point out where did I made a mistake? I think I should've blocked all causes of Idleness TLE but it doesn't.

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

Can somebody explain me the concept of duality? Or at least what I need to know about it for solving H? I know about duality and the dual plan from the voronoi diagram but I don't see any correlation. Thank you in advance!

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

So... what's the complexity of solution in G problem? I've accepted O(log6), but I had some hard times trying to optimize it. My dynamic part works O(log4) and I'm not sure how to do it faster :'(

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

    O(log5): fix the sum of popcounts of a and b rather than fixing each popcount separately and then do dp bit by bit, keeping track of current sum of popcounts and making sure a+b is equal to something.

    I suspect it can be done in O(log4) if we don't fix the popcount sum but I'm not able to work out the details.

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

      "It turns out that lengths of sides are enough to compute exact value of LCA. Find a formula on paper or see my code (the top of this page)"

      Can anyone provide me a paper write about that or give me a hints to prove its correctness. It is still not clear to me.

      Many thanks.

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

        Same, need help here :(

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

          Let's fix lengths of sides (la and lb), and let's denote LCA by v.

          Then, s = av + b, where a depends only on la and lb. b depends on actual nodes chosen but you can see that 0 ≤ b < a always.

          From discrete mathematics (or common sense) we know that given m > 0, every number x has unique representation x = pm + q such that 0 ≤ q < m.

          Therefore, there is only one possible set of values for v and b: and b = s - av.

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

Errichto, can you please point some problems that inspired problem E's solution? Thanks in advance! (It would be very useful if problem authors could point some similar problems to those they just made for the round. There are some pretty cool recurrent-but-not-so-famous techniques that just won't stop showing up!)

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

    +1 to you. While looking upon solutions, almost everybody who solved it had a similar approach. They have come across this before.

    Some similar problem please ?

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

    Do you know "calculate n-th (n ≤ 1018) Fibbonacci number" problem?

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

      Yes, with fast exponentiation. Solutions for problem E use fast exponentiation?? (I still haven't had time check the solutions, but this is a surprise to me, because I have solved some tough matrix exponentiation problems and this idea didn't show up to me during the contest... Actually, the idea of using matrices didn't cross my mind in the first place)

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

        Well, here you have not exponentiation but "product on the range [l;r]" (and with wierd multiplication)

        And I call this thing multiplication, because it is similar in many aspects (what is important it is associative, but you may also "multiply" block matrix or "multiply by vector" etc)

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

    This great post gave me the key idea to solving problem E. See also this article, which dives deeper and focuses on the implementation.

    They also have Russian translations (well, the second one was originally written in Russian and then translated into English). Don't miss this nice article (Russian only, sorry).

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

    Ok, I've just solved problem E and realized the real point of the exercise. The recurrent technique you should be familiar with is not only segment trees and monoids (the algebraic structures over which segment trees are built upon). You should also be familiar (at competitive programming level!) with DFAs/NFAs and their monoid behavior when represented by matrices. What I mean with "familiar at competitive programming level" is that you should be capable of adapting the representation/monoid to solve the problem (the solution is not a straightforward application of the technique).

    Thanks to SirNickolas, the best reference: http://jkff.info/articles/ire/

    My solution: 23493355

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

these kind of editorials are the best step by step hints rather than full blown solution.

i encourage codeforces to adopt spoilers inside the editorial

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

Can someone explain how we can get these convertions in D ?:

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

    Set up two arrays of changes in y-coordinate and x-coordinate of the eight directions like this:

    dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dx[8] = {0, 1, 1, 1, 0, -1, -1, -1} where -1 refers to North/West and 1 refers to South/East. So dy[0] and dx[0] means the fireworks moves towards North (0 degree), dy[1] and dx[1] means the fireworks moves towards North-East (45 degrees), etc.

    When the fireworks splits, two new fireworks of +45 degrees and -45 degrees are formed, so you can get the new directions by moving your pointer to adjacent elements.

    (dir+1) % 8 should be quite easy to understand (turning 45 degrees clockwise), but for anticlockwise turns we add 7 because (dir+7) = (dir+8-1).

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

Can someone explain how to do G in O(log(s)^4). I could only come up with a O(log(s)^5) solution as described here.

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

After going from LCA to its last unknown neighbour, we should check that neighbour's neighbours and also their neighbours (in total, checking all vertices withing distance 2).

What does it mean in F editorial? Can't get this part for hours >_<

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

    You know that that max distance of the root from the LCA is atmost 3.

    Go to the last unvisited neighbour of the LCA. Let it be v1 (v1 is at distance 1 from LCA). v1 has two unvisited neighbours. Let them be v2 and v3 (both are at distance 2 from LCA). Now, each of v2 and v3 have atmost two unvisited neighbours each. Let them be v4, v5, v6 and v7 (first two are connected to v2 and last two are connected to v3). All four of these v4, v5, v6 and v7 are at distance 3 from the LCA. The root is guaranteed to be one of these (from v4, v5, v6 or v7).

    If you can't understand the above explanation, drawing a diagram might help. :)

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

Looking forward to a more detailed solution for problem H, or any materials about duality in this problem?

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

    This duality is min cut max flow (you can see this problem for a similar idea: https://code.google.com/codejam/contest/3014486/dashboard#s=p2 ).

    We want to know "is there a flow between the top left corner and bottom right corner with value at least 2?". Here, we have a grid graph, and we can only move in 4 directions. We can take the dual to convert it to "is there a cut with cost at least 2?". This is equivalent to finding "is there a cut with cost at most 1?" and negating the answer.

    What is a cut of the grid graph? It turns out it is an 8-connected path from the bottom or left side to the top or right side (excluding the top-left corner and bottom-right corner).

    Here, grid cells that are blocked cost 0, and grid cells that are empty cost 1, and we want to know if a path exists with cost at most 1.

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

Can Someone explain the dp solution of the D problem. I'm not able to solve it

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

So in problem B, we can go west and east any number of kilometers, but we are not allowed to go 20,001 KM to the South for example ?

In other words, in this case

3 1 South 1000000000 East 1 North

I am allowed to go 1000000000 KM to the East.

But in this case,

1 40,000 South

I am not allowed to move around the earth :D logic xD