Interesting!!

Makes sense actually )))

So interesting（）

As a loyal PurpleCrayon Fan, PurpleCrayon orz.

Is it a trap? You can check soon :)

Are you a time traveller?

Hope you handle it well!

I know you can do it for Specialist, my friend...

Nice try

crap that didn't go well

She will be proud of you (for getting so much down vote) xD. Just a joke.

I guess problem D :P . Don't take it seriously. This is only my guess.

Sorry but why down-votes? I was just seeking to get help and improve.

man hope is not everything in this curse world. You should practice as much as you can. Then only you can stand apart from the crowd :).

hope too)

Not for you I guess

me too :) but cannot offer this one tomorrow :(

endl.

Typical interactive problem:

Div.2 C — 70% probability

Binary Search — 95% probability

You can get a birthday color :)

Div 1 is more difficult than Div 2.You can not participate in Div 1 if you have less rating than 1900.But you can participate div 2 and div 3 contest. And div 3 should be easier than the other divs. Hope you understand.

You can't join div.1 unless you have got 1900 Ratings. You are not Rated for div.2、div.1 when your Raing is higher than a number.

me struggling for cyan.

Thanks )))))

2 hours were probably for A only.

I completely disagree. There are too much bigger official participants comparing with participants from div1. Thus the last ones don't affect the competition too much, but their participations the most interesting, to be honest.

Registration:

Total: 17738

Contestants: 17502

Out of competition: 236

If those 236 persons didn't participate this will not make any change

good luck

And it was...

That is decided after contest seeing the number of people who solved it during the live contest. So u can't get that before the contest . :)

don't you dare give me some positive contribs. I just want to have negative contribs and live a happy life.

Nastia the little b*tch

You, are going down son

Just because you were not able to solve them early??

Bro Deep down we all know problem A and B are very good.

What was bad about them?

If anyone downvote me ,that is ok, i just want to express my feeling.

I don't think the problems were bad per se
But I don't like the steep cliff from B to C

I don't think it was a bad problem, but do agree that it was hella painful to think about. took me like a decade just to test my program on sample 1

For me it was:

• Lack of simple way to check implementation instead of writing test interactor (maybe I just didn't find one of course).
• min/max conditions was too far away of concrete samples. Scrolling up/down or rewrite to paper or open two tabs in one screen — neither of them is nice for me.

But problem itself was nice for me.

I agree, even tho i solved it, it felt very vague.

Thanks! Героям Слава)

I thought to divide by diameters and then join them. Do you think this is wrong?

wouldn’t then give you 0 on the first test?

Consider a graph with 6 nodes shaped like an H. There are two nodes of degree 3, so your answer will be 2. But you can get away with 1 by moving the middle line to the top.

I think I was able to come up till 2*n solution but not know what to do for 3*n / 2

