Errichto's blog

By Errichto, 3 weeks ago, In English,

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
Tutorial of Good Bye 2016
 
 
 
 
  • Vote: I like it  
  • +168
  • Vote: I do not like it  

»
3 weeks ago, # |
Rev. 7   Vote: I like it +5 Vote: I do not like it

It is deleted

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

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 weeks ago, # ^ |
    Rev. 3   Vote: I like it +79 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      thanks :)

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

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

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

        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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

        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 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 weeks ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

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

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

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

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

        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 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

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

    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 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
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 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Where is the mistake in the code ?

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

    lower must be -inf

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

      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 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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

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

    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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks!

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

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 weeks ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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 weeks ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

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 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    "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 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

very good style of editorial

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

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

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

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 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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 weeks ago, # ^ |
      Rev. 2   Vote: I like it +15 Vote: I do not like it

      "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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Same, need help here :(

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

          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 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    +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 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

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

      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 weeks ago, # ^ |
        Rev. 4   Vote: I like it +13 Vote: I do not like it

        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 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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 weeks ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    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 weeks ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

(dir + 1) % 8
(dir + 7) % 8
  • »
    »
    3 weeks ago, # ^ |
    Rev. 4   Vote: I like it +11 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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