tourist Just curious to know, What is the Checker code logic for C?

Test Cases are still not visible.

UPD: It is visible now.

Here's my solution for E with proof:

Perfectly balanced tree must have the condition that every level, except possibly the last, must be completely filled.

What's the condition for striped BSTs? Let's find the condition for each child to match condition of its parent. So, if it's a left child, it should have key parity different than the parent and if it's a right child, it should have key parity different than the parent. Now, observe that for a left child $$$u$$$,

This tells us that every node which is a left child of its parent must have even number of nodes in its right subtree. Similary for every right child $$$u$$$,

This tells us that every node which is a right child of its parent must have odd number of children in its left subtree. With these two observations, we can find number of possible subtrees of height $$$h$$$ like this,

For height $$$1$$$, there is only one tree, one node with no children. For height $$$2$$$, there is only one tree, one node with one child on its left and no child on its right.

For each height $$$h$$$, let's store all the possible trees as a pair $$$(a,b)$$$ where $$$a$$$ is the number of nodes in the left subtree of the root and $$$b$$$ is the number of children in the right subtree of the root. Now, we observe the following simple pattern:

For height $$$1$$$ possible trees: $$$(0,0)$$$, possible sizes: $$$1$$$

For height $$$2$$$: $$$(1,0)$$$, possible sizes: $$$2$$$

For height $$$3$$$: $$$(1, 2)$$$, $$$(2,2)$$$, possible sizes: $$$4$$$, $$$5$$$

For height $$$4$$$: $$$(4, 4)$$$, $$$(5,4)$$$, possible sizes: $$$9$$$, $$$10$$$

For height $$$5$$$: $$$(9,10)$$$, $$$(10,10)$$$, possible sizes: $$$20$$$, $$$21$$$

Can you spot the pattern and prove it? For every height $$$\geq 3$$$, there are exactly two trees possible.

Proof: If for height $$$i$$$ we have possible trees $$$(a,x)$$$ and $$$(b,x)$$$ where $$$x$$$ is even, $$$a$$$ is even and $$$b$$$ is odd, then for height $$$i+1$$$, we can have the right child only as $$$(b,x)$$$ as only then then number of nodes in its left subtree will be even. But the left child can have any of the two values as both satisfy the condition of right subtree having even size. Thus, the new trees are $$$(a+x+1,b+x+1)$$$ and $$$(b+x+1,b+x+1)$$$, which can then be replaced with new $$$A$$$, $$$B$$$ and $$$X$$$ having $$$A = b + x + 1$$$, $$$B = a + x + 1$$$ and $$$X = b + x + 1$$$. Thus, we can say that the pattern holds by induction.

Base case has $$$i = 3$$$, which is satisfied as $$$a = 2$$$, $$$b=1$$$ and $$$x=2$$$.

So, find all possible trees till height $$$\log(\text{max value of n})$$$ and output $$$1$$$ if $$$n$$$ is one of those values and output $$$0$$$ if it isn't.

AC Code: 62737057

I’m facing a special problem that actually I want to turn off the cf code editor and I don’t know how to do that. Can anybody help me please?

Am I only one,who solved B with BIT in O(nlogn)?

Problem C is great. I just loved it.

In problem C2, I just wonder is Solve is a recursive function ?

it is my first time to see a thing like this

The intended solution of H is very nice!

Do you know who did this during the contest? It seems the submissions are still invisible.

In problem E, I used DP: $$$dp[i][par_{root}][par_{size}]$$$ means the polynomial where the coefficient of $$$x^j$$$ is the number of ways to build a tree such that the depth is $$$i$$$ and the parity of root value is $$$par_{root}$$$, and the parity of the size value is $$$par_{size}$$$. The answer we want is the sum of the $$$n$$$-th term in $$$dp[d][0/1][n\text{ mod }2]$$$.

Then we have $$$dp[i][r][s] = multpoly(dp[i][\neg r][\neg r], dp[i][0][s \oplus r])$$$. Then I used NTT to do the multiplication and solved it barely fitting in the TL.

Now I realize the base cases are all polynomials with only 0/1 term! Which means we can just store an number for each polynomial, and do the multiplication just by adding those numbers! This will run in $$$O(\log n)$$$, and this offers an different way to prove the model solution of this problem.

