### awoo's blog

By awoo, history, 19 months ago, translation,

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)

• +88

 » 19 months ago, # |   0 Can someone guide me through PROBLEM D.Im not getting the same result as the test case.Can someone simplify the tutorial.
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 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).
•  » » » 16 months ago, # ^ |   0 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.
 » 19 months ago, # |   0 Query Contest
 » 19 months ago, # |   +8 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!
 » 19 months ago, # |   0 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.
•  » » 19 months ago, # ^ |   +1 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.
•  » » 19 months ago, # ^ |   +1 Try values in the prefix and have a count function to calculate the number of different suffixed having some property. Something like: code#include using namespace std; int cnt(vectora, int n) { //How many ways to finish up a? //Should return 0 if we have already failed return 1; } int main() { ios_base::sync_with_stdio(false); int n, k; cin >> n >> k; vectora; assert(cnt(a) >= k); for (int i = 1; i <= n; i++) { for (int j = 0; j < n; j++) { a.push_back(j); int k1 = cnt(a, n); if (k - k1 > 0) { k -= k1; } else { break; } a.pop_back(); } assert(a.size() == i); } }
•  » » » 19 months ago, # ^ | ← Rev. 3 →   +11 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.
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 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.
 » 19 months ago, # | ← Rev. 2 →   +134 "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 becomesThe 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 inThe 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 proofWe know that there must exist at least $2$ odd length paths that start and end in $k + 2$ since the solution for $k + 2$ contains two more intervals than $k$. Flipping any one of them will cause the optimal $k$ solution to be increased by some $c \ge 0$, from $g(k)$ to $g(k) + c$, and the optimal $k + 2$ solution to be decreased by $c$, from $g(k + 2)$ to $g(k + 2) - c$. So after the flip we have two $k + 1$ solutions, and by the pigeon hole principle one solution covers $\ge \frac{g(k) + g(k + 2)}{2}$ ones and the other covers $\le \frac{g(k) + g(k + 2)}{2}$ ones.So conclusion from this is that $g(k + 1) \ge \frac{g(k) + g(k + 2)}{2}$, i.e. $g$ is concave.
•  » » 19 months ago, # ^ |   +29 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.
 » 19 months ago, # |   +3 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.
 » 19 months ago, # |   0 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.
•  » » 19 months ago, # ^ |   +10 Its a python solution, not a C++ solution.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 Got the solution's idea. Thanks
 » 19 months ago, # |   0 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
•  » » 19 months ago, # ^ |   0 No, you can't. It is given that two same lights can't be adjacent.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 They can be adjacent if they are in the end of the garland
•  » » » 19 months ago, # ^ |   0 Note that it's ok to have lamps of the same color on the ends of the garland.It's written in one of the paragraph
•  » » » » 19 months ago, # ^ |   0 u have understood it wrong, lamps of same colour can be adjacent mean, at end means , a point where the garland makes the full loop.
•  » » » » » 19 months ago, # ^ |   0 Thanks for this
 » 19 months ago, # | ← Rev. 2 →   0 In problem C its not clear to me for case.7 22 1 7 3 4 5 63 1how is output 8. I am having doubts can someone please clarify. Thanks
•  » » 19 months ago, # ^ |   0 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;
•  » » » 19 months ago, # ^ |   0 Thanks
 » 19 months ago, # |   0 Can someone please explain what is the use of the pos array in 1279C?
 » 19 months ago, # |   0 In 1279D, problem D, there is error in formulas. It should be $1 / (n k_{x})$ and $cnt_{y} / n$.
•  » » 19 months ago, # ^ |   0 thanks, now i can understand that.
 » 19 months ago, # |   0 why my approach is wrong? https://codeforces.com/contest/1279/submission/68775026
 » 19 months ago, # |   0 in c why we initialise res=m? why can't we add res+=1 in the else statement when pos[b[i]] < last ??
 » 19 months ago, # |   0 I can't understand what (this choice is independent of choosing x and y) means in D problem, my solution works as follow: Find the number of possible triples(x,y,z). Find the number of valid triples(x,y,z). Calculate the probability like that => prob = valid/possible But that don't give me the correct answer. Can anyone help me?
•  » » 18 months ago, # ^ |   +1 have the same problem :(
•  » » » 18 months ago, # ^ |   0 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.
 » 18 months ago, # |   0 can someone point out what is the error in this code for problem c https://codeforces.com/contest/1279/submission/69722050
 » 18 months ago, # | ← Rev. 3 →   0 In problem C, shouldn't we have res = 2 * (pos[b[i]] - i) than res += 2 * (pos[b[i]] - i) because we only need to calculate 2*K+1 seconds for last found present, than other could be simple taken in (no. of presents-1) seconds. Here's my code : #include using namespace std; int main(){ int t;cin>>t;while(t--){ int n,m;cin>>n>>m; vector a(n), b(m); unordered_set mp; for(int i=0;i>a[i]; for(int j=0;j>b[j]; mp.insert(b[j]);}; int i=0, j=0, time=0; for(;i
 » 13 months ago, # |   +8 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 ---22 2 11 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 wantsz = the chosen gift y is given to kid z .Now I am wondering what are 2 other possibilities ?Can anybody help me ??
•  » » 13 months ago, # ^ |   +3 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.
•  » » » 13 months ago, # ^ |   0 Ouch !I feel so dumb now . How can I miss that for each kid the sum of probability distribution will be $1/n$ .
 » 11 months ago, # | ← Rev. 2 →   +16 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}}$?
•  » » 11 months ago, # ^ |   0 You missed the previous paragraph where we claim that $res(\lambda_{opt},k)=res(\lambda_{opt},c_{\lambda_{opt}})$.