By TadijaSebez, history, 5 months ago,

Author: Bugman

Author: Bugman

Author: Um_nik

• -170

 » 5 months ago, # |   +43 I think problem B and C required relatively simple ideas but I found them hard to implement. Problem B was uncomfortable to write yet doable. However, I just lost too much time over problem C trying to figure out how to implement "properly".
•  » » 5 months ago, # ^ |   0 same issue belgua
 » 5 months ago, # |   0 good job!
 » 5 months ago, # |   +38 here, have my downvote
•  » » 5 months ago, # ^ |   +26 +1
•  » » » 5 months ago, # ^ |   +8 +1, maybe the problem setter will be the next interlude.
•  » » 5 months ago, # ^ |   0 +1
•  » » 5 months ago, # ^ |   0 +1
•  » » 5 months ago, # ^ |   -11 +1
•  » » 5 months ago, # ^ |   -12 +1
•  » » 5 months ago, # ^ |   -12 +1
 » 5 months ago, # |   +67 I hate weak pretests.
•  » » 5 months ago, # ^ |   +25 I failed the system test on C and D due to some corner cases which is ought to be wrong under small random data, but it passed all of the pretests☹
•  » » » 5 months ago, # ^ |   +29 tell a joke,all the pretests of C expect the samples only have one test case so a number of codes which don't clear pass the pretests :)
•  » » » » 5 months ago, # ^ |   0 That's right, and I don't know why test cases for a multi-test problem only have one case per test in protests. Weird.
•  » » 5 months ago, # ^ |   +26 Also, the implementation of E includes a large amount of code, I think it's inappropriate to include it in this two-hour round
 » 5 months ago, # |   +42 Huge difficulty gap between C and D.And I hate weak pts.
•  » » 5 months ago, # ^ |   +8 I spent 30 mins solving A,B and C,and during the 1.5 hours left I finished nothing...
•  » » » 3 months ago, # ^ |   0 Can you please explain your approach to C?
•  » » 5 months ago, # ^ |   0 https://codeforces.com/contest/1608/submission/138783479Can someone help me please?
 » 5 months ago, # | ← Rev. 2 →   +15 Pretests were so bad and huge gap between C and D, will definitely have to downvote on this one.
•  » » 5 months ago, # ^ |   -94 My personal sorry for strong pretests in B and E, I don't like pretests == systests too.
•  » » » 5 months ago, # ^ |   +2 Hope you fst soon.
•  » » » » 5 months ago, # ^ |   -43 And what happens? And what will be different from my past fst?
•  » » » » » 5 months ago, # ^ |   0 ok so I will change my words : hope you will fst in the upcoming contests.
•  » » » » » » 5 months ago, # ^ |   -60 how could I understand the word "soon" in not future context?
•  » » » » » » » 5 months ago, # ^ |   -7 Whatever he didn't mentioned the word "soon" in his second reply LOL.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +21 Darling, I love you too, let's get married.Buy then woy, my English is week. Can you teel I wath is "Context"
•  » » » » 5 months ago, # ^ |   -8 You made that account with that name just to make this comment! You must have loose some serious rating on your original account.
 » 5 months ago, # |   +5 138767795 Input - 24 4 8 My output - 9 8 10 7 11 6 12 5 13 4 14 15 3 16 17 2 18 19 1 20 21 22 23 24  Checker comment wrong answer expected a=4 and b=8, but found 7 8 (test case 4) Doesn't my solution have 4 local maximums.
