### tourist's blog

By tourist, 2 weeks ago, Hope you enjoyed the round! Editorials for all problems are out now. Also check out ecnerwala's stream where we went through individual problems and discussed the contest as a whole: https://www.youtube.com/watch?v=5Q4tGWT7p7I.  Tutorial of VK Cup 2021 - Elimination (Engine) Comments (121)
 » 2 weeks ago, # | ← Rev. 3 →   The solution to Problem C : (driven by observations and stuff) quite similar to the editorial :122867887the variables stagesa stands for mine(in problem) and stagesb stands for Iliya's stages( can be thought as pointers) !Hope its helps !
•  » » hey , can u plz tell me why this approach fails as i m not able to figure it out since yesterday. thanks in advance.Link to soln
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   The answer is n_new - n_old which is the additional stages.Also I am not sure that s_b += b[s]; is correct!! why s is < n-1!EDIT: modified solution
•  » » » » shukraan bro... why is it getting so many downvotes, is there a community guideline that i voilated?? :(
•  » » » » » I don't know an official guides, but you better ask for the logic/proof not for debugging a code for you.
•  » » » » » » noted down sir
•  » » » » » » » Kindly remove the last word.
•  » » » » » » » » 7 days ago, # ^ | ← Rev. 2 →   string s = "noted down sir"; s = s.substr(0 , 10); cout<
 » 2 weeks ago, # | ← Rev. 3 →   There are some other approaches to problem D: Maintain a set of numbers from 1 to n. This set will contain the remaining elements which can be used. First, place all the first occurring numbers to their corresponding indexes and mark them visited. For example, if array A is : {6,6,6,1,1,1} , then after the first step our B array should look like this : {6,0,0,1,0,0} , i.e., we placed the first occurring 2 and 1 at the same index for now. Since we placed 2 and 1 so remove it from the set. Set will contain {2,3,4,5} Now traverse from left to right, when a particular index is not visited, then we have to place some value at that index. I will take out the first element from set (you can take out any remaining element, doesn't matter) and let that be val. Now if val != index then we can simply put that value at the current index and move forward. If val == index, then first look up the position of a[cur_id] and then place val at pos[a[cur_id]] and a[cur_id] will contain the correct or initial value. In the given example, we will go to 2nd index (as its not visited), take out first element from set which is 2 ... index==2 so check for the expected value at index 2 which is 6 and we have placed 6 at index 1. So, swap these , i.e, place 2 at index 1 and 6 at index 2. Now move forward, index 3 is not visited. Take out first element from set which is 3 ... Expected value 6 .. position of 6 : 2nd index , so place 3 at 2nd index and 6 at index 3. Now we will go to index 5, Take out first element which is 4 . Index != 5 so place 5 at that index and move right. Hope it helps My AC Code : https://codeforces.com/contest/1530/submission/122867049
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   I could not get AC during the contest as I was storing the positions of elements in a boolean vector :XD. I could not find this small bug :(
•  » » I knew this and couldn't implement :( Can you tell me why it's working?Like in this approach why there won't be a case s.t. for last remaining element index==val ?
•  » » » I'll try to explain why it works. Let's consider two cases. Case 1 is when n is 1 and so no assignment is possible. Now n > 1. Let's say that in the end, you have an index for which b[i] = i. Now, observe that a[i] will always be different than i (Given in question that we cannot gift ourself). So, if b[i] is i and a[i] is not i then it means that a[i] != b[i]. Now, a[i] != b[i]. Notice that a[i] has been placed already in the result (why? Because if a[i] was present only once, we would have picked it in earlier loop greedily.) So, we just bring a[i] here at this pos and send this value to where a[i] was chosen for. It will become clear from the example. Now, let's take the second test case (1-based indexing). Index 1 2 3 4 5 6 7 a = 6 4 6 2 4 5 6 res = 6 4 0 2 0 5 0 // Filling only if we encounter first time pos = 0 4 0 2 6 1 0 // pos[i] denotes index where we placed i Now, keep one pointer at first 0 from start of pos and iterate on res. If res[i] = 0, place the pointer value there and increment pointer till we are at another 0. So, pointer is at 1 (in pos array). Let's iterate over res. index = 1, res != 0, so move forward index = 2, res != 0, so move forward index = 3, res == 0, so assign res as 1 (pointer points to 1) and move pointer along until we encounter another 0. So, now pointer points to 3. index = 4, res != 0, so move forward index = 5, res == 0, so assign res as 3 and move pointer to 7. index = 6, res != 0, so continue. index = 7, res == 0, so assign res as 7. But, the last one won't fit well.Since, res = 7 is not allowed. So, see what was at index 7 in original array. a was 6. So, make res as 6 and wherever 6 was placed, place 7 there. I hope this is clear. If not, let me know.
•  » » thanks for your approach it helped me.
 » Interesting problems, especially E.Thanks for contest!
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   can u pls explain the solution for E...pls
•  » » » I think that Editorial of E is pretty good, but I'll try to retell it with more explanations.In this problem, you do not need to know various complex algorithms, just analyze the problem statement and try to figure something out.So, first of all, we need to consider two simple but important cases (same as Editorial). When all characters are the same, it is senselessly to shuffle them, because $f(t)$ will always be equal to $|s| - 1$ (here and further $t$ is our final string). Let's try to figure out when $f(t) = 0$. We can achieve it only when $t$ is unique. That's why let's find the lexicographically smallest character, which is unique in $s$, and put it on the first position of $t$. Then, we can complete $t$ with other characters of $s$ in lexicographic order. So $f(t) = 0$ and the string is lexicographically minimal. I hope previous part was simple for understanding, because now we will consider more interesting cases. But it is still a retelling of Editorial.We considered cases, when $f(t) = 0$ and $f(t) = |s| - 1$. Now I claim that $f(t)$ for other cases is equal $1$. Maybe it's hard to believe, but it's true. Let's try build $t$.Let's find the smallest character and call it $a$ (It may not be equal to 'a' like character, just convenient). $a$ will be first character of $t$. We need $f(t) = 1$ and lexicographically minimal $t$ so $a$ is the best option. Then we need to choose second character of $t$. And here some interesting cases: Lets consider if second character is also $a$. Now $t = aa + something$. And we can't have in "something" $aa$, because then $f(t) >= 2$. That's why we need to place $a$ through one: aa?a?a?a?a?a????? (here ? is some characters, which are not equal to $a$). It is easy to understand that in this case we need at least $cnt[a] - 2$ other characters ($cnt[a]$ is the number of $a$ in $s$). If we have it, everything is great, and the answer is lexicographically minimal. But else we can't have $t = aa + something$. Now, when $aa$ beginning is impossible, let's find other lexicographically smallest character and call it $b$ ($t = ab + something$). As in the previous paragraph we can't heve ab in "something". And here 2 cases (it's almost over, I promise).2.1. If we don't have any characters except $a$ and $b$, the only possible answer is t = abbbbbbaaa, because else we will have ab in "something": t = abaaaaaABbbbbb.2.2. If we have other character, everything is perfect because we can do this: t = abaaaaa?bbbbbbb??????. We just separated ab and $f(t) = 1$. But or course, ? shound be lexicographically sorted. I hope it was useful for you. I really tried my best.Here is my C++ solution with comments: 122932141
•  » » » » thanks man, got it.the thing is as i read question in contest, i start a mathematical approach and don't try many cases, which makes a easier prob hard for me. If u have any thing to guide then pls share. :)thanks once again :}
•  » » I am sorry but what exactly was interesting in problem E ?
•  » » » He found interesting the fact that this kinda C problem was so overrated and placed on Eth position) IMHO D was much better and maybe harder than just a case recognition like in Eth one.
•  » » » » kinda C problem I am probably sure algo-police is on the way after you saying that :/
•  » » » » So you solved the better and harder D but seem yet to recognize all cases in E, huh?
•  » » » » » Better means more interesting. And yes you're right lol)))) I didn't manage to solve E but not due to the the case recognition but because of a stupid mistake that I made in one of the cases. And yes, in my opinion "if else" in E is less interesting than a plain dfs like in D. But ok, the whole this discussion is strange so, idk)))
•  » » the f function is how form the every value(f....f[n])
•  » » » sorry，i got the prefix function！！
 » 2 weeks ago, # | ← Rev. 6 →   Another Solution for D : First, Place all the values of b[i]=a[i] where a[i] is chosen to given gift by only one member Then, Those who are desired by more than one person give them any random person as it wont matter (Explained later).Then, maintain of set of variables who have not yet received any gift from any person and start from index 0 and the person who hasn't chosen yet ,give him a gift not equal to itself i.e either beginning element of set and ending element of set. Now comes the main part u should notice that there can be atmost one value equal to itself and and the person whom this index wished to give a gift must have atleast 2 person desiring him so simply just find another index with same value of a[i] and just swap the two and you will acheive the desirable state.Solution Link