Please make video solution for problem D,E,F

tourist Wow, solution to H is actually easier to understand than E and F to me (both needing induction/maths of some kind). Thank you for the great contest! Though your coordinators still have not been announced :O

I overkilled D. I used merge sort tree+ segment tree to solve D. It took me almost 2 hours to implement.

For Problem D, we can find the monotonicity of the position to stop. That is, let $$$s_i$$$ be the position to stop if song $$$i$$$ is the first played song. Then for $$$i = 2, ..., n$$$, it holds $$$s_i \geq s_{i-1}$$$. Here we assume the list is cyclic.

So we can use two pointers to loop over the stopping songs for each starting song. To determine if a song can be added into the current playlist, we need to keep the maximum element of the sliding window. Using STL set can achieve $$$O(nlogn)$$$ time and we can further apply monotonic queue to achieve $$$O(n)$$$ time.

My submission: 62706780. I used STL set in contest, for simplicity of code.

In Problem A in C++ i'm getting WA for cout<<floor(arr[i]/2.0) and Ac for cout<<(long long int)floor(arr[i]/2.0) , Why?(floor and ceil returns nearest integer!

1237B — Balanced Tunnel

"Specifically, can $$$a_i$$$ must be fined if $$$c_i$$$ is bigger than $$$max(c_1,c_2,…,c_{i−1})$$$"

I think, it should be "smaller" — not "bigger". And there is a typo — "can" was meant to be "car".

Another solution for D: split the array into sqrt-size blocks and preprocesses whether the first track of each block can go to all tracks in the block, and preprocess the minimum and maximum of each block. Then iterate over every i from 0 to n-1, and for each i go skipping every block that you can hear all the tracks (keeping the current maximum and checking the minimum of the block).

tourist For problem C, what I did was to first use a stable sort on x of all points, then on y and then on z. Now taking central pairs from this sorted array was supposed to give me the solution but it failed on a test case. Do you think the order of coordinates in the stable sort matters? I mean should I do it like first on z, then on y and then on x?

The cycle formation part in D is not clear.

Isn't it enough to repeat the sequence 2 times ? Please help !

Somewhat funny, slightly different solution for H.

Probably it's more tempting to try to match the last two characters of $$$a$$$ and the last two characters of $$$b$$$. By doing operations like abcdefxyghij -> yxfedcbaghij -> jihgabcdefxy on either $$$a$$$ or $$$b$$$, we can usually achieve this. The only undesirable situation is when $$$a$$$ ends with $$$01$$$, $$$b$$$ ends with $$$10$$$, $$$a$$$ contains no $$$10$$$, and $$$b$$$ contains no $$$01$$$ (or vice versa).

However, this is rather a handy situation in the intended solution! So, if we switch to the intended solution at this point, everyone will be happy. We can even save one more operation.

please can someone provide a simple solution for C2 ,..... I got the approach for it as in editorial but coudn't understand the implementation... please

Spent 2 hours finding tricky cases for A and it happened to be -0 problem because of double. Don't wanna live anymore)

tourist participated in 153 cf rounds and came first in 77 (=ceil(153/2)).
perfectly balanced

Bonus for D: Use a queue/ Double-ended queue:

For i = 1 to 2*n (you can cycle as many as you want, but I think 2 times is enough):

• While a[Q.back()] < a[i]: Q.pop_back() and Unify (Q.back(), i). Here means if you start playing from track Q.back(), you can play track i which has greater coolness, so the result of Q.back() should be the same with the result of i.

• Push track i to the back of the Deque

• Because tracks in the Deque are sorted non-increasingly, so if you push track i to the back of the Deque then you should pop out track from the front of the queue. Suppose j = Q.front() then j is popped out from the front if and only if a[j] > 2*a[i]. Which means if you play from track Q.front() then you must stop at track i.

• After the loop, any tracks left in the Queue is UNSTOPPABLE.

By using Disjoint Set Union, every track in the same connected component has the same result. To maximize, we take the result of the coolest track in that connected component.

Finally, calculate the answer. The overall complexity is O(n) (Or close enough, since I use DSU)

Submission 62720568

How to prove this code?

Is there anyone who wrote FFT in E?

Any simple implementation for C2 with same logic?

