Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### tourist's blog

By tourist, 10 months 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.

• +349

 » 10 months ago, # | ← Rev. 3 →   -11 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 !
•  » » 10 months ago, # ^ |   -39 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
•  » » » 10 months ago, # ^ | ← Rev. 2 →   +10 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
•  » » » » 10 months ago, # ^ |   0 shukraan bro... why is it getting so many downvotes, is there a community guideline that i voilated?? :(
•  » » » » » 10 months ago, # ^ |   0 I don't know an official guides, but you better ask for the logic/proof not for debugging a code for you.
•  » » » » » » 10 months ago, # ^ |   0 noted down sir
•  » » » » » » » 10 months ago, # ^ |   0 Kindly remove the last word.
•  » » » » » » » » 10 months ago, # ^ | ← Rev. 2 →   0 string s = "noted down sir"; s = s.substr(0 , 10); cout<
•  » » 10 months ago, # ^ |   +8 Can I ask why so many downvotes?
 » 10 months ago, # | ← Rev. 3 →   +21 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
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 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 :(
•  » » 10 months ago, # ^ |   0 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 ?
•  » » » 10 months ago, # ^ |   +1 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[1] != 0, so move forward index = 2, res[2] != 0, so move forward index = 3, res[3] == 0, so assign res[3] as 1 (pointer points to 1) and move pointer along until we encounter another 0. So, now pointer points to 3. index = 4, res[4] != 0, so move forward index = 5, res[5] == 0, so assign res[5] as 3 and move pointer to 7. index = 6, res[6] != 0, so continue. index = 7, res[7] == 0, so assign res[7] as 7. But, the last one won't fit well.Since, res[7] = 7 is not allowed. So, see what was at index 7 in original array. a[7] was 6. So, make res[7] as 6 and wherever 6 was placed, place 7 there. I hope this is clear. If not, let me know.
•  » » 10 months ago, # ^ |   +3 thanks for your approach it helped me.
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 u rote "first occurring 2 and 1" instead of "6 and 1" at line 6 of ur comment. Update : also im getting runtime error on test 3(I have followed the same approach as yours). Pls check and tell me if u have time! https://codeforces.com/contest/1530/submission/130407870
•  » » 7 months ago, # ^ |   0 It's very clever to ensure that the maximum number of gifts remains the same in the form of exchange. I understand MY Code https://codeforces.com/contest/1530/submission/130934803
 » 10 months ago, # |   +57 Interesting problems, especially E.Thanks for contest!
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 can u pls explain the solution for E...pls
•  » » » 10 months ago, # ^ |   +33 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[0]$ 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
•  » » » » 10 months ago, # ^ |   0 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 :}
•  » » 10 months ago, # ^ |   +22 I am sorry but what exactly was interesting in problem E ?
•  » » » 10 months ago, # ^ |   +3 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.
•  » » » » 10 months ago, # ^ |   +8 kinda C problem I am probably sure algo-police is on the way after you saying that :/
•  » » » » 10 months ago, # ^ |   +3 So you solved the better and harder D but seem yet to recognize all cases in E, huh?
•  » » » » » 10 months ago, # ^ |   0 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)))
•  » » 10 months ago, # ^ |   0 the f function is how form the every value(f[1]....f[n])
•  » » » 10 months ago, # ^ |   0 sorry，i got the prefix function！！
 » 10 months ago, # | ← Rev. 6 →   +18 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
•  » » 10 months ago, # ^ |   0 It helps me a lot, thank you =))
•  » » 10 months ago, # ^ |   0 The same way as you, it's a good idea.
 » 10 months ago, # |   0 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.
 » 10 months ago, # | ← Rev. 2 →   +16 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.
•  » » 10 months ago, # ^ |   +87 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.
•  » » » 10 months ago, # ^ |   +16 That's reasonable. Thanks for your reply.
•  » » » 10 months ago, # ^ |   +46 What was the reason for the strange modulo?
•  » » » » 10 months ago, # ^ |   +57 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.
•  » » » » » 10 months ago, # ^ |   +16 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?
•  » » » » » » 10 months ago, # ^ |   +28 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.
•  » » » » 10 months ago, # ^ |   +72 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.
 » 10 months ago, # |   +13 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
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 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.
 » 10 months ago, # |   +9 Great Contest, thanks tourist. Highly appreciated
 » 10 months ago, # |   +16 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.
•  » » 10 months ago, # ^ |   0 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.
•  » » 10 months ago, # ^ |   0 swap(ans[b[a[i]]],ans[i]); explain this clearly
•  » » » 10 months ago, # ^ |   +3 here, see this solution, it's the same method as the guy, but I have added comments, which should hopefully help
 » 10 months ago, # | ← Rev. 2 →   +6 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 :)
 » 10 months ago, # | ← Rev. 2 →   +8 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！
 » 10 months ago, # |   +8 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
•  » » 10 months ago, # ^ |   0 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.
•  » » » 10 months ago, # ^ |   +8 Thanks, I'm still not sure why being random passes will look into it in some time I guess.
•  » » 10 months ago, # ^ |   0 Why are you adding an edge between the person and Unliked person?
•  » » » 10 months ago, # ^ |   +8 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.
 » 10 months ago, # |   +17 ecnerwala Can you please upload the video the stream on youtube? Quality 1080p lags a lot with many of ours internet.
•  » » 10 months ago, # ^ |   +40 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!
 » 10 months ago, # |   0 Very simple solution for D using only arrays and vector : 122836640
•  » » 10 months ago, # ^ |   0 Can you explain what the last for loop does?
•  » » » 10 months ago, # ^ |   0 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.
 » 10 months ago, # |   0 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!
 » 10 months ago, # |   -13 Did anyone else solve C using a treap?
 » 10 months ago, # |   +9 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.
 » 10 months ago, # |   +30 The promble E 1530E - 12 - Минимакс, 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
•  » » 10 months ago, # ^ |   0 can u pls explain E...pls
•  » » » 10 months ago, # ^ |   0 sorry... I don't think I have words better than the editorial. And, I havn't pass yet. QAQ
•  » » » » 10 months ago, # ^ |   0 no probs bro, i got the editorial now, cool
•  » » 10 months ago, # ^ |   +64 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.
•  » » » 10 months ago, # ^ |   +3 My bad. Thanks for your reply.
 » 10 months ago, # |   0 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(); } 
 » 10 months ago, # |   +19 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?
•  » » 10 months ago, # ^ | ← Rev. 2 →   +30 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) •  » » » 10 months ago, # ^ | +14 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)$
 » 10 months ago, # | ← Rev. 5 →   0 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.
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 You included But why include vector, algorithm,set etc? etc.?
•  » » » 10 months ago, # ^ |   0 Eh, I also don't know. xD
•  » » 10 months ago, # ^ |   0 Isn't the time complexity of vector erase is O(n)?
•  » » » 10 months ago, # ^ |   0 I thought it was $O(1)$. Thanks!
 » 10 months ago, # |   0 Can Problem C be solved without binary search?
•  » » 10 months ago, # ^ |   0 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.
 » 10 months ago, # |   +4 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
 » 10 months ago, # | ← Rev. 5 →   +5 A solution for problem C. Simple and Easy to understand, Hope it helps ! Submission Link — 122895932
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 nice :)
 » 10 months ago, # |   -34 tourist Can you provide your test case generator for C, in case they many of them in pretest 2 were not hand made?
 » 10 months ago, # |   +29 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?