•  » » It helps me a lot, thank you =))
•  » » The same way as you, it's a good idea.
 » kuhn algorithm work for D in 250 ms.it is believed that asymptotics for kuhn is O(NM) howewer in practice it is quite close to liniar.
 » 2 weeks ago, # | ← Rev. 2 →   As I see in other contestants' code, most popular solution for F is some kind of DP. I have just passed straightforward O($2^n \cdot n^2$) solution (brute force + OR-convolution).Even with whole bunch of pragmas it 122869425 barely fits in TL :). Was it intended to catch TLE, or my implementation is bad?UPD: I optimized brute-force part 122870796 , now it fits well, but I'm still interested if it was intended to pass or not.
•  » » The intended complexity is $O(2^n \cdot n)$ with inclusion-exclusion. Distinguishing it from $O(2^n \cdot n^2)$ is quite hard though. The time limit was set with the intention to allow any $O(2^n \cdot n)$ solution and cut off most $O(2^n \cdot n^2)$ solutions.
•  » » » What was the reason for the strange modulo?
•  » » » » I think the modulo was chosen so you can do everything in int, which might make certain solutions run faster considering how much modulo multiplication is involved.
•  » » » » » That's what I thought — but I resubmitted my solution with long long, and it actually ran slightly faster!Maybe C++ is smart enough to somehow know the numbers are small and use the faster int operations regardless?
•  » » » » » » Another thing that a smaller modulo let's you use is the Barret Reduction to replace division operations in modulos with multiplication. 64 bit C++ automatically does modulo operations with multiplications (if modulo is constant) but this is helpful for languages such as Java.
•  » » » » With modulo around $10^9$, submitting under 64-bit C++ compiler could give a 3-4x speed boost, and separating a 32-bit-compiled $O(2^n \cdot n)$ from a 64-bit-compiled $O(2^n \cdot n^2)$ was pretty much impossible.
 » For problem D, I was really glad to find a solution without using Graphs (since I am bad at Graph Theory). Hint: Try to satisfy as many wishes as you could (which is the number of different integers from the input). Then, we will have some people who do not have somebody to give a gift to. We can give them anybody who is not given yet. However, we should check if there is somebody who is matched with himself. It can be proven that in that case the optimal strategy is to satisfy the first "wish" of that person. Not really sure if you could fully understand me, tho. 122840888
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   For persons getting matched to themselves I just exchanged their value to the person having the value that person wanted. I really can't see how its a graph problem.
 » Great Contest, thanks tourist. Highly appreciated
 » my solution to D. It is a greedy approach and doesn't use graph. Hope it helps. 122817534 SummaryFirst we give everyone there wish if it is not given to anyone else yet. Then we assign left out people the remaining people. Now, we iterate and check for if the person is assigned to himself, if so, we give them there wish and assign them to the person who had their wish. It always works because, wishes granted were max earlier and after swapping also if one person loses their wish then some other person gets their wish.