I think a better way of solving B would be using queue,as it follows First-in First-out and then all we need to do is to check if the element of b is equal to front element of queue and mark it as visited and pop.If it is not equal then counter++.Also while front element of queue is marked visited,pop it.Here is my solution.

I solved D in $$$O(n^{1.5})$$$.

1. Precompute min coolness and max coolness of $$$\sqrt{n}$$$ intervals.
2. Start from the largest coolness music to the smallest coolness music.
3. Find some specific target values in each iteration.

Check my code for details. https://mirror.codeforces.com/contest/1237/submission/62726962

Here is an alternate solution to E that does not require the solver to initially conjecture that the answer is either $$$0$$$ or $$$1$$$:

Suppose we fix the parity of the root (it will be the parity of $$$n$$$). A perfectly balanced tree is a complete binary tree of depth $$$d - 1 +$$$ some leaves at depth $$$d$$$. So we can find the parities of all the nodes in the complete binary tree (i.e. for all nodes with depth $$$\leq d - 1$$$). Write them down in a sequence, like, for $$$n = 10$$$, the following will be the sequence: $$$0, 1, 1, 0, 1, 0, 0$$$ (we can compute this sequence using a recursion).

Now, since the final inorder traversal will have parities like $$$1, 0, 1, 0, 1, 0 \ldots$$$ (because the inorder will be $$$1, 2, 3, 4 \ldots$$$), we must insert a $$$0$$$ whenever there are two consecutive $$$1$$$s and a $$$1$$$ whenever there are two consecutive $$$0$$$s. Also note that if $$$j$$$ corresponds to a leaf, $$$A_j \neq A_{j + 1}$$$ (proof follows because the next node in the inorder is just the first right turn while moving up from the leaf, and a right turn means a different parity), and if $$$j$$$ is a non-leaf, then $$$j - 1$$$ corresponds to a leaf (because of complete binary tree-ness) and $$$A_{j - 1} \neq A_j$$$ (similar proof). So we have:

1. If $$$A_1 = 0$$$, insert a leaf before (in the left) because the first node has to be 1.

2. If $$$A_j = A_{j - 1}$$$, insert a leaf here (in the left).

3. Otherwise, don't (can't) insert a leaf here.

All this is compulsory for a perfectly balanced striped tree. So the answer exists only if the number of leaves to be inserted is $$$n - 2^{d - 1} + 1$$$ (i.e., the number of leaves you have).

P.S.: Note that proving $$$A_j \neq A_{j + 1}$$$ for leaves etc. was not compulsory. We could just not think about them during the contest, and set answer = 0 if $$$A_j = A_{j + 1}$$$, because if it occurs, you cannot insert anything to fix it (because, same parity on the right). Also if for non-leaves $$$A_j = A_{j - 1}$$$, then that case would be handled by the leaf at position $$$j - 1$$$ (who would give an answer of 0 as just mentioned). But still, the answer will remain $$$0$$$ or $$$1$$$, without deciphering the structure of the sequence. That part could be left to be handled by the code itself.

P.P.S: If I'm not wrong, this also proves that all leaves in the last level should be left children.

Submission: 62757866

For problem C2 I implemented the 3D solution. Here is the java code : 62760448 I sorted the points using Comparator.

Can there be a greedy solution for C2 involving sorting using Manhatten or Eucledian Distance and removing in pairs ?

In tutorial of F

" It follows that $$$R=f(h,dv)∗\binom{h−2dv}{dh}$$$ "

Shouldn't we only choose from rows marked 0 instead of all the h rows? I think it should be

" $$$R=f(h,dv)∗\binom{h- (no of filled rows) − 2dv}{dh}$$$"

Here is an alternate solution for D: lets say we want to find the answer for track x : find the first track after x that has a coolness greater than x (lets call it y) also find the first track after x that has a coolness less than x/2 (lets call it z). if z lies between x and y then the answer for track x will be the number of tracks between x and z. otherwise the answer for track x would be number of track between x and y plus the answer for track y (we can calculate the answers recursively).

I have a question of problem E. If n=5, the tree can be like this: 3 / \ 2 5 / \ 1 4 Also, it can be like this: 3 / \ 2 5 / / 1 4 Which tree dose not meet the conditions? I would appriciate it if you could answer my question!

I have a question of problem E.

If n=5, the tree can be like this:

3

  / \

 2   5