•  » » 5 months ago, # ^ |   +3 Check carefully again
•  » » » 5 months ago, # ^ |   +3 Thanks got it. Missed 14,15,3 onwards and onwards.
•  » » » » 5 months ago, # ^ |   +3 You are welcome !
 » 5 months ago, # | ← Rev. 3 →   +11 Problem B and C are quite easy but hard to code.The contest was not so good but problem D and E are interesting but quite bad pretests!
 » 5 months ago, # |   +13 everyone talking about downvote, and I am wondering how the "maroonrk" (rank 1) solved B using topological sort :p
 » 5 months ago, # |   +37 Since the editorial for MEX counting isn't yet available, I'll share my solution. Let $dp_{ijk}$ represent the number of ways to determine the first $i$ elements of the array such that the MEX of these elements is $k$, there are $j$ unique values higher than $k$ in the array, and values greater than $k$ are indistinguishable. For example, the arrays ${0, 2, 3 }$ and ${0, 3, 2 }$ would be equivalent under this scheme, in total contributing $1$ to the value of $dp_{3, 2, 1},$ because both include two distinct values higher than the MEX in the second and third positions, but ${2, 0, 3 }$ would be distinct from these arrays because the fixed $0$ is in a different position, and ${0, 2, 2 }$ is distinct from all three of these arrays and would contribute to $dp_{3, 1, 1 }.$ Note that there are $O(K)$ choices for $k$, so there are $O(NK^2)$ states in total.There are three types of transitions.1: Transitions to a higher MEX. The above DP formulation is useful because it makes these transitions feasible. First, determine the least MEX we can transition to ($k+1$, if doing so does not violate the given constraint, $b_i - K$ if $k+1 < B_i - K$; it is impossible to increase the MEX if $k \geq B_i + K$). If this MEX is $k+1$, then the only possible transition to this MEX is to make the next element of the array $k+1$. However, if this MEX is $k+1+x$ for some $x$, then we must choose $x$ of our unique values larger than $k$ that have appeared so far and assign them to the values $k+1, \cdots, k+x.$ There are $\frac{j!}{(j-x)!}$ ways to do so. Afterwards, we can transition to a MEX of $m+1$ rather than a MEX of $m$ by taking another value larger than $k$, assigning it to $m-1$, and making the next value of our array $m$. Therefore, after performing the above step, we can iterate through our new DP table and transition from $(i, j, k)$ to $(i, j-1, k+1)$ while multiplying by $j$. This allows us to process these transitions in $O(N^2K)$ time in total.2: Transitions in which the next element has appeared already. There are $j+k$ ways to choose this element, giving us $j+k$ ways to transition from $dp_{ijk}$ to $dp_{(i+1)jk}.$3: Transitions in which the next element is higher than $k$ and has not appeared before. Because elements higher than $k$ are indistinguishable, there is only one such transition, taking us from $dp_{ijk}$ to $dp_{(i+1)(j+1)k}.$Once we're finished, we can find our answer by iterating through the values of $dp_{Njk}.$ Note that we must assign the remaining $j$ larger values to numbers greater than $k$ before adding the result to our answer.My code is available at https://codeforces.com/contest/1608/submission/138771063.
•  » » 5 months ago, # ^ |   0 you are a life saver Geothermal, Jay :)
 » 5 months ago, # | ← Rev. 2 →   +41 When I see C and D:$\text{ }\text{ }$ Are you sure this is Div.1+Div.2?
