already getting bad vibes

The contest is tomorrow

that's 23 hours bro

The term "Educational Contests" specifically refers to the initiative by Harbour Space University, so it's organized by the same individuals, with a few occasional variations.

Stay positive man...

I agree with you.

bro you have already skipped all the contest in the last 6 month , i don't think so you should be saying that when you are not active

Lol you were right with this one ^^

Even C is really annoying binary search problem.

What difficulty gap are you talking about? In my opinion, D was easier than C

For me, this is one of the harders Div2Cs ever, but D seems ok if you have seen the trick.

It can be noticed that the answer of a string $$$s[0..n-2]$$$ is the product of the indexes with letter '?', thus the problem can be solved easily.

Consider the relative order of all the elements, a single "order sequence" corresponds to a permutation. We consider how many of these sequences are achievable by iterating over [1, n]. If a[i] = < or a[i] = >, then we can only place it in the front or back of the current sequence, resulting in an *1 to the answer. Otherwise, the previous i — 1 numbers have i — 2 spaces between then, we can just randomly insert a[i] into one of these, since any two ways of insertion is equivalent, this would result in an *(i — 2) to the answer.

For the operations (i, c), we notice that every single one of them only result in the change of ways to insert a[i], thus we can make our answer /(i — 2) if it is not ? before the operator and *(i — 2) if not ? after it. We can prework inv to speed the process up to O(n).

btw, note that if a[1] = ?, the answer is 0.

You can have an order from the first i chars of the string. Now if you get a '>' then a new element has to be put at the end of the order and if you get '<' then put it at the beginning. If you get a '?' then you can put a new element at any position except first and last. There are i-1 such positions. So total possibilities is the product over all (i-1) such that s[i] == '?' (one based indexing).

Why is it that the problems I don't solve always have the most elegant and easy solutions...

The case that broke my attempt was:

dttkjvzob
34

Output should be o

Binary Search : There are 4 conditions you can check using binary search 1. Both P & O lies on A 2. Both P & O lies on B 3. P lies on B & O lies on A & Both Circle collides ( radius <= distance between center ) 4. P lies on A & O lies on B & Both Circle collides

Binary Search should not be integer and it terminates whenever abs(h-l) < 0.0000001;

You have to consider 3 cases:

1. O and P are closer to B than they are to A. That means that both O and P are both in the circle around B, so the radius is chosen as the bigger distance of the two to B

2. O and P are closer to A than they are to B: Similar as case 1

3. One of them is closer to A and the other is closer to B: That means the circles are going to intersect, so you take the distance between A and B into account as well, while making sure that the points P and O lay in the circles

I was able to get AC with binary search, which was very obvious.

The tricky part was writing code to check if your radius (w) was valid. There are only two cases; if both the origin and the point P can fit in the same circle, and if they are in separate circles. If they are in the same circle, (i.e if the distance of (0, 0) and (px, py) to the center of the circle is less than your radius), then yes, they fit.

If they are in different circles, then both circles must touch each other or overlap (i.e 2 * w must be >= the distance between the centres of the circles).

Then you can binary search. Instead of incrementing/decrementing by 1s, do so by 0.0000001

I did some case work :

Case 1 : starting and ending points will lie in circle having 'a' as center i.e. dist(a, origin) <= dist(b, origin) and dist(a, p) <= dist(b, p) then only lantern a is relevant so we can set ans as max(dist(a, origin), dist(a, p))

Case 2: starting and ending points will lie in circle having 'b' as center similar to case 1 but lantern b is relevant

Case 3 : the starting and ending points lie in different circles, so we take the answer as the maximum of the distance between origin and the closer lantern, distance between target and closer lantern and half the distance between the lanterns (as this time we need both the lanterns so their circles must intersect or touch each other)

Maybe Case 1 and 2 are irrelevant but I came up with this during contest so no optimisations :)

IMO it's even easier than A

See here.

No answer is just the product of $$$'?'$$$ indexes

Just consider how the answer changes when a new character is appended to the end.

Read the string from right to left instead, and figure out how many possibilities there are.

How you solved E. Is there a well-known technique? Help me out.

Sort the programmers in decreasing order by their strength; if we want to complete a subset of projects, it's optimal to use a prefix of the best programmers. Let $$$dp(S)$$$ be the minimum prefix needed to complete a subset of projects $$$S$$$. Let $$$nxt(i, j)$$$ be the minimum number of programmers needed to complete project $$$j$$$, if we're starting at the $$$i$$$'th best programmer in decreasing order (i.e., we use programmers $$$i, i+1, \dots, i+nxt(i,j)-1$$$).

Then for $$$j \not \in S$$$, we can update $$$dp(S \cup {j})$$$ with $$$dp(S) + nxt(dp(S), j)$$$. The values of $$$nxt$$$ can be precomputed in $$$O(NM)$$$, and computing $$$dp$$$ can be done in $$$O(M 2^M)$$$ using bitmasks. There's a bit more work to be done since we have to reconstruct the answer, but that's entirely routine.

i got 2 WA for that one mistake. Luckily fixed in the last minute

what is ur thought process?

I did it using stack. Coz what you care about is the elements at the front. While your current element is less than last element of stack , keep poping it out. Finally your stack will be of length l or you may terminate in middle if length is reached.Just add index of string to the answer. For finding length and index you can use an O(n) loop which adds i where i goes from n to 1 and compare it with pos each time.

