When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

awoo's blog

By awoo, history, 4 years ago, translation, In English

1279A - New Year Garland

Idea: BledDest

Tutorial
Solution (Roms)

1279B - Verse For Santa

Idea: Roms

Tutorial
Solution (Roms)

1279C - Stack of Presents

Idea: Roms

Tutorial
Solution (Roms)

1279D - Santa's Bot

Idea: BledDest

Tutorial
Solution (Ne0n25)

1279E - New Year Permutations

Idea: Neon

Tutorial
Solution (Ne0n25)

1279F - New Year and Handle Change

Idea: vovuh

Tutorial
Solution (vovuh)
  • Vote: I like it
  • +88
  • Vote: I do not like it

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

Can someone guide me through PROBLEM D.Im not getting the same result as the test case.Can someone simplify the tutorial.

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

    Probability of choosing 1 kid in among n is 1/n. Let that kid is "x".

    Probability of choosing 1 item from the list of the chosen kid(x) is 1/k. Let that item is "y".

    So probability of choosing a pair (x, y) is 1/n AND 1/k.

    Now lets choose 1 kid from n kids again. And probability of choosing this kid is 1/n (it is not 1/(n-1) because it is independent form the previous choice. Let this kid is "z".

    As there are n kids and all the items of a kids list are different so we can say the probability of choosing a kid who want y item is frequency(y)/n.

    So probability of choosing a z kid who want y item is 1/n AND frequency(y)/n.

    Probability of finding a valid triple (x, y, z) is (1/n AND 1/k) AND (1/n AND frequency(y)/n).

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

      then what...?? do we have to sum all the probabilities of different students..?? sorry but i didn't get that. pls explain by the first test case. and i don't know why i am getting wrong answer for test case 1 but for case 2 answer is perfect.

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

Query Contest

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

In the solution to F, why is it necessary to include the $$$res$$$ variable in the binary search? It seems odd since the last value of $$$res$$$ would always be a $$$mid$$$ where $$$check(mid)$$$ returned more than the permitted operations. In which case the later $$$check(res)<=k$$$ would not trigger. However, replacing it with $$$hi + 1$$$ gives WA on 78.

Otherwise, thanks for a thorough explanation!

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

Can someone explain the "standard method of lexicographic recovery" of problem E more in detail? I never heard of a standard method for that before.

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

    Similar to the method to solve "restore the k-th permutation". I think you can google the solution to that. Just instead of choosing the next number to put we choose the entire block of numbers.

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

    Try values in the prefix and have a count function to calculate the number of different suffixed having some property. Something like:

    code
    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it +11 Vote: I do not like it

      Thanks. Now I think I have a better idea of the algorithm. It would be something like this:

      First we need to figure out the size of the first block. We try sizes 1, 2, 3, ..., N in that order (because of lexicographic order). We keep a running count of how many permutations we have skipped (initially 0). The number of permutations where the first block has size x is $$$(x-2)! \times DP(x+1)$$$. So we keep skipping block sizes until we find the block size x where the k-th permutation lives. So let's call $$$k' = k - skipped$$$. This means we want the k'-th permutation among all permutations where the first block has size x.

      So now we know the first block has size x, but we still don't know the exact permutation of numbers from 1 to x of the first block. To find it, we need to remember that there are (x-2)! good permutations for the first block, and that for each one we can fill the remaining numbers to the right in DP(x+1) ways. This means we need to find the r-th permutation of the first block, where r = k'/DP(x+1). So how do we find the r-th good permutation of a block of size x? Here the idea would be doing something like lexicographic recovery: first in a block of size x, we know the first number is x. So we need to fill the second, third, ..., and x-th numbers of the block. For the second number we can try 1, 3, 4, ..., x-1 (x is already used and 2 would create a self-loop). So this is the part I haven't figured out yet (and I would appreciate some help):

      1) How do we check that the prefix of numbers we have placed so far in the block is valid? I guess the naive way of following pointers and making sure there are no closed cycles should be enough (if we close a cycle prematurely then it's wrong).

      2) This part I don't have any clue yet: How do we count the number of ways we can fill the remaining numbers to the right (the suffix of the block we haven't filled yet) such that the full permutation is good? We have to count making sure we don't accidentally count permutations that would create invalid cycles in combination with the prefix we have placed so far. No clue how to do that.

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

        if you have prefix of length $$$X$$$ and set first $$$Y$$$ numbers correctly(no cycle there), the rest can be set in $$$(X - Y - 1)!$$$ ways. You can see it in code as well, where $$$cycl[lft]$$$ is used. You can think about it like this, you have to put $$$X-Y$$$ numbers in rest of the places. It's obvious that no number can go to it's place like $$$p[a] = a$$$ as it will create a cycle of length one. Now putting some number in some place, let's say $$$p[2]=6$$$ creates a constraint $$$p[6]\neq2$$$, but there already was a constraint $$$p[6]\neq6$$$ so for one place there is still one constraint about numbers that are left. So if you know that block has size $$$6$$$ it should start with $$$6$$$ and number of ways is $$$4!$$$. When you move to next position, you basically have same problem, you "know" (by iterating) the first number and size is one less.

»
4 years ago, # |
Rev. 2   Vote: I like it +134 Vote: I do not like it
"P. S.: We don't have the strict proof that the ans(c) is convex, but we have faith and stress. We'd appreciate it if someone would share the proof in the comment section."