•  » » Also can anybody link the problem variation where a person can have more than 1 wishes. I left it last time when I didn't know graphs. It would be a great help as I can't find it.
•  » » swap(ans[b[a[i]]],ans[i]); explain this clearly
•  » » » here, see this solution, it's the same method as the guy, but I have added comments, which should hopefully help
 » 2 weeks ago, # | ← Rev. 2 →   Can somebody please explain to me why this code gets accepted, but during the contest I got on the same code WA? There is only one very small difference between those 2, the AC one has a forgotten cerr into it, you can check with a diff tool :)
 » 2 weeks ago, # | ← Rev. 2 →   Problem E really required careful case analysis. My solution got wrong answer on pretest 6 just because of missing a single -1. qwqI think it is a nice problem to test participants' carefulness！
 » I really liked $D$. Construct directed graph $G$ with edge from $i$ to $j$ if $i$ wants to give a gift to $j$. Now store $2$ sets: $Unliked$ and $Popular$. A element $i$ is in $Unliked$ if $d_G^{-}(i) = 0$ and in $Popular$ if $d_G^{-}(i) > 1$. Now while $Unliked$ is non empty, take a Unliked person and a person who wants to give a gift to a Popular person and is not the same as the chosen Unliked person. Now just delete the edge from this person to the Popular person and add an edge from person to Unliked person. Remove this Unliked person from Unliked, and if the Popular person, is no longer Popular remove him from Popular set as well. An implementation is here: https://codeforces.com/contest/1530/submission/122822889