•  » » 10 months ago, # ^ |   0 Thanks for the explanation!!
 » 10 months ago, # |   +10 Problem B simple explanation Putting Plates
 » 10 months ago, # |   0 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
 » 10 months ago, # |   +7 Problem A Simple Explanation Problem A
 » 10 months ago, # |   +13 Short code for B (Perl) — 122869086
 » 10 months ago, # |   -66 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[0].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; } 
•  » » 10 months ago, # ^ | ← Rev. 3 →   0 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
•  » » 10 months ago, # ^ | ← Rev. 2 →   +32 Please try to use spoiler tag before posting long codes. Like thisIt'sveryirritatingwhensuddenlythecodecoversthewholescreenandyouhavetoscrollsomuch!
•  » » » 10 months ago, # ^ |   +9 Even better, post a link to your submission, then we can see the failed tests.
•  » » 10 months ago, # ^ |   0 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).
 » 10 months ago, # |   0 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"
 » 10 months ago, # | ← Rev. 2 →   0 Can anyone please help with problem C, what's wrong with my solution submission ? I've tried many times, couldn't find the issue.
•  » » 10 months ago, # ^ |   0 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.
•  » » » 10 months ago, # ^ |   -10 Got the issue finally, did correction while calculating llya's score, now it got accepted. Thanks !!
 » 10 months ago, # |   0 Here is my solution to problem C using binary search on answer link P.S."also my first comment"