in ~[n/2] queries we can find the position of 1 (or n) and then using this position we can find the rest of the numbers in n-1(or n-2, doesn't matter) queries

First try to find position of n in array using query 1. You can do this by checking adjacent pairs and if their result is n-1, check the swap as well. This takes atmost ceil(n/2) + 2 queries.

Using this position of n, you can easily find all values via query 2. This takes at most n-1 queries.

So total queries are well under the limit.

Use $$$t = 2$$$ and $$$x = 1$$$ to find $$$1$$$ in permutation for $$$n / 2 + few$$$ queries (if $$$p_i == 1$$$ then answer is $$$1$$$);
Use $$$t = 1$$$ and $$$x = n - 1$$$ to find other numbers in permutation for $$$n - 1$$$ queries (if $$$p_i == 1$$$ then answer is $$$p_j$$$).

? t i j x Important observation: t=1 and x=n-1 max(min(n-1,Pi),min(n,Pj)) equals — n-1 if Pi=n — max(Pi,Pj) otherwise

t=2 and x=1 min(max(1,Pi),max(2,Pj)) equals — 2 if Pj=1 — min(Pi,Pj) otherwise if anyhow by using t=1 and x=n-1 we get the position of n in the permutation in <= (n/2)+30 queries , we can get remaining elements by using t=2 and x=1 in n-1 queries we can get the remaining elements in n-1 more queries.

How to get the index of n ?? we can see that for (i,j) t=1 and x=n-1 the output can be n only when Pj=n if output is n-1 Pi can be n we can check take (i,j) like this ( 1 2 ) ( 3 4 ) ( 5 6 ) . . . if the output during any stages is n we get index_of_n otherwise we get a set of possible values of index_of_n (corresponding to output n-1,with max 2 possibilites)

so we can check the index of n in max (n/2) + 2 queries after that our job is done

Pretests are cases that will be tested during the contest. Not all of them will be visible to you. And there will be more tests following in the system test phase after the contest.

Check out this: https://codeforces.me/blog/entry/4088

Don't be sad! Good luck on the next contest! You will comeback

you can find the maximum of the permutation in about n/2 moves with t = 1, x = n-1, changing i and j every time. If you get the result n, j is the position of the max. If you ever find an n-1, try for j and i. If then you get the result n, that means i is the position of the max.

And then using the maximum you can use t = 2, x = 1 to find each element in n moves.

Indices are have to be different. I wasted 30 mins implementing this then noticed the statement.

My not so interesting solution.

Asking queries of type 1 with $$$x=n-1$$$ will give you the maximum value among two positions asked. If the answer to the query is $$$n-1$$$, just ask the same two position again with $$$n-1$$$ value and take the greater answer of the two queries asked.

Same thing with min and queries of type 2.

After you get the maximum and the minimum, one query of type one for two position with value equals to $$$minValue$$$ (found above) will tell you which of them is the larger and which is the smaller.

I took 12 queries to figure out exactly what the first three elements are.

Then I query every other element (of index idx) with the largest known element (of index maxidx)

• First I use a type 2 query that works if the other element is smaller t=2, i=idx, j=maxidx, x=1
• If the other element is larger, I follow up with a type 1 query t=1, i=maxidx, j=idx, x=n-1

I update the largest known element along the way.

The worst case is still 2n. To avoid the worst case, I shuffle the remaining queries.

I had exactly this solution: 115619047

To find the value of the first element I used binary search:
After checking different values of $$$x$$$, I relaized that the query of type $$$1$$$ returns $$$x+1$$$ if and only if $$$x \leq p_j$$$. And it doesn't even matter what the value of $$$p_i$$$ is. This allows us to do binary search on $$$x$$$ to find the value of $$$p_1$$$, by doing queries like $$$(t=1, i=2, j=1, x=mid)$$$, where $$$mid$$$ comes from our binary search.

After we found the value of $$$p_1$$$, we can find the value of every other element in at most 2 queries. But in the worst case it might be exactly 2 queries per element, e.g. if the permutation is sorted in reverse. That's why I shuffled the indices, hoping that it will take 1.5 queries on average.

ya I am thinking the same, like partition tree into a minimum number of line graphs and then join those graphs, it can be done in O(n) I think, but couldn't implement

how? please give me some example

Sometimes the things which appear to be so obvious also turn out to be wrong.

Yaaa, I exploited the same and used a segmented sieve to calculate primes from $$$1e9$$$ to $$$1e9 + 1e7$$$, and turned each number into a prime other than the smallest one.

I feel Pepega right now.

Oh shit!!! I didn't notice. Will take care next time...

realized that except the minimum element all elements can be changed to any other so simply swapped the first and minimum element and did a[i]=a[i-1]+1 for all i bw [1,n-1]

I approached another simple solution . As all the consecutive pair of integers are co-prime so just find the minimum element and its index from the array. Then change all the elements according to this order. Suppose the array isa[]={9, 6, 3, 5, 11} minimum element is 3 so change the array into a[]={5, 4, 3, 4, 5} That means make the elements increasing order from the minimum index to left and right.

Exactly!!! I also tried the same approach but I made a stupid implementation mistake :/, got RE instead. :(

1 2
1 3
1 4
1 5
5 6
5 7
5 8

Dia is 2 — 1 — 5 — 7 but ideally 1 — 5 should be removed