Me too！Fighting for the last 30 points!

So why U dont participate?

But the time is not friendly...

So why U dont participate?

*contest

I got -49 and -41 in two Div.3 rounds when I was a Pupil. Hope you can get rating increasing in Div.2 rounds :)

As I know, you can't register in 2 minutes before the round starts, because registration cancels in 5 minutes before, so you may got a bug with a CF and you somehow registered (but no).

You get this message iff you make the exact same submission without any code change. This actually prevents making the same submission twice (making the submit button idempotent).
It might be the case that your friend either made the same submission again or it just happened due to some network issue. In either case, at least once the submission should have been submitted.

I've met the same thing before..

It was working for me. so mostly only you or maybe I did not do any submit in that 30 min mark to even notice it. But if it happened people would complain here I guess

I was using and refreshing Codeforces constantly (to see friend's standings). Didn't even go down once for me.

It was down for me also

During last few seconds, I was not able to submit. But not for 30 minutes for sure.

Store, for each vertices cnt[v] = number of leaves in subtree rooted at v, and dp[v] = maximum number v can get, if leaves in its subtree are assigned numbers from 1 to cnt[v].

Transitions can be derived by considering relative order.

binary search on the value, for a given x, all values >= x will become 1, otherwise 0. then do a normal dfs to find the minimum needed 1s and if it's less that the 1s you have, then it's true, otherwise false.

For each vertex find number d such that we need d numbers >= x to get value x in this vertex. For leaves it's 1, for min it's sum of this value in children, for max it's min of this value in children. Now answer is number of leaves — this value in root.

It's a dp problem on tree. You can see my submission later 52702102

write the formulas open the formulas and integrate it. no very good observations pure math

The solution of F is DP. Editorial will be out later. :)

Same here probably not couting some flush or idk...

sorry

I figured my issues and got AC. My submission: 52716310.
(For reference, my WA3 solution: 52711736)

However, I still think Codeforces judge system worked a bit weird.

If my implementation was correct (hopefully I didn't misread anything), any time I read value -1 my code would terminate immediately with a non-zero return code, therefore force-runtime-error my solution. Yet in this case (well too bad I use only 1 exceeded query :"> ), guess the interactor stopped and sent the verdict to the checker immediately before I had my chance to force-RE. :D

Weird, but I won't blame anyone. Today I learned. :">
Thanks Codeforces and the setter team for the round. ;)

try to make '(' from left and ')' from right ....

Firstly odd strings will never work. Secondly you will always need same number of ( and ) in the final string. Thirdly you want to change ? to ( in the beginning of the string and ? to ) in the last part of the string.

Then just do the usual stack code to check if the parenthesis are balanced.

Code

it's probably something like this

10

(?)?)??(?) which should print (()()()())

found that bug in my solution but hadn't enough time to fix it

maybe 6 ???)??

answer should be ((()))

Same, I tried hacking but cf was too slow at the end :(

Similar thing happened to me too, but while loading (and eventually getting 502 bad gateway error) there was a notification to browser that said pretests passed

Hint for E: Answer for the query == 1 (mod) 2 iff exactly one of ends of snake lies in asked rectangle.

I feel sorry about it but we havn't seen this problem before this comment. :(

Even I was doing the same mistake for almost an hour :(

Then suddenly striked a test case

6 ((?)))

Your Output: :( Correct Output: ((()))

You use a greedy way for parenthesis completion, which fails to form a valid solution in several cases. Try:

8 (????)))

Similarly, when the input is like this,

6

???)??