•  » » 10 months ago, # ^ |   0 great work
 » 10 months ago, # |   +8 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
 » 10 months ago, # |   0 Actually we can brute force C: 122875589
 » 10 months ago, # |   0 tourist Any updates on the editorial for the problems F,G,H?
•  » » 10 months ago, # ^ |   +17 i'm sure that he is working hard to catch up with it. be patient please
 » 10 months ago, # |   0 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.
 » 10 months ago, # |   +78 Please update editorial for problem F. Or can someone help me with it ?
•  » » 10 months ago, # ^ | ← Rev. 2 →   +1 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)$
 » 10 months ago, # |   -36 1 day i will beat tourist...i will become ultra legendary grandmaster
•  » » 10 months ago, # ^ |   -8 Good Luck brother!!
•  » » 10 months ago, # ^ | ← Rev. 2 →   +16 you can beat everyone. you just need to... Spoilerflip everyone's rating curve upside down.
 » 10 months ago, # | ← Rev. 2 →   0 Can anyone share priority queue approach and code for problem C, I am not able to figure out mistake in my code.
•  » » 10 months ago, # ^ |   0 You can see my submission
 » 10 months ago, # |   0 Can anyone explain their DP solution for F ? The one which is $O(2^{n} n^{2})$
•  » » 10 months ago, # ^ |   +8 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)$
•  » » » 10 months ago, # ^ |   0 Thnaks for your reply. Can you provide some resource on "and-convolution" ? Is this related to fft ?
•  » » » » 10 months ago, # ^ |   0 You can search "Fast Walsh Hadamard Transform". I only have Chinese resource : oi-wiki.
•  » » 10 months ago, # ^ |   0 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)
 » 10 months ago, # | ← Rev. 3 →   0 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...
•  » » 10 months ago, # ^ |   0 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.
 » 10 months ago, # |   0 prefix function is how to form the f[1] to f[n]
 » 10 months ago, # |   0 in codeforces i can learn many,thanking everyone!
 » 10 months ago, # |   0 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?
•  » » 10 months ago, # ^ |   +6 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.
 » 10 months ago, # |   0 in F why 1-f（1，{}） is equal to 1+f(n+3,S)? PLEASE
 » 9 months ago, # | ← Rev. 2 →   0 Can anyone explain the thought process of reducing problem F from 2^(2n+2) to 2^(n+2) if one is following the basic inclusion-exclusion process?
 » 9 months ago, # |   +1 does E really **** interesting ???
 » 8 months ago, # |   0 Why my problem C give wrong answer in test case 2nd 102 Here is the link https://codeforces.com/problemset/submission/1530/128546861Can someone help in figure out the error I use the same logic as editorial
•  » » 8 months ago, # ^ |   0 You haven't considered the condition when number of stages become divisible by 4. In that case you have to decrease aSum. Read the editorial once again
•  » » » 8 months ago, # ^ |   0 Thanks dude.
 » 8 months ago, # | ← Rev. 2 →   0 https://codeforces.com/contest/1530/submission/129846951 this is my code for problem c using binary search but i can't understand why it's giving WA in TC 2 ! Someone plzz help;
 » 5 months ago, # |   0 what does '|' mean in P(Li|Ls1∩…∩Lsk) (problem F)