After discussing the problem with my brother we have come up with a proof of ans(c) being convex. The way I think of the problem is that you are given a list of numbers containing $$$0$$$s and $$$1$$$s, and then let $$$g(k)$$$ be the maximum number of $$$1$$$s you can cover with $$$k$$$ intervals of length $$$L$$$. In this formulation the goal will be to prove that $$$g(k)$$$ is concave.

Take an optimal $$$k$$$ interval solution and an optimal $$$k + 2$$$ interval solution. Then make a bipartite graph out of the intervals, where edges are drawn between intervals that intersect. Here is an example for $$$k=7$$$ (the black bars symbolizes the intervals of the two solutions)

The bipartite graph then becomes

Bipartite graph

The reason for picking $$$k$$$ and $$$k + 2$$$ is because I want to create a $$$k + 1$$$ configuration from this that is at least as good as the mean of $$$g(k)$$$ and $$$g(k + 2)$$$. The method I apply is based on analysis of alternating paths in the bipartite graph, in particular what happens if you "flip" a path (meaning you exchange intervals between the two solutions). For example flipping the 3rd path from the left will result in

The 3rd path from the left has been flipped

The following is a proof of the existence of a $$$k + 1$$$ interval solution that contains at least as many $$$1$$$s as the mean of the optimal $$$k$$$ solution and the optimal $$$k + 2$$$ solution.

Formal proof

So conclusion from this is that $$$g(k + 1) \ge \frac{g(k) + g(k + 2)}{2}$$$, i.e. $$$g$$$ is concave.

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

    Awesome! This kind of proof resembles the proof of convexity for Monge dynamic programming. This also has an additional nice property of being constructive.

    For the proofs using less brain, it seems the problem can be reduced into negative cycle canceling. Construct an edge $$$i \rightarrow i + 1$$$ with cost 0, and $$$j \le i$$$ with cost $$$-sum[i, j)$$$ for $$$i < j \le i + L$$$. Since negative cycle canceling is dual to the augmenting path, it should have the same convex property.

    In the contest, I thought the problem had an MCMF modeling. But after the contest, what I had in mind turned out to be wrong, and this is the best I could get afterwards.

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

Just curious as to why is it that some problem names in the tutorial appear in Russian (like problem F), while others are in English? I have seen this in many previous editorials as well.

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

For the solution of Verse for Santa, alot of macros are used. Its not that clear to me as i am not that fluent in c++ and macros are not defined in solution. Can someone please give reference to their full solution link. It will help me thanks. If its java then better.

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

    Its a python solution, not a C++ solution.

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

In the first question "New Year garland" For the second test case where 1 red, 2 green and 10 blue bulbs are given. we can arrange them as GRBGBBBBBBBBB But according to the question it should print NO

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

    No, you can't. It is given that two same lights can't be adjacent.

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

In problem C its not clear to me for case.

7 2

2 1 7 3 4 5 6

3 1

how is output 8. I am having doubts can someone please clarify. Thanks

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

    First in array A {2 1 7 3 4 5 6},we need to remove first 4 element to grab 3 and putting back the removed elements in order of ({1,2,7} or {1,7,2}) and your array A become {1,2,7,4,5,6}; the total opearations you did before was 7{removing 4 elements + putting back 3 elements} and now you just need 1 more operation to remove 1 from A; so total no of operations = 7+1 = 8;

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

In 1279D, problem D, there is error in formulas. It should be $$$1 / (n k_{x})$$$ and $$$cnt_{y} / n$$$.

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

I can't understand what (this choice is independent of choosing x and y) means in D problem, my solution works as follow:

  1. Find the number of possible triples(x,y,z).
  2. Find the number of valid triples(x,y,z).
  3. Calculate the probability like that => prob = valid/possible

But that don't give me the correct answer. Can anyone help me?

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

    have the same problem :(

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

      try to search about dependent events in probability on Google, i found any help in that.

      that is a really good book about probability.

      after that, see that comment, he/her shows two errors at editorial.

      sorry for my bad english.

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

I was trying to figure out all possible triplets in Problem D . But I couldn't figure out all 8 possibilities .
Here is what I got ..
for the first case which is ---
2
2 2 1
1 1

(1 , 2 , 1) , (1 , 2 , 2)
(1 , 1 , 1) , (1 , 1 , 2)
(2 , 1 , 1) , (2 , 1 , 2)

Where (x , y , z) is ...
x = kid number .
y = one of the gifts kid x wants
z = the chosen gift y is given to kid z .
Now I am wondering what are 2 other possibilities ?
Can anybody help me ??

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

    You are right, there are 6 possibilities. But they do not have the same probability.

    After first selection, both x = 1 and x = 2 have probability of 1/2. If he selected x = 2, then we have only 1 selection for y, so selection (x = 2, y = 1) also has probability of 1/2. Finally, each of (2, 1, 1) and (2, 1, 2) would be 1/4.

    In case of x = 1, both y and z have two options, so probability for each of (1, 2, 1), (1, 2, 2), (1, 1, 1), (1, 1, 2) is 1/8.

    Then, since the only incorrect choice is (1, 2, 2), whose probability is 1/8, the answer will be 7/8.

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

      Ouch !
      I feel so dumb now . How can I miss that for each kid the sum of probability distribution will be $$$1/n$$$ .

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

In problem F, the claim is $$$ dp[n][k] = res(\lambda_{opt},c_{\lambda_{opt}}) - \lambda_{opt}k $$$.

Why is the last value $$$k$$$ instead of $$$ c_{\lambda_{opt}} $$$?

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

    You missed the previous paragraph where we claim that $$$res(\lambda_{opt},k)=res(\lambda_{opt},c_{\lambda_{opt}})$$$.