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

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

This is the preliminary version of editorial. Expect bugs. Some changes might happen!


1150A. Stock Arbitraging

Tutorial

1150B. Tiling Challenge

Tutorial

1150C / 1149A. Prefix Sum Primes

Tutorial

1150D / 1149B. Three Religions

Tutorial

1150E / 1149C. Tree Generator™

Tutorial

1149D. Abandoning Roads

Tutorial
Challenges

1149E. Election Promises

Tutorial
  • Проголосовать: нравится
  • +258
  • Проголосовать: не нравится

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

Pretest for B were weak :(

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

Thank you for a lightning fast editorial.

What was that sudden increase in difficulty curve from problem C to D (Div. 2)?

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

Please, add author solution too :(

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

I think that, at least, main tests 37 and 40 for Div2B should have been in the pretests.

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

Can someone help me find a counterexample to the following logic in div1 D:

  • Find connected components if we use a-edges only

  • Discard all b-edges with ends in the same component

  • In the remaining graph, find shortest path from 0 to each p that uses minimum number of b-edges
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I'm trying to figure out this myself :/

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

    If I understand you correctly, this should be a small counterexample for $$$a=2$$$, $$$b=3$$$. The dotted lines are heavier, solid lines are lighter:

    You can go from $$$1$$$ to $$$5$$$ using two heavy edges ($$$1 \to 2 \to 5$$$, cost $$$6$$$), which is more optimal than using one heavy edge ($$$1 \to 3 \to 4 \to 5$$$, cost $$$7$$$).

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

    UPD: Deleted, sorry

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

The contest had quite an interesting difficulty distribution. Problem B took quite a bit of time to implement (the solution was extremely simple, though) where C was absolute lolly and D had only 35+ solve in contest time (a little better in the Div 1 version, probably 50+).

One other thing, there's a spelling mistake in the problem B name. You missed an 'l'. :p

Thanks for the super fast editorial.

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

    One other thing, there's a spelling mistake in the problem B name. You missed an 'l'. :p

    Fixed! shame on me

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

In Div1.C, you wrote that $$$δ \text{ (the final depth, might be non-zero)}$$$. Maybe it is more clear to say that $$$δ$$$ is the total depth change in that block?

»
6 лет назад, # |
  Проголосовать: нравится +97 Проголосовать: не нравится
Challenge to D about 2^o(n) solution
»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Can't div2 D be solved searching by searching subsequence (using precalculated positions for each symbol) and marking them as used? We have 6 order varinats to search subsequences: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).

It goes into $$$O(q \cdot 250 \cdot 6)$$$, but algorithm looks like not work :(

my try

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

    Try this testcase: The Word of Universe is "abadadab", and there are two religions in that moment. Their descriptions are "abab" and "adad".

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

    the long word "abcbdefe", and two subsequences "abef", "bcde"

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

    I think it can be implemented properly with some backtracking, but not sure how that affects the complexity.

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

Div2 D is a nice problem,though i didn't solve it during contest.. (also got fst on C..nooo..)

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

For D, during contest I didn't realize we can ignore components of size $$$3$$$, so I had a higher complexity and with no optimizations my solution would get TLE. With the following heuristic I was able to pass main tests: in Dijkstra, if the shortest path from $$$1$$$ to $$$i$$$ is $$$2$$$(I used $$$4$$$ in contest but $$$2$$$ also passes main tests, interesingly $$$1.99$$$ doesn't pass) times shorter than the shortest path from $$$1$$$ to $$$i$$$ with some $$$mask$$$, ignore this $$$(i, mask)$$$ state. Can someone prove that this works or find a countercase?

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

I don't understand why in B div1 you obtain the shortest prefix in that way. Why can't you choose a character from the same prefix? Why is it always making the prefix bigger, what if there is a character that we can use in the current prefix?

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

Can somebody please explain the solution for Div2D? What exactly are we doing in the DP part? Thank You

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

Just a little request to all the coders who conduct the rounds try to please explain the editorial with the help of examples. I know this will take little bit of your extra time but it will help us how you approach the given problem. Example there are lot of people who are not able to understand the editorial of question D but if you try to explain us with the help of an example they will understand better. It's up to you guys but please think this once. It will help us to learn more and save our time. Thankyou Happy coding.

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

    If I find some free time this week, I'll try to rewrite this editorial, e.g. to include some examples or write the explicit DP transitions.

    I even thought about writing some interactive app where you could fiddle with the inputs and see how DP states change, but it's imho quite time-consuming. No promises for this one, then.

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

The solution to div1 D is really beautiful

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

Can anyone prove that Div1D is NP-hard ? I might learn some way to deal with that type of problem to avoid some unnecessary ideas.

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

    As nobody published their proof, let's go with mine:

    Reduction

    On that note, I think probably nobody solving the problem actually proved that the problem is NP-complete — I guess they had some sort of intuition that they shouldn't be able to solve it in polynomial time.

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

Could someone elaborate more on the solution to Div2 D/Div 1 B. I don't quite understand how we can use the helper array to check for a valid construction without keeping an index to the Words Of Universe string in our dp.

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

Could anyone recommend a good textbook about some advanced game theory (with all that ordinal nimbers, hackerbushes etc)?

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

For div1-D I implemented this code using a priority queue. This is tutorials logic. And took 639ms.

But when I implemented same logic using a single normal queue it took 280ms. ( My code ).

Can any one tell me why without priority queue Dijkstra working much faster. Please help me to understand the complexity for 2nd code ( without priority queue ) . I understood the complexity of the 1st code ( with priority queue ).

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

I think the transition has problem:

when string is : "abdabc" , and then the s[0] is "ad", the s[1] is"b",s[2] is empty,the dp[2][1][0] should be 4 but the program show the dp[2][1][0] is 2,and the problem is caused by the wrong transition:dp[1][1][0] can not update the dp[2][1][0] by just using the helper arry

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

I can hack you with the following data:

the origin string is "abd",3 operations + 1 a + 1 d + 2 b the answer should be YES YES NO but yours is YES YES YES

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

emmmm.... I misunderstand the problem,sorry