As a free-riding tester, give me contribution.

As a tester, video editorials for some problems will be available on my channel after the contest.

As a tester,

Same as above comment.

As a co-author, please give me contribution!

As a tester, this is my first testing round! Good luck guys!

As a tester I forgor to test 💀

As a tester, I can't think of anything funny to put here.

two-four-five particle

Unusual time with least deviation.

Time To Tourist To Go To First Pos AGain

As a downsolver, I can confirm that authors put a lot of work into this round and I hope you enjoy it.

Sadly the round will not be Easter themed :(

Please add more contests.

culver0412 orz

As a non tester，I will also enjoy this round：）

As a non-tester, I will enjoy easter :)

As a tester, I am not a tester.

why only 1900+

Happy Easter, Codeforces! Sadly the round will not be Easter themed :( (in White) , Excited for the Contest

As a non-tester, I want to be a tester.

As a non-tester,i want to ask how can i become a tester one day

Well i am more excited to watch tourist Vs jiangly, this time.

what kind of question is the first one

Huge separation between C and D today in pure Div 2 lol

Tourist The King ! Again on top

most stupid div2 contest ever, B and C are both some quasy patterns with no proof of why it should ever work other than that it is a pattern that could apply in codeforces contest

I like interactive problems but this was extremely hard to understand

DID YOU ALL NOTICE?? There is a highlighted text while selecting the first line of the blog... "Happy Easter Codeforces" one, extend it further from left to right!!

Spent about 1 hr on div2D and finally figure it out but couldn't implement it in time.

Congratulations to YocyCraft for becoming GM after this round, assuming you pass system tests!

Thanks for an amazing contest! Solved D1A, B and C, got 160th and +107 delta according to carrot. Definitely my best performance ever. I really loved the style of problems and statements were clear and consise, straight to the point with no unnescessary stories. I would honestly love to see more contests from you as soon as possible!

What was Test 2 in Div1-C ?

D1C is overwhelming, and D1D is also nice! Thanks for the great round!
Sorry I got FST on D with $$$m=1$$$, so sad

Div1 B

https://codeforces.net/contest/1815/submission/201562137

This submission get WA on test1, but why?

I tested it by myself, the result was allright.

Guys, is Div2 C binary search?

A,B,C problems were good enough....But, hardness(D-C)=inf...

What was the intended solution for div2A? I couldn't think of anything and figured brute force would probably result in around sqrt(n) complexity by brute forcing until I find an I such that gcd(x-1, abs(y-i)) = 1. This ended up working for me.

mesosan orz

Can anyone tell the idea behind the problem C.

D problem ORZ

Problem C from Div. 2 is somewhat similar to Drought from the USACO 2022 January contest.

how to solve div2A?

Div 2 F :skull:

Solution for Div1B:

• Do $$$"+ n","+ (n+1)"$$$,you'll get a chain.

• Do $$$"?1,i"(2 \leq i \leq n)$$$,you'll get a endpoint $$$e$$$ of this chain.

• Do $$$"?e,i"(1\leq i \leq n ,i \neq e)$$$.Sorted by distance, we get the entire permutation.

Is this logic incorrect for D1C: Firstly all vertices should be reachable from 1 in the graph with reversed edges, else the number of sequences are infinite. Then I find out SCCs. The SCC containing '1' has a sequence: [s2,s3,..sk] + [1] + [s2,s3,..sk]. Then in topological order we build other sequence for other SCCs.

I did A,B,C pretty easily. But in D what was that permutation about, we had to guess it but what that permutation really meant ?

Even after spending 30 mins I couldn't understand the permutation. Please explain.

Interaction details are very annoying... missed the problem due to that :d... input 1 if it is correct or -2 if it is not... did you really need to do that?

In case anyone's wondering, the "hack" in Div1D is not taking modulo when printing the answer for $$$m = 1$$$.

That's pretty silly. There was an OpenCup contest around 2018 from Red Panda where "output something modulo $$$M$$$" was defined as "you may print any number that is congruent to the answer modulo $$$M$$$".

I think that should become the standard. Add some extra helper functions to testlib.h and it wouldn't be very hard to do that way in every contest.

How to solve Div-2C today's contest?

The format of interactive problems is very bad. You get random verdicts and notes from checker and can't understand, what you did incorrectly. I spent 50 minutes to submit already correct solution, which did queries incorrectly. And for "Is it possible to get for all queries non-negative answers, but get WA for test?", the answer is not "No comments", but "Yes, it's possible" (if you print not permutation at ! operation).

The problem $$$B$$$ is nice though. Notice, that you can create a bamboo (or spagetti?) in three moves. Then using $$$n - 1$$$ moves find one of its ends. But you can't understand, which one you found, so track both cases. Then in $$$n - 2$$$ find $$$n - 2$$$ other numbers of permutation. You have no query to find last one, so do it manually.

still sad for the last edu codeforces which is unrated
i should earn 100+rate on that round
and even 20 rate will surely make me CM this time

Solution for Div1C:

Define finite number:

• $$$1$$$ is finite number;

• if $$$v$$$ is a finite number and $$$(u,v)$$$ exists,$$$u$$$ is also a finite number.

We have discovered a directed graph. Starting from $$$1$$$ for BFS, if there is a number that is not finite, no solution.

We also note $$$dis[i]$$$ as the shortest distance from point $$$1$$$ to $$$i$$$.

Obviously,for all $$$i$$$ that $$$dis[i]==1$$$,There can be at most $$$2$$$ numbers in the sequence.

Similarly,or all $$$i$$$ that $$$dis[i]==x$$$,There can be at most $$$x+1$$$ numbers in the sequence.

Construction:A bit complex. I implemented it using a linked list.

I guessed all the questions I solved today :clown:

Div 2. A, B had good samples so no penalties
Died in C penalties ;-;

can someone explain the logic behind B? I just saw a random pattern in testcases and printed it.

Can someone give a formal proof along with the method for B. I was clueless about how to approach this question. Thanks

can anyone give some idea related to div2b

Can anybody give me a test case for div2 C where my solutions is failing. Thanks.

Submission = link

The main code is as follows:

def solve(n, array):
    for i in range(1, n):
        if array[i] < array[i - 1]:
            if i + 1 < n:
                diff = array[i - 1] - array[i]
                array[i + 1] += diff
                array[i] += diff
            else:
                print("NO")
                return
        diff = array[i-1] + maximum
        array[i-1] -= diff
        array[i] -= diff
 
    print("YES")

For div2F/1D, sequence for m = 2 is available here. https://oeis.org/A328565. (m != 2 is trivial)

We can get the nth term (a direct formula isn't specified) using the structure in https://oeis.org/A328565/a328565.png, which says if a given xor y can be achieved given n. Now we can form a recursive equation to get answer for a big n.

Div2 D is totally a disaster it's far harder than C(even harder than E,i think)

abcforces

Solved Div1 A-C. Give me >=51 delta plz.

D1A/D2C: Let d[0]=0, d[n]=0, and d[i]= how many times we do operation on pair (i, i+1) (decreasing is regard as -1 operation), then we have a[i]+d[i-1]+d[i]<=a[i+1]+d[i]+d[i+1], which means d[i+1]>=d[i-1]+(a[i]-a[i+1]), so we have an inequallity system. If n is odd, this inequallity has a solution, but if n is even, we have 0=d[n]>=d[n-2]+(a[n-1]-a[n])>=d[n-4]+(a[n-1]-a[n])+(a[n-3]-a[n-2])>=...>=d[0]+(the alternative sum of a)=(the alternative sum of a), so we need to check whether the alternative sum of a is non-positive.

D1B/D2D: If we add edge for x=n and x=n+1, the graph will become a path: n --> 1 --> n-1 --> 2 --> n-2 --> 3 --> ..., so we can query (1, i) for 2<=i<=n to get the furthest point from p[1], and it must be one of the endpoint of this path. Let j be the furthest point then we can query (i, j) for 1<=i<=n, i!=j and we can get the order of p[i] on this path. The answer will be this order or its reverse order.

D1C/D2E: Let's build a directed graph with node numbered 1...n, and add an edge (b-->a) for each pair (a, b). Note If there's any number cannot be reached from 1, we can build an infinite sequence: Let c[1], c[2], ..., c[r] be the set of numbers cannot be reached from 1, the infinite repetation of (c[1], c[2], ..., c[r]) will be a valid answer. Otherwise, we can group numbers by the distance from 1. If the maximum distance from 1 is k, and we denote the list of i-dist numbers as L[i], we can build a sequence as L[k], L[k-1], ..., L[0], L[k], L[k-1], ..., L[1], L[k], L[k-1], ..., L[2], L[k], L[k-1], ..., L[3], ..., L[k], L[k-1], L[k-2], L[k], L[k-1], L[k]. We can see for any pair of same numbers with distance i, there are occurences of all numbers with distance >=i-1 (except itself) between them, and by the defination of distance, for any pair of (a, b), because there's an edge (b-->a), we have dist[b]>=dist[a]-1, so this is the valid answer. And we can see that each number with distance k can have at most k+1 occurence in any valid sequence (that's because between k+2 numbers of distance k there are at least k+1 numbers of distance k-1, k numbers of distance k-2, ... , 2 numbers of distance 0, but the only number with distance 0 is 1, that's a contradiction), so this is an optimal answer.

when is the next contest MikeMirzayanov sir?

There may be an alternative solution for Div1B to get a unique permutation using $$$\approx 1.5n$$$ queries for sufficiently large $$$n$$$.

• First, + n and + (n - 1) to get the vertices $$$1, 2, \ldots, n - 1$$$ connected like a chain. This takes $$$2$$$ queries.

• Then, we would like to find $$$x$$$ so that $$$p_x = n$$$, the isolated vertex, in this part. To do so, we may take any two indices $$$i, j$$$ and ask ? i j, if the response is non-negative, eliminate both of them from the candidate list; otherwise, exactly one of $$${p_i, p_j}$$$ must be $$$n$$$. We can find which it is by just asking ? i k with any $$$k \neq j$$$. This takes up to $$$\left\lfloor \dfrac{n}{2} \right\rfloor + 1$$$ queries.

• Do + (2n - 1) so that vertex $$$n$$$ is connected to vertex $$$n - 1$$$. Now, the graph forms a chain. This step takes $$$1$$$ query.

• By asking ? x z, $$$\forall z = 1, 2, 3, \ldots, n$$$, the permutation can be uniquely determined since each response is distinct. This takes $$$n$$$ steps.

Directly implementing this solution would fail for $$$n \leq 6$$$. But as you can see, there are many apparently redundant queries in some steps.

For problem D1B/D2D's interaction format, our intent was to prevent unexpected verdicts caused by wrong output format or exceeding number of operations, since we can tell the contestant to terminate the program and receive Wrong Answer.

However, some issues arised, such as some contestants forgetting to read the integer $$$1$$$ or $$$-2$$$ depending on whether the answer is correct. If they didn't read it, they are effectively solving the next query with $$$n=1$$$ which causes some errors unexpected by the contestants. Although the statement was bolded in the statement, it turned out that it was still not too obvious for everyone :(

Lots of contestants asked about self-loops. We did not expect that confusion, since the distance from a node to itself is always $$$0$$$, but we should have explained that clearer in the statement. Sorry about that.

Other than the somewhat complicated interaction format and unclear details, I hope you still enjoyed the problems.

Good problems especially problem D!

Div2 D (Div1 B) is a little vaguely worded. It did not explain the case for query ? i i. I thought this would return 0 iff there is a self-cycle from i to i (and -1 otherwise). So I constructed an algorithm that should be similar to the correct solution:

1. if n == 2, "! 1 2 2 1", otherwise:
2. query "+ 2". now there is a self-cycle from 1 to 1.
3. query "? 1 1" ... "? n n" to get the position of 1.
4. query "+ n+1" and "+ n+2" to make a linked list
5. we have n-3 queries remaining. query "? pos_of_1 i", i != 1. This would determine the position of all but 2 numbers. Thus we have two candidate permutations.

I should have used the question feature, didn't think about that. The reality is "? i i" always returns 0. This is very confusing because in the example, n=6 and there was a query "+ 12". So this query is entirely useless, and potentially misleading (I thought self-cycles are useful). I tried 11 submission with different throw() to test out what went wrong. After I finally found out I didn't even want to code anymore. Very frustrating for me.

P.S. Other than this, great contest! Lots of constructive algorithms.

For some reason didn't enjoy neither of ABC =(. Maybe simple observation/construction problems aren't to my taste. But most probably the reason is I am just bad at math

Today D was much harder then regular D

Problems were very cool authors! I really enjoyed D1B-D1D.

Although I'd say B > C > D in terms of difficulty personally and seems I would've FST on the D hack if I did finish it in time which is unfortunate for those that did.

Great job overall still, hope to see more from you guys in the future!

201512259 Can someone please tell why it failed on Problem A ??

I am new to the website. I participated in this contest in Div 2, with account rating of 540, and it looks like it is unrated for me. Why ? Please explain to me

How do you rigorously solve Div 2 B? I was able to intuitively guess the correct pattern, but couldn't prove that it was optimal.

Just realized my code in problem C wasn't passing because of a int oveflow fml

What is the logic behind div2 C. I am completely blank on this one. I've seen some solutions which use left to right traversal and right to left traversal. But m not sure how to prove it. Can someone give a solid solution. Thanks UPD: Got it! thanks for the replies

Auto comment: topic has been updated by culver0412 (previous revision, new revision, compare).

which div2 was tougher in your opinion ?

from last two.

Can someone please explain proof of B in editorial in more detail?

In particular, I would like to know what does it mean lowerbound for maximum cost and how do we, from the observations in proof before that, conclude that this is the value of the lowerbound.

In task we need to construct the grid such that minimum cost over all paths is maximized. So I think in order to prove that some construction satisfies the requirements we need to find value C(n) such that for every placement of integers on the grid minimum cost among all paths in the grid is <= C(n). Then we need to show that for our construction minimal cost equals C(n). Am I wrong?

No more contests in the coming week?

I'm struggling to understand Div2D's example. How does [1 2 3 4 5 6] comply with the query about $$$p_1$$$ and $$$p_3$$$? The distance between nodes 1 and 3 is 2 in the graph at that time.