•  » » 5 months ago, # ^ |   0 yeah,i have no thoghts of C.
•  » » » 5 months ago, # ^ |   -8 I solved it in O(Nlogn) using fenwick treeas the values of bi are large so i did a coordinate compression to map the values in range 1 to n as we only require the relative order of values.first i sorted the input on the basis of increasing ai's then one can see that the n-1 player in this sorted input can easily win as it has maximum ai so ans[(n-1)]=1 here n-1 is not same as indx of n-1 element in the provided input as we sorted/modified the input so we can keep track of the actual index by storing ((ai,bi),i) pairs of pair so ans[pair[n-1].second]=1.here we also update bit which stores prefix maximum or sum in my case i used prefix max bit[i] stores mx value from 1 to iso here we update bit[pair[n-1].first.second] with 1 or any non zero val pair[n-1].first.second is just bi valuewe also require prefmx of b's for the sorted pairs so i created prefmx[] array whihc stores max value of bi in prefix of sorted inputnow we iterate from n-2 to 0 now to find answer for a particular i first we see the prefmx[i] whihc gives the maximum value of b's from 0 to i now we use this prefmx val to query in our bit we do query(prefmx[i]) if this query value ==0 then ans[pairs[i].second]=0; else{ ans[pairs[i].second]=1 and also we will update the bit update(pairs[i].first.second,1 or any non zero postive) }now the logic behind this is that if we are standing at i in sorted pairs that one can easily see that we can easily win over all player from 0 to i-1(as current elements ai is max due to sorting) so we just need to verify that whether current player can win over players from i+1 to n-1as current player can defeat any player in prefix(due to more value of ai) and if any player in prefix can can defeat any other player(due to more bi) in suffix whose ans is already 1 than we can easiy see current player can win.if we can found such suffix player whose ans is already 1 thanFirst the player in suffix can defeat all players except current player and the prefix player(we can see that since its ans is 1 it is capable of defeating all players) then prefix player can defeat suffix player(due to more bi) and then current player can defeat prefixplayer(due to more ai).now first we are finding the the maximum value of bi that is present in prefix now the player with max bi is prefix playernow we query in bit query(maxbi) which gives a positive number if there is any suffix player whose ans is 1 present(as whenever we get answer one we are updating the bit for that value of bi).so if there is any player in suffix whose bi < prefmxbi and answer for that player is 1 than current player can easily win otherwise not.the answer for query(prefmxbi) is zero if there is no suffix player whose bi
 » 5 months ago, # |   0 Please can somebody say what's wrong with my approach? 138778827
 » 5 months ago, # |   +37 A few nice problems ≠ A nice contest. I have to downvote. Hope they can write a nicer contest :(
 » 5 months ago, # |   -8 the problems are great and challenging,but the samples and pretests are so weak.
 » 5 months ago, # |   +44 It's a great contest, the problems are nice, and the pretests can judge your real skill in an efficiency way. The truth你全家都炸了，双亲早亡还来出题，孤儿院是闲的慌吧
•  » » 5 months ago, # ^ |   -29 IN ENGLISHYour whole family has been blown up, and your parents died early and you come to ask questions. The orphanage is idle, right?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +19 The real English translationIt's a great contest, the problems are nice, and the pretests can judge your real skill in an efficiency way.
 » 5 months ago, # |   +17 What is the purpose of the 1sec. time limit for problem C? Usually these O(nlogn) problems have 2sec...
•  » » 5 months ago, # ^ |   +1 I passed it in 155ms using O(nlogn) algorithm, so :D
•  » » » 5 months ago, # ^ |   +15 Yes indeed, but the reason I am asking is because I write in Java. I translated my java solution to CPP and it passes in 200ms Yet, for java the time limit is strict, and the exact same code TLEs (i didn't manage to translate it in time during contest...).
 » 5 months ago, # |   0 Is it possible to use Discretization and 2-D Binary Indexed Tree to solve E by O(36(logn)^4)?
 » 5 months ago, # | ← Rev. 2 →   +18 I want to describe an approach without graphs for $C$ which is a bit different from editorial and other submissions I have seen. Sort the people by their first map strength. Let us name them $1,2,\dots, N$. Now obviously person $N$ can win the tournament as he has the largest first map strength.Let us assume we have the answer for all people from person $i+1$ to person $N$. Now let's look at person $i$. He can beat all people from $1$ to $i-1$ as he has greater 1st map strength. I claim that person $i$ can win if and only if there exists a person $j$ such that: $i \lt j$ Person $j$ can win the tournament 2nd map strength of person $j$ $\lt$ than $max_{k = 1}^{i}$(2nd map strength of person $k$) By moving right to left, we can keep track of the minimum so far of the 2nd map strength of a winnable person and compare with prefix max of 2nd map strengths. My submission 138786776I really liked this problem. It's very nice!
