TadijaSebez's blog

Editorial of Codeforces Round #758 (Div.1 + Div. 2)
By TadijaSebez, history, 3 years ago, In English

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...
  • Vote: I like it
  • -170
  • Vote: I do not like it

Comments Comments (105)
| Write comment?
»
3 years ago, # |
  Vote: I like it +43 Vote: I do not like it

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".

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

good job!

→ Reply
»
3 years ago, # |
  Vote: I like it +38 Vote: I do not like it

here, have my downvote

→ Reply
»
3 years ago, # |
  Vote: I like it +67 Vote: I do not like it

I hate weak pretests.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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☹

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      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 :)

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Also, the implementation of E includes a large amount of code, I think it's inappropriate to include it in this two-hour round

    → Reply
»
3 years ago, # |
  Vote: I like it +42 Vote: I do not like it

Huge difficulty gap between C and D.

And I hate weak pts.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

Pretests were so bad and huge gap between C and D, will definitely have to downvote on this one.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -94 Vote: I do not like it

    My personal sorry for strong pretests in B and E, I don't like pretests == systests too.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Hope you fst soon.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -43 Vote: I do not like it

        And what happens? And what will be different from my past fst?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          ok so I will change my words : hope you will fst in the upcoming contests.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it -60 Vote: I do not like it

            how could I understand the word "soon" in not future context?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it -7 Vote: I do not like it

              Whatever he didn't mentioned the word "soon" in his second reply LOL.

              → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +21 Vote: I do not like it

      Darling, I love you too, let's get married.

      Buy then woy, my English is week. Can you teel I wath is "Context"

      → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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)
  1. Doesn't my solution have 4 local maximums.
→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

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!

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

everyone talking about downvote, and I am wondering how the "maroonrk" (rank 1) solved B using topological sort :p

→ Reply
»
3 years ago, # |
  Vote: I like it +37 Vote: I do not like it

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://mirror.codeforces.com/contest/1608/submission/138771063.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +41 Vote: I do not like it

When I see C and D:

$$$\text{ }\text{ }$$$ Are you sure this is Div.1+Div.2?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah,i have no thoghts of C.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please can somebody say what's wrong with my approach? 138778827

→ Reply
»
3 years ago, # |
  Vote: I like it +37 Vote: I do not like it

A few nice problems ≠ A nice contest. I have to downvote. Hope they can write a nicer contest :(

→ Reply
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

the problems are great and challenging,but the samples and pretests are so weak.

→ Reply
»
3 years ago, # |
  Vote: I like it +44 Vote: I do not like it

It's a great contest, the problems are nice, and the pretests can judge your real skill in an efficiency way.

The truth
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -29 Vote: I do not like it
    IN ENGLISH
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +19 Vote: I do not like it
      The real English translation
      → Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

What is the purpose of the 1sec. time limit for problem C? Usually these O(nlogn) problems have 2sec...

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I passed it in 155ms using O(nlogn) algorithm, so :D

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      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...).

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to use Discretization and 2-D Binary Indexed Tree to solve E by O(36(logn)^4)?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

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 138786776

I really liked this problem. It's very nice!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same as my approach..it was a bit annoying to implement tho

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the explanation. I have been searching for a understandable solution for hours.

    → Reply
»
3 years ago, # |
  Vote: I like it -18 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone explain fivedemands's solution for problem C ? Thanks in advance.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

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://mirror.codeforces.com/contest/1608/submission/138742092

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Shouldn't it be max on both sides of the equation?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No it is min only. You can check out my submission too

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Ah my mistake, i didn't see the break you had there

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Would you please explain why min was taken?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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?

            → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          because the players on the right are all "winners" , so ya

          → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It should be max() on right side. I did same thing after contest but still getting WA. :(

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can anyone explain their approach for D ?

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

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?

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 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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Yeah...

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I did it with 2 pointer method. https://mirror.codeforces.com/contest/1608/submission/138742050 There is lot of templates just ignore those. look at solve()

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you briefly explain your DFS approach to solve Problem C?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

B is cancer but C is so cool.

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

people downvoting should atleast appreciate the effort it takes to conduct a contest.

→ Reply
»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

I think problem D is easier than C.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C :

am trying to solve it by (Binary Search) :

https://mirror.codeforces.com/contest/1608/submission/138819932

can any one help me what is the testcase I get WR in it

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I've done using binary search too, check out my submission if it helps.

    138831067

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      It helped. Thanks

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      quantau can you explain what are you doing in 'ok' function

      am trying to debug the code to understand it but without any result ;(

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -14 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

C'mon at least include the sample codes in the editorials

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Could someone please tell me whats wrong with my C solution?

I am essentially doing a reverse dfs.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody tell simple countercase for my solution link

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Got a WA on TC2 for Problem C, not sure why. https://mirror.codeforces.com/contest/1608/submission/138834566

Can somebody tell me what is going wrong in my code or provide any counter case. Thanks

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For those who wonders, there exist simple dp solution for C, which requires 25 rows of code Here is it: https://mirror.codeforces.com/problemset/submission/1608/138843789

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/contest/1608/submission/138845902

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I don't understand about the weak pretest for problem D

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

好

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for question C

https://mirror.codeforces.com/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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think my logic is correct but i'm getting wa on 21st testcase

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Meanwhile,I think the editorial is hard to understand.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's interesting how there exists 3 completely unique solutions for C!!

→ Reply