•  » » great solution, I did it with randomization 122882331, it was very easy but couldn't do it during the contest... I was scared to see fewer submissions.
•  » » » Thanks, I'm still not sure why being random passes will look into it in some time I guess.
•  » » Why are you adding an edge between the person and Unliked person?
•  » » » When we process elements of the Unliked set, we try to increase their indegree to $1$, by connecting them to people, whose connections are useless. Like the ones connected to Popular people. This is a greedy, straightforward solution that works. Hope you understand.
 » ecnerwala Can you please upload the video the stream on youtube? Quality 1080p lags a lot with many of ours internet.
•  » » Yes, will do tomorrow.Re 1080p: unfortunately, Twitch transcoding (quality conversion) is not guaranteed for Twitch affiliates, it's only priority, so whether there are lower quality options is out of my control. Hope it's available next time! I've heard it's prioritized by viewership, so it might be more likely since all of you showed up!
 » Very simple solution for D using only arrays and vector : 122836640
•  » » Can you explain what the last for loop does?
•  » » » Sure, I have a vector of people who were not selected by anyone. So I am just looping over existing elements to replace repeating elements with vector elements.
 » This example test cases of the problems were very strong.I about to submit with wrong logical solution for problem C and D. It got caught in the initial test case, thus no penalty, Whew.Then made the necessary changes and got accepted. Enjoyed the round throughout!
 » Did anyone else solve C using a treap?
 » I did an overkill for C. I used an ordered_multiset. Though I feel a bit stupid, I think the template I used is pretty amazing : 122832592.This would actually be useful in solving a more general problem: lets say instead of predicting in how many minimum moves we can win, the game continues with different scores being added to each and we need to find the move at which our score will be atleast the opponent's. In this case we would require (or atleast this is one way) order statistics on our multiset.
 » The promble E 1530E - 12 - Minimax, I got a wrong answer on test 2 with this checker log:wrong answer 48th words differ — expected: 'ff', found: 'ff'I don't know what is that means.122886321
•  » » can u pls explain E...pls
•  » » » sorry... I don't think I have words better than the editorial. And, I havn't pass yet. QAQ
•  » » » » no probs bro, i got the editorial now, cool
•  » » For the ff test case, you are printing an extra character with ASCII code 0 after ff. If you print t.size(), you will see that it is 3.
 » So I used the exact idea that the solution mentions, however I can't figure out (for literally hours) what is wrong with my code since everything I coded seems logical. Can anyone help me please, thanks in advance! IdeaAlternatively, notice that when we add 100 to our scores, it just adds 100 to our overall score except for the case when the total number of completed stages becomes divisible by 4, when we also need to subtract the score of the worst currently included stage from the sum. We can similarly handle adding 0 to Ilya's scores. If we sort all our and Ilya's scores at the beginning and maintain a pointer to the current worst included stage in both scoresheets, we can add a new 100/0 stage and recalculate the totals in O(1). Code#include using namespace std; void solve() { int n; cin >> n; vector a(n), b(n); for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 0; i < n; i++) cin >> b[i]; sort(a.rbegin(), a.rend()); sort(b.rbegin(), b.rend()); int k = n - (n / 4); int sa = 0, sb = 0; deque mxa, mnb; for(int i = 0; i < k; i++) { sa += a[i]; mxa.push_back(a[i]); sb += b[i]; } for(int i = k; i < n; i++) { mnb.push_back(b[i]); } if(sa >= sb) { cout << 0 << '\n'; return; } int curn = n; while(true) { curn++; if(curn % 4 != 0) { // only add new element sa += 100; if(!mnb.empty()) { sb += mnb.back(); mnb.pop_back(); } } else { // remove one smallest element if(!mxa.empty()) { sa -= mxa.back(); mxa.pop_back(); } else { sa -= 100; } sa += 100; } if(sa >= sb) break; } cout << curn - n << '\n'; } int main() { int t; cin >> t; while(t--) solve(); } 
 » Sad to see that simply changing long long into int can make a huge difference to not only the result but also my current rating, though my solution has a complexity of 2^nn^2 (actually it is 2^{n+2}n^2!).TLE : 122856541AC : 122887934btw how to type LaTeX in Codeforces?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   Put them into $$ symbol. For example, $2^{n+2} n^2$ will be $2^{n+2} n^2$ (only 1 is enough tho, the math engine rendered it 3 times somehow) •  » » » Thank you very much.Well actually I did so, but there might be something wrong with my operation just now so that when I previewed the comment the symbol $$ didn't work.Now it works. $\mathcal{O}(2^{n+2}n^2)$
 » 2 weeks ago, # | ← Rev. 5 →   In problem D, my code is of order O(n) but still it took 1918ms (phew!). Can someone tell me why?Algo v stores the input. flag is 1 for the positions which are requested and it also stores who requested them. left stores the positions not requested by anyone. v1 stores the output. flag1 stores which numbers are used in real time.If the requested number has not been used, then we use it. Else, we use the left array. If this number is equal to its position, we swap it with the position which has the number it requested.Code: 122834097PS: Sorry for such a trivial question. Just started learning STL.
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   You included But why include vector, algorithm,set etc? etc.?
•  » » » Eh, I also don't know. xD
•  » » Isn't the time complexity of vector erase is O(n)?
•  » » » I thought it was $O(1)$. Thanks!
 » Can Problem C be solved without binary search?