•  » » 5 months ago, # ^ |   0 Same as my approach..it was a bit annoying to implement tho
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Edit: That was a wrong reasoning, I misread your comment. Thanks anyways :)
•  » » 4 months ago, # ^ |   0 Thanks for the explanation. I have been searching for a understandable solution for hours.
 » 5 months ago, # |   -18 I came here to plug my solutions video, but looking at the downvotes just made me sad and I would just like to say, the contest was nice guys, weak pretests sucks yea, but problem C was nice atleast and I even got +ve, so win for everyone.Yes, I still plugged my video, I ain't no saint.
 » 5 months ago, # |   +6 Can someone explain fivedemands's solution for problem C ? Thanks in advance.
•  » » 5 months ago, # ^ |   +6
 » 5 months ago, # | ← Rev. 2 →   +23 I have an alternate solution to C.Sort all players by $a_{i}$. Now iterate in reverse. Player $n - 1$ can always win so we start with $i = n-2$. If $max(b[0],b[1],...,b[i]) > min(b[i+1],b[i+2],...,b[n-1])$ then this player can win, otherwise break since no smaller players can win now. Note that the $b_i$ order is different than input since the array is now sorted by $a_{i}$.https://codeforces.com/contest/1608/submission/138742092
•  » » 5 months ago, # ^ |   0 Shouldn't it be max on both sides of the equation?
•  » » » 5 months ago, # ^ |   0 No it is min only. You can check out my submission too
•  » » » » 5 months ago, # ^ |   +5 Ah my mistake, i didn't see the break you had there
•  » » » » 5 months ago, # ^ |   0 Would you please explain why min was taken?
•  » » » » » 5 months ago, # ^ |   +1 I'm not sure how to prove this, but my intution was that if $i^{th}$ position can't win, then no smaller positions can win(hence the break statement). Now I thought that for $i^{th}$ player to win, I only need to check whether he can defeat the $(i+1)^{th}$ player(since I know that the $(i+1)^{th}$ player is winning). That is why I took minimum of suffix and maximum of prefix. I am not at all sure if this is even a correct intution or the final answer just happens to be correct.
•  » » » » » » 5 months ago, # ^ |   0 Exactly! I used the same approach but no idea how to prove it. Also, why does it not matter if I sort the first array or second array? I think this approach transposes to the editorial solution. Can someone help connect the dots?
•  » » » » » » 5 months ago, # ^ |   0 My attempt at its proof... Lets assume that (i + 1)th player is losing but ith player is winning. ith player can only be winning if the max(b[0],b[1],..,b[i]) is greater than max(b[i + 1],b[i + 2],..,b[n]) since it needs to beat all the players with greater strength in mapA with the help of mapB. So if its possible then it should also be possible for (i + 1)th player as the prefix of ith player is a subset of prefix of (i + 1)th player. Thats why we assumed it wrong. Conclusion:- ith player is winning only if (i + 1)th player is winning. Please correct me if I am wrong.
•  » » » » » 5 months ago, # ^ |   0 because the players on the right are all "winners" , so ya
•  » » 5 months ago, # ^ |   0 It should be max() on right side. I did same thing after contest but still getting WA. :(
•  » » » 5 months ago, # ^ |   0 see my submission I did by storing right max.
•  » » » » 5 months ago, # ^ |   0 You have sorted in reverse order so you right max is same as my left max
•  » » 5 months ago, # ^ |   0 This is a great solution!!!
 » 5 months ago, # | ← Rev. 2 →   0 And I've seen that the solution to the problem is being hacked too much.
 » 5 months ago, # |   0 Can someone please tell me why did we check a+b+2 < n condition in B question and how did we construct the order since the editorial is a little tough to understand.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 If we have an array of integers with indexes $[0, n - 1]$, then we count maximums and minimums in range $[1, n - 2]$. So maximum amount of a + b you can get (i.e. amount of maximums + amount of minimums) is $n - 2$. if maximums + minimums > n - 2 then there is no such permutation
 » 5 months ago, # |   +8 Can anyone explain their approach for D ?
 » 5 months ago, # | ← Rev. 3 →   +2 Problem B is definitely obnoxious problem, but I spent an hour and found quite elegant solution. I'm sure you are already noticed that if abs(a - b) > 1 there is no solution. Why abs(a - b) >1?Because between two maximums there is at least one minumum and vice versa.But how can we construct an example of needed permutation?Firstly consider this example: $n = 10, a = 3, b = 3$ i.e. we have permutation: $[1,2,3,4,5,6,7,8,9,10]$ and we need to make 3 maximums and minimums somehowlet's play a little with it, let's swap 2 and 3$[1,3,2,4,5,6,7,8,9,10]$And now by a single swap I made one maximum 3 and minimum 2. Now let's swap 4 and 5$[1,3,2,5,4,6,7,8,9,10]$So 5 is new maximum and 4 new minimum. So by swapping I can produce 1 maximum and 1 minimum. And for test case $a = 3, b = 3$ you just can do another swap and there you go, you have needed permutation $[1,3,2,5,4,7,6,8,9,10]$ with 3 maximums and 3 minimums.So what to do if we have $a \neq b$? Let's see if $a > b$, and you will see how to do $a < b$ too:Let's consider previous test case $n = 10, a = 3, b = 3$ but with $a = 4$.We ended up with $[1,3,2,5,4,7,6,8,9,10]$ with 3 maximums and 3 minimums. Where 1 extra maximum can appear? Actually we didn't used the right-hand side of array. So in this test case to produce extra maximum we can swap 9 and 10. And now we have $[1,3,2,5,4,7,6,8,10,9]$ which is an answer to this test case. How to produce the minimum instead of maximum? If you store permutation in reverse order you can replace 2 last elements as well. I hope my explanations were clear, also see my implementation: code