maybe you are too good at combinatorics :)

std::string::erase is linear in time complexity.
https://cplusplus.com/reference/string/string/erase/

This means your code is $$$O(N^2)$$$

Turn back time and assume that at moment $$$0$$$ diamonds $$$2$$$ are stolen and at moment $$$d$$$ diamonds $$$1$$$ are stolen.

For $$$t=1,2$$$ cameras, the time interval to turn it off is determined. For each $$$t=3$$$ camera, it has $$$2$$$ choices:

1. Turn it off in $$$[d+1,s]$$$.
2. Turn off in $$$[1,s], [d+1,d+s]$$$ respectively.

Note the left endpoint of each interval $$$\in { 1,d+1 }$$$. If a decision has been made on what to choose, by Hall's theorem, the illegitimate $$$\Leftrightarrow$$$ appears in at least $$$1$$$ of the following cases:

1. $$$\exists r$$$, $$$>r-d$$$ cameras need to be turned off in $$$[d+1,r]$$$.
2. Think of stealing diamond $$$1$$$ as adding an interval $$$[d,d]$$$, then, $$$\exists r$$$, $$$> r$$$ cameras need to be turned off in $$$[1,r]$$$.

Let's assume, $$$t=3$$$ are turned off in $$$[d+1,s]$$$ by default. Each time, find $$$\min r$$$ such that $$$>r-d$$$ cameras need to be turned off in $$$[d+1,r]$$$. At this point, we need to pick a $$$t=3$$$ camera in the interval and change it to $$$[1,s],[d+1,d+s]$$$. It can be found that the larger the $$$s$$$ chosen, the easier it is to satisfy all the $$$2$$$ restrictions imposed by Hall's theorem. Scan $$$r$$$ while maintaining the stack of $$$s$$$ of $$$t=3$$$ cameras in $$$[d+1,r]$$$, taking the top of the stack ($$$\max s$$$) each time.

If $$$1$$$ of Hall's theorem is satisfied by this scan, it is straightforward to determine $$$2$$$ once. This is because changing any $$$t=3$$$ makes the $$$2$$$ restriction tighter. Thus the problem is solved by enumerating $$$d$$$ at the beginning and sweeping $$$2$$$ times, with total time complexity $$$O(n^2)$$$.

i did the same thing.

Well, You're not alone.

Same :(

'if (r + r < dist)' is the problem.

A doesn't have to overlap with B. Everything could be done with 1 lantern.

double num3 = ((px - bx) * (px - bx) + (px - by) * (py - by)); variable error. u did px-by not py-by.

I was the same as you at first, but I quickly realized that after every comparison, an answer could appear. So every time you compare, you should save the possible answers and finally take the smallest one.

The checker for this problem wouldn't have been a difficult one to implement imo. And I don't think printing in the same line would had have any impact on it..

it's actually very convenient to test your program, since you can query for all positions of the same string and get the resulting concatenation.

Personally, I found it very convenient for testing purposes. I would start with a string, delete $$$x$$$ characters, and then I want to check if my program handled this correctly, so I set up my input to write all characters of that resulting string (so the test cases involve the same original string with the position range corresponding to my desired reduced string). I even wrote a separate program to generate such input text, given the original string and position range.

I don't know if this relates to the reasoning behind why the output was in one line, but I definitely appreciated this!

Video Solution — Problem C: Better Explanation.

Found the error i was taking the pos in an int variable fml

You don't always remove the maximum character. For example, if your string is baz, removing b gives you az, but removing z gives you ba. Here, az is lexicographically smaller than ba, so you remove b instead of z.

The correct character to remove is the leftmost character which is bigger than the character in the next index.

That being said, even if you remove the correct character, your approach of manually finding the character to remove and appending the string would take $$$\Theta (n^2)$$$ time. For $$$n$$$ as high as $$$10^5$$$, this will definitely result in Time Limit Exceeded in later tests.

Here you need to find the real "lowest" one, not from the first one, because the first one might be dropped.

for (int i = dp[subCur] + 1 ; i <= dp[cur] ; i++) {
     res[p].push_back(a[i].second);
}

So for reversed approach, while you are not seeing a ?, your permutation is fixed. The moment you see a ? You cannot remove first and last element which means you can remove any of the remaining i-2 elements.

In forward approach, as you go on filling your array , you set some unknown numbers in your set. The moment you see a ? you are like I can fill this number in any position in my set except the first and the last position so in total again i-2 options

It's not about Monocarp performing the operations in reverse; we still assume Monocarp performs the actions in the order specified, but our analysis considers the number of possibilities in reverse order.

Consider the last character; when Monocarp added the last integer at the end of the activity, what could this integer have been? If the last character is >, then this means that the last number Monocarp added must have been $$$n$$$ (only one possibility). If this last character is <, then this means that the last number Monocarp added must have been $$$1$$$ (only one possibility). If this last character is ?, then this means that the last number Monocarp must be between $$$2$$$ and $$$n - 1$$$ ($$$n - 2$$$ possibilities). We can then extend this argument to all indices in reverse order.

but you didn't solve it using dp

me too :(((, I am pretty sure I joined as a rated participant, but its showing up in my unrated tab

what do u learn new??