T

O

U

R

I

S

T

!

!

Press F for Um_nik

I bet they all sound to him like something of "what time is it?" difficulty.

Duh bro...... Every question is A or B for tourist xD!!!

Sounds as round will be semi-rated

And still you are unrated

Mike shinoda

Then hacked:-(

Mr. Radewoosh... I don't feel so good...

+124 feels like 'I am the one the one, who need no gun to have respect on the street' Huge respect Radewoosh :)

Maybe because they want less no of coders with their ratings fall ? :P

.... Wait a minute, who's gonna miss Tourist's round xD ?

Yes, why let more people to participate. Why would someone do that?

Yes, and after this, tourist might enter in Codeforces Top Contributors list as well :)

<3 <3 <3 <3 <3 <3

Sorry

It means that the difficulty of problems in this round perfectly matches its id.

You doesn't even spell it correctly. It should be "wonder"!

But the other writers are also very good!

All of them worked very well not only tourist

How can SuccessfulHackingAttempt and YaAAbu not be in the same round at the same time?

you just mentioned 11 people for a stolen yet terrible joke. good one mate

Same, I saw some other good comments got massive downvotes, I don't understand why there are so many random downvotes.

it's seem interesting with you but not everybody. you should comment something useful or amusing

Come on. Such comments only suit when immature kids like greens and greys post them. You are orange. Maintain some dignity

BREAKING NEWS

tourist tripled his practice after reading this

Contest length will be 2.5 hours, you can see it in contests page

Hoping for no DDOS, no stuck queue, correct statements, no bugs in test data.

I wrote to you in PM

Choose any point, and pair it with point that area will be minimised.

sort by x,y,z 1. first if two adjacent(in the sorted list) x,y are same then they can be pair 2. Once all with x,y equal pairs are done processing all adjacent pairs with same x can be pair 3. rest of adjacent two points can be pair

need to wait system test but I solved it this way, hope its correct

Are they both not the same thing?

ohh i thought it was max depth til now lol

Did you come up with something that can be solved by FFT?

I realized that was sum instead of max only after reading your comment.

I have some error and failed test 5. I don't understood what I did wrong. I wrote the stress, stressed some test with $$$n=50$$$, then remove some sorts which did nothing in the code, change some variable names and the second solution becomes correct. lol

I had WA6. I reduced the 3d problem to 2d problem (for each x), and then to 1d problem (for each y). Whenever I could not find a pair from the same vertical line, I was looking for a matching point in another vertical line in the same vertical plane, and then was deleting it. Then some lines did not contain any points, and I was still iterating through them, so that made a mess (=WA).

Well in my case I had 3 wrong submissions for pretest 5 .. but later on upsolved it.. What I did in my algo was first sorted the points on the basis of x and then y and then z. Then picked out pairs which are on the same line.. then on the same plane and then the remaining I failed pretest 5 because I didn't find the pair on same line correctly. What I did previously was that when in the sorted points list I found a pair I started searching for the next pair with first point ahead of the second point of the found pair. I changed it to first point should be ahead of the first point of the found pair and it worked! Hope it helps!

iterate through all b[i] reverse. keep a variable tmp and each time you iterate, update it to the smallest j such that a[j] corresponding to the b[i] has occured. Now for each b[i], it pays a fine if curresponding a[j] occured after tmp, else update tmp. (curresponding means the choosing j such that a[j]=b[i])

use two i,j indices for in and out arrays, then if in[i]!= out[j] remove out[j] element from in array and j++

otherwise i++,j++

while (y < n - 1) {
    if (in[x] != out[y]) {
      auto pos = find(in.begin() + x, in.end(), out[y]);
      in.erase(pos);
      ans++;
      y++;
    } else {
      y++;
      x++;
    }

My thought process during the contest went like this:

Let t[i] be the time the i-th car entered the tunnel.

So for instance: in[i]: 3 5 2 1 4

Then t[3] = 0, t[5] = 1, t[2] = 2, and so on..

Also keep the opposite array so you can determine which cars to fine, that is: inv[t[i]] = in[i]

When the cars leave the tunnel, if there are two cars j and i such that j < i but t[j] > t[i], then that means that even though j entered the tunnel after i, it left the tunnel before i, so in that case car j definitely surpassed car i and j must be fined.

Let's create a set s which will contain the entrance times of the cars that already left the tunnel.

Now let i be the i-th exiting car, for every car j that's already left the tunnel and hasn't been fined (so they are in s) such that t[j] > t[i], j must be fined and removed from the set (you can do that by using upper_bound).

Note this is $$$O(n\log{}n)$$$ because you insert and remove each element at most once.

But after the contest I realized you actually don't need that set! You can just keep the minimum entrance time :`), though at least to me this way of thinking was more natural.

.

.

<----

Not sure. Thought answer is 1 if $$$n$$$ is between $$$[2^i , 2^i + 2^i/2)$$$, otherwise 0. got $$$WA$$$ on test case 6.

I completed the code at the last moment but couldn't submit in time.

Here's my solution in short:

Perfectly balanced tree must have the condition that every level, except possible 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

1 can be used on the left, 2 can be used oh both sides

4 can be used on both sides, 5 can be used on the left

9 can be used on the left, 10 can be used on both sides

20 can be used on both sides, 21 can be used on the left

so

int solve(int x) {
	int cur[] = {1, 2};
	int st = 0;
	while(cur[1] < x) {
		if(st == 0) {
			cur[0] = 2 * cur[1];
		} else {
			cur[0] = 2 * cur[0] + 1;
		}
		cur[1] = cur[0] + 1;
		st = 1 - st;
	}
	return (x == cur[0] || x == cur[1]) ? 1 : 0;
}

Here is my solution — First for each element calculate the next number in direction of clock which is less than half of this value. Build minimum segtree over this values. Then iterate elements in non-decreasing order, you can use segtree to get the moves from i then set value at i to infinity.
Maybe there is not so coding solution.

I am not retard anymore, thanks man for the motivation

Same happened with me...finally submitted at last minute. And didn't got time to even read D,E,..

Agreed, C was much harder than DEF for me (at least if you include implementation)

Good to know I'm not alone xD

I thought there are more AC of C than D. Anyway how to solve F guys ?

For each point, select the closest one? $$$O(N^2)$$$, I think.

You can solve C1 in n^2, but not C2.