•  » » 5 months ago, # ^ |   0 Thankyou FanarillFar better than editorial.
•  » » 5 months ago, # ^ |   0 Great solution.
 » 5 months ago, # | ← Rev. 2 →   0 Is it just me or someone else solution as well TLE in system check but submitting the same code getting AC for Problem C? TLE:TLE CODESAME CODE AC:AC CODETadijaSebez Is it due to tight limit or load on server during system check????UPD: verdict changed!! thankyou
 » 5 months ago, # |   +12 Yeah...
 » 5 months ago, # |   0 In Problem C DFS solution was easy, can anyone give a link to someone's code who did with 2 pointer method? Or anyone here have a video editorial who did it with 2 pointer method? Please share the link. Thanks for help :)
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 I did it with 2 pointer method. https://codeforces.com/contest/1608/submission/138742050 There is lot of templates just ignore those. look at solve()
•  » » » 5 months ago, # ^ |   0 Can you explain your 2-pointer method for Problem C?
•  » » 5 months ago, # ^ |   0 Can you briefly explain your DFS approach to solve Problem C?
•  » » » 5 months ago, # ^ |   0 We can make a graph with n nodes. Each node is a player.We can sort players by strength in a and b. and add edges a_i+1 to ai. which means ai+1 is just stronger than ai. This way, there will be a graph with 2n-2 edges.You can see that the strongest player of a can be the winner, but who else can be the winner? Answer is, anyone who can defeat this strongest player of a.now who can defeat the strongest player of a? anyone who can reach that strongest player of a in that graph.It is easy to find all nodes who can reach a node. Just invert all directions of edges, then the destination node will become source node. Run a dfs from that source and all reachable nodes can be winners
 » 5 months ago, # | ← Rev. 2 →   0 Hey guys, could you explain the approach to problem D? This is what I tried. The 1st observation is number of WW & BB should be same. Then the remaining strings will be either WB or BW. Now we can split into 3 cases, Number of ??, Number of B? or ?B & number of ?W or W?. Somehow we need to make equal number of WW & BB using these cases. For B? or ?B, only BB is possible. Similarly for ?W or W?, only WW is possible. But for ??, anything is possible. After finding the number of ways of making WW's equal to BB's, then for '??', there are 2^count ways. For ?B, only WB is possible similarly if there is ?W only BW. So the answer is Let c0 = count of ??, c1 = count of ?W or W? and c2 = count of ?B or B?. Then the answer is C(c0, i) * C(c0 — i, j) * C(c1, k) * C(c2, l) * 2 ^ (c0 — i — j). where (i + k) — (j + l) = 0.I was able to optimize the second part using vandermonde identity. i.e C(c1, k) * C(c2, l). i.e with the difference of d, where d = k — j, answer is C(c1, d) or C(c2, d) depending of sign of d, * C(c1 + c2 — d, c1 or c2) depending on sign. But cant optimize the 1st part of ??. i.e. Number of ways of getting the difference diff, where diff = number of WW — number of BB. and putting the rest to 2 ^ (c0 — i — j). Any help in optimizing would be highly appreciated. Thanks.
 » 5 months ago, # |   0 Miles of difference between A,B. What an absolute unbalanced round!
 » 5 months ago, # |   +1 B is cancer but C is so cool.
 » 5 months ago, # |   +10 people downvoting should atleast appreciate the effort it takes to conduct a contest.
 » 5 months ago, # |   -12 I think problem D is easier than C.
 » 5 months ago, # |   0 Problem C : am trying to solve it by (Binary Search) : https://codeforces.com/contest/1608/submission/138819932can any one help me what is the testcase I get WR in it
