Author: TadijaSebez
Tutorial is loading...
Author: oversolver
Tutorial is loading...
Author: TadijaSebez
Tutorial is loading...
Author: TadijaSebez
Tutorial is loading...
Author: oversolver
Tutorial is loading...
Author: Um_nik
Tutorial is loading...
Author: TadijaSebez
Tutorial is loading...
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".
good job!
here, have my downvote
+1
+1, maybe the problem setter will be the next interlude.
+1
+1
+1
+1
+1
I hate weak pretests.
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☹
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 :)
Also, the implementation of E includes a large amount of code, I think it's inappropriate to include it in this two-hour round
Huge difficulty gap between C and D.
And I hate weak pts.
I spent 30 mins solving A,B and C,and during the 1.5 hours left I finished nothing...
Can you please explain your approach to C?
https://codeforces.net/contest/1608/submission/138783479
Can someone help me please?
Pretests were so bad and huge gap between C and D, will definitely have to downvote on this one.
My personal sorry for strong pretests in B and E, I don't like pretests == systests too.
Hope you fst soon.
And what happens? And what will be different from my past fst?
ok so I will change my words : hope you will fst in the upcoming contests.
how could I understand the word "soon" in not future context?
Whatever he didn't mentioned the word "soon" in his second reply LOL.
Darling, I love you too, let's get married.
Buy then woy, my English is week. Can you teel I wath is "Context"
138767795
Check carefully again
Thanks got it. Missed 14,15,3 onwards and onwards.
You are welcome !
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!
everyone talking about downvote, and I am wondering how the "maroonrk" (rank 1) solved B using topological sort :p
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.net/contest/1608/submission/138771063.
When I see C and D:
$$$\text{ }\text{ }$$$ Are you sure this is Div.1+Div.2?
yeah,i have no thoghts of C.
I solved it in O(Nlogn) using fenwick tree
as 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 i
so here we update bit[pair[n-1].first.second] with 1 or any non zero val pair[n-1].first.second is just bi value
we 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 input
now 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-1
as 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 than
First 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 player
now 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<prefmxbi and answer is 1. else the suffix player is there.
Link to code
Please can somebody say what's wrong with my approach? 138778827
A few nice problems ≠ A nice contest. I have to downvote. Hope they can write a nicer contest :(
the problems are great and challenging,but the samples and pretests are so weak.
It's a great contest, the problems are nice, and the pretests can judge your real skill in an efficiency way.
你全家都炸了,双亲早亡还来出题,孤儿院是闲的慌吧
Your whole family has been blown up, and your parents died early and you come to ask questions. The orphanage is idle, right?``
It's a great contest, the problems are nice, and the pretests can judge your real skill in an efficiency way.
What is the purpose of the 1sec. time limit for problem C? Usually these O(nlogn) problems have 2sec...
I passed it in 155ms using O(nlogn) algorithm, so :D
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...).
Is it possible to use Discretization and 2-D Binary Indexed Tree to solve E by O(36(logn)^4)?
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:
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 138786776
I really liked this problem. It's very nice!
Same as my approach..it was a bit annoying to implement tho
Thanks for the explanation. I have been searching for a understandable solution for hours.
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.
Can someone explain fivedemands's solution for problem C ? Thanks in advance.
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.net/contest/1608/submission/138742092
Shouldn't it be max on both sides of the equation?
No it is min only. You can check out my submission too
Ah my mistake, i didn't see the break you had there
Would you please explain why min was taken?
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.
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?
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.
because the players on the right are all "winners" , so ya
It should be max() on right side. I did same thing after contest but still getting WA. :(
see my submission I did by storing right max.
You have sorted in reverse order so you right max is same as my left max
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.
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$$$. ifmaximums + minimums > n - 2
then there is no such permutationCan anyone explain their approach for D ?
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.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 somehow
let's play a little with it, let's swap
2
and3
$$$[1,3,2,4,5,6,7,8,9,10]$$$
And now by a single swap I made one maximum
3
and minimum2
. Now let's swap4
and5
$$$[1,3,2,5,4,6,7,8,9,10]$$$
So
5
is new maximum and4
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
and10
. 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
Great solution.
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 CODE
SAME CODE AC:AC CODE
TadijaSebez Is it due to tight limit or load on server during system check????
UPD: verdict changed!! thankyou
Yeah...
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 :)
I did it with 2 pointer method. https://codeforces.net/contest/1608/submission/138742050 There is lot of templates just ignore those. look at solve()
Can you briefly explain your DFS approach to solve Problem C?
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
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.
B is cancer but C is so cool.
people downvoting should atleast appreciate the effort it takes to conduct a contest.
I think problem D is easier than C.
Problem C :
am trying to solve it by (Binary Search) :
https://codeforces.net/contest/1608/submission/138819932
can any one help me what is the testcase I get WR in it
I've done using binary search too, check out my submission if it helps.
138831067
It helped. Thanks
quantau can you explain what are you doing in 'ok' function
am trying to debug the code to understand it but without any result ;(
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<k<j$$$ . Now, we use the maximum power in 2nd map of all the players with $$$index <=j$$$ to kill players with $$$index > 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.
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.
C'mon at least include the sample codes in the editorials
Could someone please tell me whats wrong with my C solution?
I am essentially doing a reverse dfs.
you forgot to clear the adj array https://codeforces.net/contest/1608/submission/138832488
thank you!
can somebody tell simple countercase for my solution link
Got a WA on TC2 for Problem C, not sure why. https://codeforces.net/contest/1608/submission/138834566
Can somebody tell me what is going wrong in my code or provide any counter case. Thanks
For those who wonders, there exist simple dp solution for C, which requires 25 rows of code Here is it: https://codeforces.net/problemset/submission/1608/138843789
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<int,int> 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
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.net/contest/1608/submission/138845902
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 maximumbi
also?I think $$$b_i$$$ also need to be considered. not considerd:138866797 considered:138866137
I don't understand about the weak pretest for problem D
好
Please use English in Codeforces.
for question C
https://codeforces.net/contest/1608/submission/139063539
logic -→
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
i think my logic is correct but i'm getting wa on 21st testcase
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.
Meanwhile,I think the editorial is hard to understand.
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
It's interesting how there exists 3 completely unique solutions for C!!