Yes, it is rated.

Fixed: It's held at the unusual usual time.

If this is the time chosen by the CF management, there must be a reasoning behind it.

Acctually Codeforces round 386 and 387 is held on the tasks of the municipal stage All-Russian Olympiad of Informatics 2016/2017 year in city Saratov. But the Codeforces round 388 is an usual Codeforces div2 round. That's why we have 3 contest in just under 24 hours, the first 2 is like mirrors of the Olympiad and the last is the usual round.

All the best !

It will be!

Good luck! And I wish I can be the witness^_^

Just 3 points, fighting!

I guess even tourist can't solve 120 problems in 2 hours, so 5! is too much I believe.

Don't give up yet!! You can do it!!

Also the first time for me by solving A,B and C!All three passed :D

Your rating will go up like a rocket :)

Nice rating change :D Congratz!

Look at your new rating color! Anyway, nice rating graph :)

congratoulation ✌

Was Blue for less than a day. Back to Cyan for me now!

Mine was: 21 DDDDRRRRRDRDRDRDRDRDR

I got passed pretest with simulation.

I did... It was passing pretests with 998ms. So I rewrote it and now I realized my rewritten solution is wrong.

If you simulated using a queue, it was easy and fast. (And correct, I hope)

You could simulate and even afford an extra log factor(I did this and got 778 ms main tests) for total O(n lg^2 n)

I simulated it, but I used next array (using DSU) to avoid TLE. Which is to jump over the cells that are already deleted. 23151066 my run time is 15 ms because the complexity in total is O(n).

I simulated it. I used two set<int> and lower_bound in them. 23155161.

PD.: Sorry for my horrible English.

Finding vertices from midpoints of sides of a triangle.

You permutate the smaller segment but the whole array still exists.

I know that feel, bro. I hope we don't fall in our ranking

What should be the correct answer?

How can the answer be D?

My answer is R, btw.

And I use the 'wrong' algorithm.

UDP: And I passed the system test.

My solution is just deleting the first undeleted instance of opposite party,

and it PASSED the system test.

Consider positions i and j, then element at pos-j can be less than element at pos-i only if we choose a segment that covers both i and j and then choose an appropriate permutation.
Suppose we fix the segment, then above prob = P(for any r-length segment) = (put j before i if i is placed at pos=k) = 1/r*(sum(k=1..r) (k-1)/(r-1)) = 1/2.

So, just calculate number of segments that cover positions i and j(for all i,j) and multiply overall by 0.5.
1. For i<j a[i]<a[j] we have sum P=(i+1)*(n-j)/(n*(n+1)) to our final result.
2. For i>j a[i]>a[j] we have to sum P=1-(i+1)*(n-j)/(n*(n+1)) to our final result.
Both can be done similar to finding inversions either using divide and conquer(like my solution: http://codeforces.com/contest/749/submission/23156836 ) or BIT for O(n*log(n)).

linearity of expectation
for a pair i , j , such that i < j the probability of j become more than i is p where , so if a_i < a_j , add p to answer else add 1 - p to answer. To do this in O(NlogN) , use bit.

Actually you have to simulate it, but in an efficient way. One way is to use queues, you can use, 1 for all people who is available to vote, other for people in R and other with people in D. The trick here is to realize than in every "iteration" people alive is greatly reduced.

YES :D. I use the same solution :)

i used parallel binary search but i guess its probably overkill

I used the following approach.
Let's insert every people into set. And just delete peoples in query when query comes. Now last element of set is people who won. And now you can erase last element of set and find money. After everything is done you should insert everything you deleted.

i used a set to put every person's "best" bid in it. i also made sets for each individual person which contained all of their bids. Now for every query , i traversed the bestbid set from end, when i found the bestbid whose bidder is still available (to do this i used binary search on all bidders who didnt come). the bidder no can be known using this,let him be y.but the bid maybe lesser than the bestbid of this person,so i again travelled the bestbidset to find another such person who came. if his bid was x , then i have to search bid greater than x in y's bids.i used lowerbound for this purpose.i use x=0 if no x is available.

You shouldn't use printf with ios base synchronisation turned off.

Because you use std::ios::sync_with_stdio(false). If you use this line in your code then it's better not to use scanf/printf. It will be a mess because iostream and stdio can't sync thus the order of output won't be same as you expected.

The C is easier than B, but I failed C.:P

Yes it does.

For all case answer will be three and one can easily get the solution in google.

A little bit changed in problem would be better.

Yeah, I`ve also noticed this

It's not posted yet but U can look at my solution here if U want...my code

:)

I used a queue to simulate..

You can use set to simulate the optimal moves.

The solution I used is O(nlogn). The current candidate removes the next voting candidate of the opposing party. Use std::<set> to keep track of available voters.

I kept two treesets (ordered sets for c++) holding the indexes of each R and each D. starting from 0, I simulated each D skipping the next valid R, and each R skipping the next valid D. What I would do is delete them from the tree set when someone was skipped. Additionally, Tree sets allow you to query the lowest number greater than a given index in log(n) time. So my solution was O(n*lg(n))

I think simulation is the correct solution. It can be proved that after each step, the total no of non eliminated voters will be at least halved. That guarantees atmost log(n) steps of the simulation. Using queues the simulation can be done in linear time. So the overall complexity is O(nlogn).

lol i understand that,it happened to me twice today ... mrning and night :(

R at pos 1 will ban pos 2 from voting.
R at pos 3 will ban pos 4 from voting.
D at pos 5 will ban pos 6 from voting.
D at pos 7 will ban pos 1 from voting.
Now string is RDD.
Pos 1 bans pos 2.
Pos 3 bans pos 1.
So D.

RDRDDRD

INITIALLY R-1,3,6 D-2,4,5,7

POS=1 R-1,3,6 D-4,5,7

POS=3 R-1,3,6 D-5,7

POS=5 R-1,3 D-5,7

POS=7 R-3 D-5,7

POS =3 R-3 D-7

POS =7 R- D-7

ANS D

everyone will play optimally.

RDRDDRD ->R.RDDRD ->R.R.DRD ->R.R.D.D ->..R.D.D ->..R...D ->......D

hope you understand.

jury take a long time to check your solution , jury's problem

S1.erase (pos); u[*pos] = 2;

You are deleting the iterator before accessing it.

R at pos 1 will ban pos 2 from voting.
R at pos 3 will ban pos 4 from voting.
D at pos 5 will ban pos 6 from voting.
D at pos 7 will ban pos 1 from voting.
Now string is RDD.
Pos 1 bans pos 2.
Pos 3 bans pos 1.
So D.

First two R-s kill their neighbor D-s.

It turns to RRDRD, where the third D is about to vote. Next you expell the fourth R -> RRDD, the rightmost D is voting.

RDD -> D wins

mmm, now i see, i didn't think that killing the 1st unkilled instance would make a difference

answer is R ??

They didn't..

becuase you are cheater!

hahaha .. true that

Is there any variable that is used uninitialized? Different compiler on different machines will assign different values to those variables;

My compiler does not even allow it to compile, because

error C4700: uninitialized local variable 'rf' used
error C4700: uninitialized local variable 'df' used

Variable rf is not initialized, so it gets a rubbish value which can be 0. thus rf = 0 => no while loop => !rf is true => printed answer is D.

Line 59:

long long cur = check(mid);
if(cur + 2 <= n - mid) {
    ans2 = mid;
    l = mid + 1;
}

Cur + 2 is incorrect. There can be more than one bid of same person after mid value. Check this case:

5
1 1
2 2
1 3
2 4
1 5
1
1 2