•  » » 5 months ago, # ^ |   +3 I've done using binary search too, check out my submission if it helps.138831067
•  » » » 5 months ago, # ^ |   +3 It helped. Thanks
•  » » » 5 months ago, # ^ |   0 quantau can you explain what are you doing in 'ok' functionam trying to debug the code to understand it but without any result ;(
•  » » » » 5 months ago, # ^ |   0 The vector of pair contains the strengths of each player in first map in sorted order and in vector $b$ the $ith$ element is the strength of $ith$ player of vector $v$ in 2nd map. $ith$ element of $b1$ contains the maximum element of first $i$ elements of $b$. If some $ith$ player can win then any player with index $j > i$ can also win as he will simply let $ith$ player kill everyone except himself and kill $i$ himself in the end. Hence, we need to find the smallest index $i$ which can win then all the players with index $j > i$ will also win. So we apply binary search.Now for some $ith$ player of vector $v$, he can defeat all the the players with $index < i$ , now we will use the maximum power in 2nd map of all the players he killed to kill the players with $index > i$ . After finding some $j > i$ $s.t$ he can kill $jth$ player $i.e$ $b1[i]>b[j]$ , then $jth$ player can kill all the players $k$ where $i j$ . And the process will repeat, if we are able to kill all players then $j=n(1$ $indexed)$ and we return true from the ok function.
•  » » » » » 5 months ago, # ^ |   0 Thank you a lot for this explanation, I owe you one
 » 5 months ago, # | ← Rev. 2 →   -14 I have never heard of any Div.2 or Div.1+Div.2 contests that C is a graph problem and D is a Maths problem like this. The problems are very nice, but I think the contest is awful. I have had my donwvote.
 » 5 months ago, # |   0 In last few contests 1st question was difficult to think, but todays 1st was like lollipop.
 » 5 months ago, # |   +3 C'mon at least include the sample codes in the editorials
 » 5 months ago, # | ← Rev. 2 →   0 Could someone please tell me whats wrong with my C solution?I am essentially doing a reverse dfs.
