vaaven's blog

By vaaven, 20 months ago, translation, In English

1802A - Likes

Idea: Aleks5d, Preparation: vaaven

Solution
Code

1802B - Settlement of Guinea Pigs

Idea and preparation: Aleks5d

Solution
Code

1801A - The Very Beautiful Blanket

Idea and preparation: 4qqqq

Solution
Code

1801B - Buying gifts

Idea: Tikhon228, Preparation: DishonoredRighteous

Solution
Code

1801C - Music Festival

Idea: vaaven, Preparation: ViktorSM

Solution
Code

1801D - The way home

Idea: Tikhon228, Preparation: Ormlis

Solution
Code

1801E - Gasoline prices

Idea and preparation: Kirill22

Solution
Code

1801F - Another n-dimensional chocolate bar

Idea and preparation: Tikhon228

Solution
Code

1801G - A task for substrings

Idea and preparation: grphil

Solution
Code
  • Vote: I like it
  • +125
  • Vote: I do not like it

| Write comment?
»
20 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Testcases aside, I thought this was generally a really cool round (or at least all the problems I tried).

»
20 months ago, # |
  Vote: I like it +14 Vote: I do not like it

What does SNM mean in tutorial of d1E?

»
20 months ago, # |
  Vote: I like it +8 Vote: I do not like it

It can be shown that it is optimal to minimize the number of shows first, and then maximize the amount of money.

Can anyone share a proof of this statement? it seems intuitive but i failed to prove it:c

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If there are fewer shows, they can do another show to get more money

  • »
    »
    20 months ago, # ^ |
    Rev. 7   Vote: I like it +13 Vote: I do not like it

    It can be seen that for all paths with end vertex $$$v$$$ and best vertex $$$t$$$, the number of shows is $$$0$$$ and/or the amount of money $$$< w_t$$$. So comparing any two possible paths with the same $$$v, t$$$, you can always do more shows on the path with fewer shows to get at least $$$w_t$$$ rubles, which would be more money than the other path.

»
20 months ago, # |
  Vote: I like it +40 Vote: I do not like it

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

This round is a little difficult, but the tasks are really interesting. I love div 2C.

»
20 months ago, # |
  Vote: I like it +26 Vote: I do not like it

div1E smart solution is great!

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I solve solve Div1 B with ternary search? If so, why my solution 197805657 did'nt work for this? Can someone help me?

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

alternate construction for beautiful blanket: for each row, simply use consecutive integers. denote the smallest power of 2 greater than m as 2^j. then let the first element in each row i be i*2^j, and the rest of the elements be simply the consecutive integers after i*2^j. this construction satisfies the conditions in the problem. examples:

n=4, m=4
0 1 2 3
8 9 10 11
16 17 18 19
24 25 26 27
n=5, m=7
0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks ! Your solution is easier to prove its accuracy.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one say whats wrong with this solution for div2.c

0 1 4 5 8
2 3 6 7 10
12 13 16 17 20
14 15 18 19 22
24 25 28 29 32
»
20 months ago, # |
  Vote: I like it -8 Vote: I do not like it

为什么没有中文版?