•  » » Yes, we can. First sort the array and calculate the initial sum. If (total rounds)/4 increases, then we can remove the first element we used to calculate the sum from your sum and add 100. Nothing changes for Illya. Else, we add 100 to your sum and 0 to Illya's sum.
 » My solution for problem D.First of all we store each element's frequency in an array .Then We traverse the array and each element that its frequency is 0 we store them in a deque (you will understand why deque in a bit).Next We traverse the array (doesn't matter from left to right or from right to left) and we look for some cases: If the frequency of whom person i wants to gift is 1 , then we give him it , OR there is only 1 number left in the deque , and it equals to i , then we give i a[i] . if the above cases are not satisfied , then we look to the deque. if the first element in the deque is equal to i , then We give him the last element , else we give him the first element .Finally the answer is the number of elements in the array (n) minus the number of elements from 1 to n that there frequency is 0 .CODE
 » 2 weeks ago, # | ← Rev. 5 →   A solution for problem C. Simple and Easy to understand, Hope it helps ! Submission Link — 122895932
•  » » 12 days ago, # ^ | ← Rev. 2 →   nice :)
 » tourist Can you provide your test case generator for C, in case they many of them in pretest 2 were not hand made?
 » Just did D a little different so I thought I'd comment how out here (in the loving memory of my multiple wrong submissions prior to the AC UwU)Do correct me if I'm wrong anywhere, and I apologize if it's a really inferior approach to be explaining and/or very poorly explained.Okay so what we do know is that the numbers appearing more than once in the array need to be replaced with the ones between $1$ to $n$ that are not appearing at all (since everyone must get a gift). It is given that no employee initially is assigned to themselves as secret santa, so the only self assignments that can potentially be caused would be because of us replacing repeated numbers with the absent ones. This self assignment can be easily avoided as shall be discussed in the approach:Intuition:Let the given array be called $a$. Firstly we make a list of numbers that are absent in $a$ (let's name it $se$) and also maintain an array to count the number of appearances of the integers $1$ to $n$ in $a$ (say $b$). Now we traverse $a$ starting from index $0$ (iterator of $se$ starting also from the first element of $se$) and each time the number we encounter in $a$ has more than $1$ appearances indicated by $b$ we replace it with a number from $se$ and update its count in $b$ decrementing it by $1$ and moving the iterator of $se$ to the next unused number in it. Carrying out the Replacement:Since as has been explained in the editorial, the maximum fulfilled wishes will always be the equal to the number of different integers in the given array, the order of replacement is not of any consequence as long as we are cautious (while replacing repeated numbers with those form $se$) about not assigning the employee as his own secret santa, i.e. the number we choose from $se$ for the replacement must not be equal to number of the employee.Among the numbers in $se$, there will at most only be one such number for each employee that could result in self assignment. Thus while iterating through $a$ (suppose we're at index $i$) and $se$ (suppose the iterator points to $j$-th element), if the number of appearances of $a_i$ are more than $1$ in $b$ we can encounter two possibilities: Employee number is equal to $j$-th element of $se$. Employee number is different than $j$-th element of $se$. In case of the second possibility, we can replace $a_i$ with the $j$-th element of $se$ and increment $j$, thus eliminating the possibility of assigning the same number initially absent in $a$ to more than one employees. In case of the first possibility however, we replace $a_i$ with $j+1$-th element of $se$, since $j$-th element remains unused, we swap the $j$-th and $j+1$-th elements of $se$ and increment $j$. This results in the next element we encounter through the iterator of $se$ being the originally $j$-th element hence prevented from being skipped.Code:122890172 (my very unclean submission I suppose.)Time Complexity:It would take this $O(n)$ to reach an answer as the maximum number of runs the inner while loop performs is 2, a constant. (I sure do hope I'm not wrong) All done, thanks!How do you conclude these comments anyways... Does this count as one?