after executing your code the string s is (())??, and according to Line 40(the third of the five cout<<":(";), print :(, and end. But the correct answer is ((())).

I felt same, but I got AC.

A bit intuitively, but we can see a few things:

• If the chosen rectangle contains exactly one end of the snake, the query result will be an odd integer, otherwise the result will be even.
• Since two ends of the snake are in different cells, there must be either two columns or two rows that each contains one distinct end of the snake.

Our solution will be divided into two phases:

Phase 1: Find the columns/rows with the snake's end.

Assume that the snake's head and tail stays at different rows, let's denote them as $$$xa$$$ and $$$xb$$$ (since we don't really care about the order of the head and tail, assume that $$$xa < xb$$$). Thus we'll see that: - $$$xa$$$ is the lowest row index $$$x$$$ such as query ? 1 1 x n returns an odd value. - $$$xb$$$ is the lowest row index $$$x$$$ higher than $$$xa$$$ such as query ? 1 1 x n returns an even value.

If searching for the rows didn't do, we repeat the similar process with the columns.
In theory, this phase takes up $$$2000$$$ queries, but we can shrink it to $$$1998$$$, knowing that querying with the last row/column always results in $$$0$$$.

Phase 2: Find the exact cell in each row/column.

This part has a binary search concept.

Assume that we're working with rectangle x ya x yb (if the rectangle has the form of xa y xb y, we can do similar things).

Assume $$$ym = \lfloor \frac{ya+yb}{2} \rfloor$$$. We'll query the rectangle x ya x ym. If the returning value is odd, continue the binary search with that rectangle, otherwise continue with the rectangle x (ym+1) x yb if such rectangle exists.

Repeat the search until the rectangle consists of only one cell. That would be the head/tail we need.

Each binary search process consumes at maximum $$$\lceil \log2(1000) \rceil$$$ queries, or $$$10$$$ queries.

We have two rows/columns to deal with, so the second phase will use up to $$$10 \cdot 2 = 20$$$ queries.

In summary, the process (at its most optimal form) will use $$$2018$$$ queries at most. Pretty close. :D

My solution, for reference: 52716310

If the result of a query is odd, then exactly one snake end must be in the rectangle.

Query all rows. If both ends are in different rows, we obtain two queries with an odd result and can binary search the cell in both rows.

If all rows return an even result, this means that both ends must be in the same row, therefore both ends can not be in the same column. Query all columns to get the columns of both ends. Then, for the first column binary search one snake end. As both snake ends are in the same row, we are done.

As binary search takes at most 10 queries for $$$n\leq 1000$$$, we have that in the first case we use at most $$$1000 + 2\cdot 10\leq 2019$$$ queries. In the second case, we use at most $$$2\cdot 1000 + 10\leq 2019$$$ queries.

My approach using some observe:

1. max node would ignore all small number from subtree
2. min node would sum all number from subtree
3. result of a subtree is bounded with its size

try it!

https://codeforces.net/contest/1153/submission/52707952
(I traverse with bottom up)

I used the same approach.
It's based on the observation that we should give priority to put open brackets first in the sequence. So we just count in the first iteration that how many open brackets we can put more in the string (Remember you cannot put more than n/2 open brackets).
In the next iteration whenever we get a '?' we put open brackets until we have exhausted them all and then put all the closed ones. At each point we check that the balance should not be less than or equal to 0 except at the end of the string where it should be exactly zero.
Why this works? Because in any valid sequence you can always replace a closing bracket with a later open bracket.

We feel sorry about forgetting to explain it, but I wish you can get it from the first sample and its illustrations. :)

I think that your binary search may take 10 queries. Note that if you start with i = 2^9 it'll be divided 10 times until it reaches 0

Cool, I found one above .

You need to iterate the string "from both sides", or twice. First time counting the opening, and closing brackets. Second time replacing the question-marks. Replace them by open brackets from the left, and closing ondes from the right, make sure number of open and close is same. Check if the resulting string is correct. If yes, then all prefixes of it are not correct.

you can iterate the string from left to right and replace "?" with "(" as many as you can,you can see that other position must be replace with ")".when you replace all "?" with "(" or ")",just check the string to ensure that the string is correct and any prefixes is not correct.hope that can help you and sorry my English is poor,hope you can understand...

If I understand your formula correctly, $$$a$$$ is the time of first bus arrival and $$$b$$$ is the period of buses arriving.

You calculate answer as minimum of some values by modulo of each $$$b$$$, so answer will never exceed $$$min(b)$$$. Consider test cases like this: $$$n = 1, t = 1, a_1 = 1234, b_1 = 1$$$. There will be no buses until $$$1234$$$ time moment but your solution will give $$$0$$$ as answer.

It's not allowed, but I did everything on my own so don't worry.

That's already published: D