/ \

1 4

Also, it can be like this:

3

  / \

 2   5

/   /

1 4

Which tree dose not meet the conditions?

I would appriciate it if you could answer my question!

I got WA on Pretest 5 in A and the checker says wrong output format Expected integer, but "-0" found. What does this mean?

Casting the output to int gives AC. If the error was in output format, why did the first 4 pretests pass?

Link to code

One of the best D !

In problem D, how can one do binary search over a segment tree?

In problem D, what is the reason why repeat the numbers 3 times is enough?

In 1237F, I am facing difficulty in understanding the equation of number of ways to place exactly dh horizontal domino and dv vertical Domino. Can someone explain how we arrived at this equation: R⋅C⋅dh!⋅dv!.

Author’s solutions are good, but I know more interesting way to make this world better — checking M3139 homework ^_^

tourist Wonderful round, as always, but something about it clearly require further consideration. Maybe it’s homework of group m3139...

Very wonderful and complicated problems. But I know some more. For example, the problem of checking M3139 homework.

Amazing balanced problems. I think it's time to check M3139 homework 4more balance :3

Thanks a lot to MikeMirzayanov for Codeforces and Polygon, and also thanks to tourist for checking M3139 homework

An alternative approach for problem H: (a bit not elegant, but able to solve the problem in n operations)

First, check the number of 00s, 11s and 01/10s. Then, judge the situation where there're no 01/10s, which can be solved easily in n operations.

Consider we can do operations on both binary strings, as doing a sequence of operations on B is equivalent to doing the reverse of the sequence on A. And think about each time we make the last 2 characters of A and B equal and do the process on the prefix of length n — 2 of A and B.

Then, assume that at least one of the strings begins with 01 or 10.

Then, discuss about these cases:

1) One of the strings begins and ends with 00 or 11 while the other doesn't begin or end with 00 or 11.

In this case, we can modify the other string such that the end of the other string before the operation becomes the beginning of it. It begins with 01 or 10.

2) At least one of the strings ends with 00 or 11, except for case 1:

In this case, there's at least one string which begins with 01 or 10 and ends with 00 or 11. Modify the other string.

3) Neither of the strings ends with 00 or 11.

Consider string A neither begins with 00 nor 11. It's definitely possible to do operations on A such that its end equals to that of B. After the operation, A's end becomes A's beginning, which is 01 or 10.

Note that at first we need to modify the string so that at least one of A and B doesn't begin with 00 or 11. This takes 1 operation.

But we can find that when the length of A and B both becomes 2, we'll need only 1 operation at most.

So the total number of operations is n.

Is there any solution with a smaller number of operations? I wonder ...

can anyone explain the logic of j and k in question D?

can anybody explain ques B approach please

I was 100% sure that in D we need to use the fact that end of path is x/2. But this solution is general, the problem could be given as x-c, and path stops when you reach x-c. But I am glad I still got solution even though I was skeptical that I didnt use the fact x/2 at any point except that x/2 < x.

Hi,please down vote me

Can you make this solution to E any shorter? Maybe by using some other programming language?

ЛУЧШИЙ

O(n * log^2(n)) solution with Binary Search and Segment Tree is giving TLE. Can anyone help ? Submission: 83481373

I don't know why my program doesn't get this right. When the index of the car when exiting is larger than when it entered you count it. and make the index of all the cars that it overtaked less by 1.

This is my code:

include

include

include

include

using namespace std;

int main(){ int n; cin >> n; map <int,int> indexA, indexB; vector a, b; for (size_t i = 0; i < n; i++) { int xi; cin >> xi; a.push_back(xi); } for (size_t i = 0; i < n; i++) { int yi; cin >> yi; b.push_back(yi); } int cnt = 0; reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); for (size_t i = 0; i < n; i++) { indexA[a[i]] = i; indexB[b[i]] = i; } for (size_t k = 0; k < n; k++) { int i = a[k]; if(indexB[i] — indexA[i] > 0){ cnt++; for (int j = indexA[i]+1; j <= indexB[i]; j++) { indexA[a[j]]--; } } } cout << cnt << "\n"; return 0; } Can anybody help ?

https://mirror.codeforces.com/contest/1237/submission/274033759

Another way of problem B using two stacks , u can optimize it by using array instead of map for hashing