•  » » Thanks for the explanation!!
 » Problem B simple explanation Putting Plates
 » For problem B , i just wrote all the condition in my code that are given in the question.In order to not get RE i took a 40*40 matrix and start the matrix at cell 5 * 5... here my solution — https://codeforces.com/contest/1530/submission/122886137
 » Problem A Simple Explanation Problem A
 » Short code for B (Perl) — 122869086
 » Can some tell me what is wrong with my code I am getting a WA on C. #include using namespace std; #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define ll long long #define ld long double #define precise(x) fixed<>t; #define pll pair #define vl vector #define vll vector< pll > #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ff first #define ss second #define pf push_front #define pq priority_queue int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1}; string yes = "YES"; string no = "NO"; ll mod = 1000000007; ll MAXN = 100001; void print(vector &a) { for(auto i:a) cout< &a) { ll n = a.size(); ll m = a.size(); for(ll i=0; i1) fac.pb(n); } void solve() { ll n; cin>>n; vl a(n,0), b(n,0); ll sa = 0, sb = 0; for(int i=0; i>a[i]; for(int i=0; i>b[i]; sort(rall(a)); sort(rall(b)); int k = n-n/4; for(int i=0; isb) { cout<<"0"<0) { sb += b[index]; index++; temp--; } ans++; } cout<>t; for(ll i=1; i<=t; i++) { solve(); } } else solve(); return 0; } 
•  » » 2 weeks ago, # ^ | ← Rev. 3 →   you only add something to sb but sometimes sb should be decreased.counterexample :170 0 100 100 100 100 100100 100 100 100 100 100 100
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   Please try to use spoiler tag before posting long codes. Like thisIt'sveryirritatingwhensuddenlythecodecoversthewholescreenandyouhavetoscrollsomuch!
•  » » » Even better, post a link to your submission, then we can see the failed tests.
•  » » The number of values dropped should be $\left\lfloor \frac{n+ans}{4}\right\rfloor$ not $\left\lfloor \frac{n}{4}\right\rfloor$To implement this you need to treat every fourth step differently. When (n + ans)%4 = 0you shouldn't add to sb, but should subtract the smallest remaining value from sa (after adding 100 to it).
 » For problem C, it's also possible to do a binary search on how many exams are needed. It's O(n) complexity to answer "Take X more exams, if I can have a no-lower score or not"
 » 2 weeks ago, # | ← Rev. 2 →   Can anyone please help with problem C, what's wrong with my solution submission ? I've tried many times, couldn't find the issue.
•  » » It looks as if you are taking too few values from Ilya's results (array b). You are, in effect adding 100s to array a and 0s to array b. Ilya wants to count his best results so as the total number of stages increases the number of non-zero entries counted in array b should increase, but in your code it is decreasing.
•  » » » Got the issue finally, did correction while calculating llya's score, now it got accepted. Thanks !!
 » Here is my solution to problem C using binary search on answer link P.S."also my first comment"
•  » » great work
 » My simple solution for D , without using any sort of graphs: First try to assign each person, his choice if that choice has not been assign yet, maintain a bool vector to store the gifts which have been assigned and index array to store indexes which have not been assigned any gifts yet. Now construct a set containing gifts which have not been assigned. Now iterate for each index, if that index has not been assigned gift,then,there are two cases (i) first element of set is not equal to current index ,then assign that gift and erase it from set. (ii) Its equal to current index , since atmost 1 gift can be equal to current index,then we will assign next gift to current index and erase it .Now if set contains only 1 element and its equal to current index ,then we will swap the gifts of current index and index which has been assigned the choice of the current index ,this will not affect the final answer
 » Actually we can brute force C: 122875589
 » tourist Any updates on the editorial for the problems F,G,H?