•  » » 5 months ago, # ^ |   +1 you forgot to clear the adj array https://codeforces.com/contest/1608/submission/138832488
•  » » » 5 months ago, # ^ |   0 thank you!
 » 5 months ago, # |   0 Can anyone help me figure out what is wrong with the below logic for problem C? For each player, I am storing his minimum power in array A and his maximum power in array B. Now the player with the maximum value of B is definitely a winner. So I sorted array B (made another array of pair to also store the index of the player) and I am iterating from the highest power to the lowest power in B. I also made a variable min_power to store the minimum power required to defeat any winning player. Initially, min_power = a[index_with_maximum_value_of_b]. Whenever a player is found whose maximum value is at least the min_power, I include this player in the winner set and also update min_power to min(min_power, a[player_just_included_in_the_set] Any help would be highly appreciated.
 » 5 months ago, # |   0 can somebody tell simple countercase for my solution link
 » 5 months ago, # |   0 Got a WA on TC2 for Problem C, not sure why. https://codeforces.com/contest/1608/submission/138834566Can somebody tell me what is going wrong in my code or provide any counter case. Thanks
 » 5 months ago, # |   0 For those who wonders, there exist simple dp solution for C, which requires 25 rows of code Here is it: https://codeforces.com/problemset/submission/1608/138843789
 » 5 months ago, # |   0 For problem C, I have a much more simple way to do (at least for me). It doesn't require any graph knowledge, just sort and greedy.Observation : If $p$ can be a winner, and $q$ can beat $p$, then $q$ is also a winner.First, we construct two array, sorted by their strength, and also store their index. I use pair to store these data. After that, we maintain $min_{1}, min_{2}$. They are the minimum required strength in map-1 or map-2 to become winner. And we travel from the top of these two array, since we also store their index, we can keep $min_{1}, min_{2}$ decreasing by check map1 and map2 in a rotation. Until it doesn't decrease anymore we stop our algorithm and output.Actually, My strategy in this problem is really similar to this https://leetcode.com/problems/jump-game/. maintain the minimum winnable number on both map .Since we sort, the time complexity will be $O(n\log(n))$.Here's my code. 138742846
 » 5 months ago, # |   0 My approach to C: Sort the array A and B which contains the value and their index in pair. Observe that the player having max A or having max B value will always win. Now for some other player to win, he would wish that either all the remaining players have lesser A value or lesser B value. For eliminating larger B values, we can use max A value to eliminate those players, and similarly, for larger A, we can use max B values. When we are eliminating any element from the B array, we would keep track of the min A value till that suffix of B array, which will denote that our A pointer can be decreased to that min A value and similar operation for B pointer. It will be continued until the current index of A and B corresponds to the same player in the original array. My code : https://codeforces.com/contest/1608/submission/138845902
 » 5 months ago, # |   0 In editorial of C,To find the set of such nodes, we can run DFS from the player with maximum ai.Why only ai? Don't we have to take maximum bi also?
•  » » 5 months ago, # ^ |   0 I think $b_i$ also need to be considered. not considerd:138866797 considered:138866137
 » 5 months ago, # | ← Rev. 2 →   0 Can someone explain how an array is constructed in problem B in easy terms?
 » 5 months ago, # |   +16 I don't understand about the weak pretest for problem D
 » 5 months ago, # |   +7 好
•  » » 5 months ago, # ^ |   0 Please use English in Codeforces.
 » 5 months ago, # |   0 for question Chttps://codeforces.com/contest/1608/submission/139063539logic -→ sorting the strengths take the highest strength index and insert it in set check the next strength , if lies in set then remove it else add it and make its flag as 1(included in answer). if set becomes empty then other players with smaller strength won't be able to win anyone which we have already counted
•  » » 5 months ago, # ^ |   0 i think my logic is correct but i'm getting wa on 21st testcase
 » 5 months ago, # |   0 Why the hell, the tutorial for problem C is so confusing. According to the tutorial, we should use DFS but using graphs not only increases the size of code but it also makes it confusing. There is a really simple approach using maps and the tutorial could have been written in a simple manner keeping in mind that not everyone around here is a Candidate Master or Master.
 » 5 months ago, # |   0 Meanwhile,I think the editorial is hard to understand.
 » 5 months ago, # |   0 +1
 » 4 months ago, # |   0 Did anyone else find the explanation of problem- B difficult to understand? I have solved it in another way but I didn't understand the editorial. Can annyone help me out?
 » 2 months ago, # |   0 holy shit, F is one of the most beautiful problems I've ever seen, upsolved in a day! although my $O(n^2k)$ passes in 3900ms... xD