mnbvmar's blog

By mnbvmar, 5 years ago, In English

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
  • Vote: I like it
  • +258
  • Vote: I do not like it

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

Pretest for B were weak :(

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

Thank you for a lightning fast editorial.

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

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

Please, add author solution too :(

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

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

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

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

    I'm trying to figure out this myself :/

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

    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$$$).

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

    UPD: Deleted, sorry

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

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.

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

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

    Fixed! shame on me

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

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?

»
5 years ago, # |
  Vote: I like it +97 Vote: I do not like it
Challenge to D about 2^o(n) solution
»
5 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

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

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

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

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

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

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

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

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

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

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?

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

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?

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

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

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

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.

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

    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.

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

The solution to div1 D is really beautiful

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

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.

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

    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.

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

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.

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

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

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

    Surreal Number? That's so difficult. :( Bad memory to me, I know little about it until now.

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

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

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

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

emmmm.... I misunderstand the problem,sorry