•  » » i'm sure that he is working hard to catch up with it. be patient please
 » I have different solution for D:First of all, lets construct bipartite graph with edges from i (left side) to a[i] (right side)It is clear, that answer is maximum matching in this graph + some extra edgesLets find maximum matching and fill $answer$ with itNow we have some people, who doesn't give and who doesn't recieve giftsLets assign them to each other and if we got collision that $i$ should give to $i$, then just swap that $i$ gives to $a[i]$ and someone who gives to $a[i]$ gives to $i$It works in $O(MaximumMatching) + O(n)$. My $O(nm)$ Khun implementation (based on this Burunduk1's article) works under 400ms: 122962186.
 » Please update editorial for problem F. Or can someone help me with it ?
•  » » 13 days ago, # ^ | ← Rev. 2 →   Try this: $F(S)=\sum_{T\subseteq S,T\neq \emptyset } (-1)^{|T|-1}G(T)$where $F(s)$ means the probability that there exists a element in $s$ satisfies the conditions,$G(s)$means the probability that all elements in $s$ satisfy the conditions . This also right for: $G(S)=\sum_{T\subseteq S,T\neq \emptyset } (-1)^{|T|-1}F(T)$
 » 1 day i will beat tourist...i will become ultra legendary grandmaster
•  » » Good Luck brother!!
•  » » 13 days ago, # ^ | ← Rev. 2 →   you can beat everyone. you just need to... Spoilerflip everyone's rating curve upside down.
 » 13 days ago, # | ← Rev. 2 →   Can anyone share priority queue approach and code for problem C, I am not able to figure out mistake in my code.
•  » » You can see my submission
 » Can anyone explain their DP solution for F ? The one which is $O(2^{n} n^{2})$
•  » » I think it is 1 — P(no line is ok):$dp_{i,mask}$ means ：consider the i-th row and the columns which have no failed cell is mask (mask also record whether the diagonal is ok).And do the "And convolution" is $O(2^nn)$ for one row .Totally in $O(2^nn^2)$
•  » » » Thnaks for your reply. Can you provide some resource on "and-convolution" ? Is this related to fft ?
•  » » » » You can search "Fast Walsh Hadamard Transform". I only have Chinese resource : oi-wiki.
•  » » After inspecting ecnerwala's solution I think he used this state:$dp[i][mask]$ = what is the probability that after having considered the first $i$ cells (using a snake index from left to right, top to bottom) the cols/diagonals that can still be winning are represented by $mask$, and we haven't won any of the rows so far.(but with space saving trick to reduce memory)
 » 13 days ago, # | ← Rev. 3 →   in C in sample test_case 3.... .... 20 30 40 50.... 100 100 100 100... consider this... 20 30 40 50 100 100... 100 100 100 100 0 0... in total extra 2 stages seem sufficent.....(6-6/4 = 5)...so by taking 5 best scores we can fullfill the criteria...but the answer is 3.....please tell me where Iam wrong...
•  » » k = n — floor(n/4) 1. for total count of numbers is 4, k = 3, so (40 + 30 + 20) = 90 < 300 2. when count is 5, k = 4, so(100 + 40 + 30 + 20) = 190 < 300 3. count is 6, k = 5 so ( 100 + 100 + 40 + 30 + 20 ) = 290 < 300 4. At last count is 7 which is 3 more than beginning count of numbers, k = 6 so ( 100 + 100 + 100 + 40 + 30 + 20) > 300 So we need 3 more rounds.
 » prefix function is how to form the f to f[n]
 » in codeforces i can learn many,thanking everyone!
 » In problem F, to optimize the solution to $O(2^n \cdot n)$ using the first way described, how to actually achieve that complexity? Wouldn't updating the products and rolling back (in $O(n)$) for each possible state of $f(i, S)$ calculated recursively (for which there are $(n + 2) * 2^{(n + 2)}$ states) take $O(2^n \cdot n^2)$ in total?
•  » » At level $i$, there are $2^{i-1}$ states, resulting in $2^0 + 2^1 + \ldots + 2^{n+2} = O(2^n)$ states in total.
 » in F why 1-f（1，{}） is equal to 1+f(n+3,S)? PLEASE