Why is there no Chinese version?

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm sure this is inadvertant, but in problem 1801A, after submitting any wrong solution, the pattern is literally visible in jury's answer xD.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain solution to Div 1. C? I can't understand what the editorial says.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is how I solved the problem. It's a bit long but I tried to make it as comprehensive as possible -

    the first thing we notice is no matter which track we start from in a particular song, the ending track will always remain the same and this position is the last track in the song such that it is strictly greater than all tracks before it. Let's denote this track's value as $$$X[i]$$$.

    We notice that if we place a song $$$j$$$ with larger $$$X[j]$$$ before a song $$$i$$$ all tracks in song $$$i$$$ become redundant since you can't continue any of them.

    So it's best if we sort the songs by the value of $$$X[i]$$$ in non decreasing order. But the issue is when we reach a case like -

    $$$n$$$ = 3

    first song — 1 2 3

    second song — 5

    third song — 4 5 6

    here we could place the third song after the first song to get a higher value.

    From now on we shall consider all songs as sorted by $$$X[i]$$$. So we do dp, where $$$dp[i]$$$ stores the max coolness in the prefix of length $$$i$$$.

    We also notice that the values of $$$dp[i]$$$ are non decreasing since we can always just continue off of the values of $$$dp[i-1]$$$.

    Now, let us denote $$$val[i][j]$$$ as the max that we can extend the $$$jth$$$ track in song i, for example the following song would have values —

    song = 4 1 3 6 2 8

    $$$val[i]$$$ = 3 -1 -1 2 -1 1

    I denote -1 for some $$$val[i][j]$$$ because they are not the max value in the prefix and they never add to the coolness.

    To compute $$$dp[i]$$$, we go through all tracks of song $$$i$$$ and binary search to find the first $$$X[k]$$$ that is strictly less than $$$a[i][j]$$$ (where $$$a[i][j]$$$ denotes the value of track $$$j$$$ in song $$$i$$$) and $$$val[i][j] \neq -1$$$, then we choose the max value of $$$dp[k]+val[i][j]$$$ over all valid tracks $$$j$$$.

    The final answer is $$$dp[n]$$$. Here is my submission

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you bro, great explanation!

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did pretty much the same thing that you did. I am somehow getting the wrong answer. Here is my submission link submission. I am having a hard time debugging. Could you please help

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the correctness issue with using Dijkstra's directly using the same cost function as the editorial mentions, and using the shortest path found to n-1, rather than maintaining the dp state for NxN [v][best] pairs?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It might be optimal to 'stop by' a different node for higher money from performances, before continuing on to the end.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The solution for 1801A can be simpler: just let M(i,j)=i*256+j.

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I appreciate the fast editorial, however it has been quite a while and the solution for B has not been posted yet. Aleks5d please post the solution! It would help newbies like me out :)

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let U be a guinea pig whose gender is not yet known.

    If $$$x=1$$$, let $$$U:=U+1$$$.

    If $$$x=2$$$, let $$$K$$$ be the number of guinea pigs whose gender is known.

    In the state of $$$U$$$, it must always be in a cage. For $$$K$$$, $$$⌈K/2⌉$$$ cages are needed.

    This is because in the worst case, the gender must be determined in order male, female, male, etc., and eventually $$$⌈K/2⌉$$$ cages are needed.

    However, since cages are not lost once they are bought, the maximum value of the answer is updated as follows.

    ans = max(ans, k + ceil(t/2))

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

C,

Actually, We can always make all part as zero with this.

int Y, X; cin >> Y >> X; cout << Y * X << endl;
for (int y = 0; y < Y; y++) for (int x = 0; x < X; x++)
    cout << y * (1ll << 32) + x << (x == X - 1 ? "\n" : " ");
»
15 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Div-1 E doesn't really require HLD, we can simply use two fenwick trees to find hash of a path in $$$O(\log{n})$$$ similarly to how we query path sum in trees.

Each path $$$u \rightarrow v$$$ can be divided into two subpaths $$$u \rightarrow lca(u, v)$$$ and $$$lca(u, v) \rightarrow v$$$.

We can now build two fenwick trees upon euler tour of the tree, one to find the hash of upward vertical path $$$u \rightarrow lca(u, v)$$$ and one to find the hash of downward vertical path $$$lca(u, v) \rightarrow v$$$.

  • The first fenwick will store value $$$(-par_u.P^{H - depth_u})$$$ at $$$EntryTime_u$$$ and $$$(+par_u.P^{H - depth_u})$$$ at $$$ExitTime_u$$$.
  • The second fenwick stores value $$$(+par_u.P^{depth_u})$$$ at $$$EntryTime_u$$$ and $$$(-par_u.P^{depth_u})$$$ at $$$ExitTime_u$$$.

($$$par_u$$$ is the parent of $$$u$$$ in dsu, $$$H$$$ is height of the tree, and $$$P$$$ is the number we chose for exponents in hash)

To find hash of upward vertical path $$$a \rightarrow b$$$, simply query range $$$[ExitTime_a, ExitTime_b]$$$ in the first fenwick tree. To find hash of downward vertical path $$$a \rightarrow b$$$, simply query range $$$[EntryTime_a, EntryTime_b]$$$ in the second fenwick. (Exponents can ofc be easily adjusted in $$$O(1)$$$ with $$$O(n\log{MOD})$$$ precomputation.)

Implementation: link

»
13 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Can someone please explain Problem C- Music Festival solution? I did not understand the tutorial at all. vaaven

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how does one get the logic of div2a (beautiful blanket) during contest?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div 1D. Can we use the topological sort instead of dijkstra?

270590828 — My wa6 solution.

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

Div 1D, Can someone please help me with my submission? I have tried debugging for a few hours but I can't get it.

I suspect it is something to do with priority_queue ordering, WA6. Thanks.

Edit: solved