arsijo's blog

Lyft Level 5 Challenge 2018 — Final Round — Editorial
By arsijo, 6 years ago, In English
Tutorial is loading...

Author: arsijo

Developer: stanislav.bezkorovainyi

Tutorial is loading...

Author: arsijo

Developer: stanislav.bezkorovainyi

Tutorial is loading...

Author: stanislav.bezkorovainyi

Developer: stanislav.bezkorovainyi

Tutorial is loading...

Author: Lewin

Developer: Lewin

Tutorial is loading...

Author: Noam527

Developer: Noam527

Tutorial is loading...

Author: Noam527

Developer: Noam527

Tutorial is loading...

Author: Lewin

Developer: Lewin

Tutorial is loading...

Author: _h_

Developers: _h_ and majk

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

Comments Comments (28)
| Write comment?
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Div2 C. Why my solution failed on test no. 17 I used Difference array and Binary search.? http://codeforces.net/contest/1075/submission/45302142

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

    Not sure if this is your case, but I also used the same technique and got WA on test no.17 Maybe this test case might help you?

    2 3
3
5
1 4 1
2 100000 2
1 4 3

    My code outputs 2 but now I see that it should be 1...T_T

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +56 Vote: I do not like it

Overall complexity of Div.2C should be O(nlog(n)) because of sorting.

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

Anyone know the tag for problem C Div 2? Solution presented above is greedy?

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

    Binary Search/Two Pointers. But I think it is more helpful to view it as adhoc where you have to make observations. In this case main observation based on vertical lines span the whole grid, and no horiztonal touching.

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

Div2C: I did everything right, but forgot to write sort()... I am feeling so bad about this alexa play despacito

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

Nice !

→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Div1D is not original.

Here is the same problem in one of the Indian Regionals — https://www.codechef.com/KGP17ROL/problems/XORQUERY

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

    E and F aren't great either. My understanding is that CF wants to encourage problem writers and the bar for problem quality isn't set too high, so unless contest organizers want high quality original problems (which wasn't the case this time but in the past for this reason some companies had problems set by their own engineers and not outsourced) you should not have high expectations.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    Hey,

    I did not intend to copy/steal a problem by any means. Neither me nor the testers knew of this problem (and also no other task that is similar to div1D), otherwise it would be brought up. I'm sure you understand that we want to have tasks with as high quality as we can, and also being original. Still, I'll try to look deeper for tasks similar to mine, but honestly, I think it's impossible to assure my problems are original.

    Anyway, I hope you still managed to enjoy some other tasks from the round :).

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

Hi, Can someone tell me whats wrong with Code??

Interactive Problem

Thanks in Advance

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

    The problemis that you need to run a bfs to find the closest vertex instead of finding any vertex like you do with your dfs.

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

Isn't W(3,5)⊕W(5,2) equal W(2,2), not W(3,2)?

Because [3⊕4⊕5]⊕[2⊕3⊕4⊕5] is equal to 2.

And that would mean that W(a,b)⊕W(b,c)=W(a,c)⊕b.

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

    In the presented solution, we look at the subarray by its end borders. So,

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

Can anyone help me out with Div. 2 F? I'm getting WA on test 14. I'm using dsu and merge small-to-large, and but I cannot tell what my error is and this problem is quite hard to debug.

45341296

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

    update: I fixed my error, a pretty big one, actually. I was updating the subtrees with p[l]^p[r] instead of x^p[l]^p[r].

    → Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Thanks a lot for detailed explanations!

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

Can anyone explain the dp part of Div1-C, Also what are c1,c2..,c6 wrt this question?

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

    We need to find 3 points, such that |x1 — x2| + |y1 — y2| + |x2 — x3| + |y2 — y3| + |x3 — x1| + |y3 — y1| is maximal. We are going to try all possibilities of assigning + or — to each of these pairs. For example if we have +--+-+, we are going to have (x1 — x2) — (y1 — y2) — (x2 — x3) + (y2 — y3) — (x3 — x1) + (y3 — y1), which evaluates to 2*x1 — 2*y1 — 2*x2 + 2*y2 + 0*x3 + 0*y3. c1 here is the coefficient next to x1, c2 is the coefficient next to y1...c6 is the coefficient next to y3. So we calculate arrays P, Q, R as in the editorial and then do dp to get the maximum for such combination. The dp state is [current point][taken points]. You can also check out my implementation 45365331.

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

      Thanks a lot :) , I got majorly confused on how taking all possible combinations wont give wrong answer because we are taking the cases are not possible too, For those who are confused on this part -> max value of the expression can be |x1 — x2| + |y1 — y2| + |x2 — x3| + |y2 — y3| + |x3 — x1| + |y3 — y1|, any other case will be less than or equal to this, Hence this wont affect our maximum. With similar reason we can prove why this wont work for minimum.

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Thanks, stanislav.bezkorovainyi for writing a descriptive and well explained tutorial for problem 1074A.

→ Reply