why were your solutions skipped in codeTon round 5?

Go and say it infront of the mirror and see the magic

Every problem has equal points. Rankings are determined by penalties. You can read this comment.

Nevermind :(

You can't drink and drive even if you get a negative rating, it's extremely dangerous.

Everyone cares about ur life, please don't joke with ur own precious things. Drunk drive is very dangerous, right?

Guess What?! it is

Wow you got it (same as me T_T)

Too hard A also, i think a lot of people just resigned after trying A

B felt more like a forced question.

Concubine approval

+1, but A was kinda funny

Agree about B. I couldn't solve it and just left being sad, tried D but didn't like it after 5 minuter

It is easy to notice that the chip will be moving along the LIS ending at the i-th element. If the length of the LIS ending at the i-th element is 2, the i-th element is lucky, otherwise Bob can always make himself win. 219331114

Let’s define cnt(pi) as count of elements lesser than pi that comes before it when going from left to right.

Alice can choose an index i if all pj<pi for j<i cnt (pj)=0.

Let $$$d_i = -1$$$ for all $$$i$$$. Now denote $$$d_i = 1$$$, if $$$i-th$$$ element is good, otherwise $$$d_i = 0$$$.

We go from $$$0$$$ to $$$n - 1$$$. It's obvious, that if we now have $$$d_i = -1$$$, then it's gonna be $$$1$$$ if we have no $$$a_j$$$, such that $$$j < i$$$ and $$$a_j < a_i$$$ and $$$d_j = 1$$$, otherwise $$$0$$$. So we just keep $$$2$$$ minimum elements. One with $$$d_i = 0$$$ and one with $$$d_i = 1$$$ and compare $$$a_i$$$ with each of them. After this update minimums.

Answer is $$$sum(d)$$$.

I solved that in O(n) Time complexity (One scan to be exact) and O(1) Space Complexity (No need to make an array).

So we declare two int variables as minLucky (the minimum lucky element until the ith element) and Min (the minimum element till ith element) and initialize them both as INT_MAX. Also, initialize a variable lucky = 0 (this stores the number of lucky elements).

We run n iterations and in each one, input a number (say x) of the permutation and do the following: (1) if x is greater than minLucky, ignore and continue; (2) if x is smaller than Min, update Min = x; continue; (3) if x is greater than Min and smaller than minLucky, then x surely is a lucky element, so increment lucky and minLucky = x (of course x was less than minLucky to reach condition (3))

Finally output lucky and there we go. You can find my code here.

Note: I came up with this solution on my own, although after the contest ended. Also have NOT been able to mathematically prove the working yet. I just took many different test cases and made observations to reach this approach.

PS: This is my first comment/post on this site. English is not my first language

Imagine English being your official language but you find it difficult to even understand the problems T_T...

Consider the case 111111111.....000000000.....

Ah, I see now. Guess the constraints fooled me into thinking it was some kind of brute force.

It does seem to be fairly low for this problem, but I think you can prove it's at least N/8 in the general case.

Rationale: you can start with a string of (N/2) 0s followed by (N/2) 1s which creates an imbalance of (N/2)^2 and any swap can reduce the imbalance by at most 2N, and (N/2)^2/(2N) = N^2/8N = N/8.

You can change any string s to any string t with at most n/2 swaps, so n/2

Suppose you decide to take 2, then the opponent will take 1 and you won't be able to make a move so, you win. Suppose you decide to take 3, then the opponent will take 2, then you will take 1, because of which your opponent wins. Suppose you decide to take 4, then the opponent will take 2, then you will take 1, because of which your opponent wins.

Yep, basically if $$$s$$$ doesn't occur in $$$(((...)))$$$ then it's an answer, otherwise if $$$s$$$ doesn't occur in $$$()()...()()$$$ then it's an answer, otherwise there is no answer.

i think you ignore the case when n=1 and string="("

In my solution I just make 2 strings "((...))", "()()..." and checked if input string is a substring of first, then the second is the solution. Also the "NO" answer comes only with "()".

Agree

It felt really forced, like they had to place a problem B somewhere and came up with a contrived problem

Video editorial for problems A&B:

https://youtu.be/p-nKn3Hg9JE

Thought would be useful!

IN ENGLISH

UPD: My greedy solution was wrong

I solved it using 3D-DP. Sketch: Assume w.l.o.g there are more 10 than 01. Then there is a diff > 0 you need to fix. Swapping a 1 with a 0 on the right fixes 2*(difference of indices). Now you can do similar to subset sum dp (you need a third dimension to store the position of the first 0 you used). The value of an entry denotes how many swaps you need to achieve this sum. Total runtime O(n^4).

Maximum size of 0 or 1 doesn't matter for solution.... But maximum value of balance matters which can be at most n/3*n/3

ternary search or some simple math

I wish your code was readable.

bro your code looks like its from a nuclear reactor in Iran

You are using memset on a 3e6 size dp for every test case. The total possible test cases are 1e4. So time complexity of your code will be more than 1e10.

maybe because it's a segment tree problem ?

bruh what do you need all those defines for, bet you don't use even a quarter of them often enough to justify adding them to the template

I SUBMITTED 3 WA BECAUSE OF THIS.

THAT SUCKS

without music :"(

nah it's good

I can't prove my solution. But actually greedy approach works. Let's denote $$$cnt1$$$ equal to number $$$01$$$ occurs in $$$s$$$ as subsequence and $$$cnt2$$$ equal to number $$$10$$$ occurs in $$$s$$$. Now let's find such $$$i$$$ and $$$j$$$, that after swapping $$$s_i$$$ and $$$s_j$$$ we will make $$$|cnt1 - cnt2|$$$ smallest. Swap $$$s_i$$$ and $$$s_j$$$ and continue doing this until you get $$$|cnt1 - cnt2| = 0$$$.

I did it ternary Search

No I don't think so , there is no monotonocity of some property , It was just greedy one.

i don't think lis is needed though:

My submission that passes tests 219294134.

When i find a new m2, that element is winning because it can't reach any former m2 (all of those are bigger) and there's an m1 that the m2 can reach (meaning that a move exists and it leads to a losing state). It's easy to see that all the other moves are losing : if an element doesn't enter any of the ifs, it's trivially a losing one as that can reach another losing element (basically it can reach any m2, as it's bigger).

This proof feels harder than the code, i 100% didn't think it this way when i wrote it but it feels right.

Hope that my solution is right and easy to understand 219268377

I would recommend you to firstly participate virtually in some Div3 or even Div4 rounds. Difficulty of problems there should suit you way better than Div2. But to be fair, usually problems A and B are a bit easier than in this contest. Good luck!

DW, this contest was way harder and weirder than other div2 contests. Try again in another contest.

A is the kind of stupid problem that you take a bold guess by intuition. I looked at it for 5 mins and guess I only have to test ()()() and ((())) kind of bracket sequence and luckily it passed. I did a little proof after this. And B is just simple strategy based on modulo. You can find editorial shortly after the contest where you read solutions.

Can someone show simple test which fails on greedy solution?