culver0412's blog

By culver0412, 6 months ago, In English

Happy Easter, Codeforces! Sadly the round will not be Easter themed :(

We (arvindf232, culver0412, dbsic211, happy.potato, jerryliuhkg) are delighted to invite you to participate in Codeforces Round 865 (Div. 1) and Codeforces Round 865 (Div. 2), which will take place on Apr/09/2023 17:45 (Moscow time). Participants with a rating lower than 1900 will participate in Division 2, while participants with a rating of at least 1900 will participate in Division 1. Notice the unusual starting time.

All the problems were authored and prepared by arvindf232, culver0412, dbsic211 and happy.potato. Huge thanks to the following people, without whom the round would not be possible:

In both divisions, you will have 2 hours and 15 minutes to solve 6 problems. One of the problems is interactive, please see the guide of interactive problems if you are not familiar with it.

Wish you good luck and high ratings!

UPD1: Score distribution is as follows:

  • Div. 1: 500-1250-1750-2500-3000-3500
  • Div. 2: 500-1000-1250-2000-2500-3250

UPD2: Editorial

UPD3: Congratulations to the winners!

First solves
  • Vote: I like it
  • +408
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +53 Vote: I do not like it

As a free-riding tester, give me contribution.

»
6 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +21 Vote: I do not like it

As a tester,

»
6 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Same as above comment.

»
6 months ago, # |
  Vote: I like it +108 Vote: I do not like it

As a co-author, please give me contribution!

»
6 months ago, # |
  Vote: I like it +21 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +70 Vote: I do not like it

As a tester I forgor to test 💀

»
6 months ago, # |
  Vote: I like it +72 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

two-four-five particle

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Unusual time with least deviation.

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Time To Tourist To Go To First Pos AGain

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it -19 Vote: I do not like it

    You're right. But I hope jiangly's rating can exceed 4000 as soon as possible!

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Is it possible to reach 4000 if one get 1st in div1 everytime?

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        Rank 1 performance in div 1 is higher than 4000, so yes it is possible!

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Wait, you really can somehow lose rating if winning div1??

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it +13 Vote: I do not like it

            If I remember correctly there was a round where in the middle tourist ranked first, tied with another user, and tourist's delta was shown as negative.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        When i click to register div1 codeforces gives this "Rating should be between 1900 and 9999 in order to register for the contest XD.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          What all Think if jiangly reaches 4000 does some new name comes or or something cool happens kind of international legendary grandmaster

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    it will be very interesting to watch tourist vs jiangly. Jiangly just bashed atcoder today in 25 mins which is around the time tourist does it usually.

»
6 months ago, # |
  Vote: I like it +120 Vote: I do not like it

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

Downsolver joke
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    As a participant, I will appreciate the work of authors and testers. Thank you for the contest!

»
6 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Sadly the round will not be Easter themed :(

»
6 months ago, # |
  Vote: I like it -11 Vote: I do not like it

hope this contest will be fun!..

»
6 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Please add more contests.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
6 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

As a non tester,I will also enjoy this round:)

»
6 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +16 Vote: I do not like it
Spoiler
»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

As a tester, I am not a tester.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This month already 4 contests happened. What's about for the rest of the month

»
6 months ago, # |
  Vote: I like it -10 Vote: I do not like it

why only 1900+

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Since your rating is lower than 1900, you are in Division 2.

»
6 months ago, # |
  Vote: I like it -19 Vote: I do not like it

↑ caused by playing Genshin Impact

»
6 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i still remeber the last edu codeforces,which unr because of test mistake

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    I will just copypaste my comment from a recent blog:

    If you are a tester, most likely, you are invited by one of the authors. So do you know any round authors? If you don't, there is an alternative solution: be a round author yourself! Some coordinators and authors will invite authors of previous rounds as testers.

»
6 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi ! My friend is unable to access her ID as she had registered with her gmail account, but is unable to log back into the ID due to an "invalid request" from codeforces's end. Kindly resolve this issue as soon as possible, she is missing out on a lot of contests. Her ID is gd2326848

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what kind of question is the first one

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it -17 Vote: I do not like it

    -

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      yes bro , if they highlighted the lattice points it would have been better to understand lol

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      It's a Greedy question, if you don't want to touch any unnecessary points, go to (1, b-1) or (a-1, 1), after that, go to (a, b), if a == 1 == b go to (a, b) with one step.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How did you figure that the first step should be (1, b-1) or (a-1,1)? Did you apply some formula or just trial and error?

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          the case (3, 6) show me, because I can always make an L using a maximum of 2 steps

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Not that you asked me but I might give my 2 cents. I tried to imagine different ways to solve some queries, and I just got the idea to try and make the lines go as close to a rectangle as possible.

»
6 months ago, # |
  Vote: I like it +41 Vote: I do not like it

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

37e63674d34a1a5bb35d01d2bf4ddb2e2463ea7c

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

First time I did A, B and C during a Div. 2 contest. Now I can just pray that they all pass sys tests :D

»
6 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Tourist The King ! Again on top

»
6 months ago, # |
  Vote: I like it -44 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I think C was a little pretty, I didn't like B though.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Both are provable

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Agree about B, but C can be solved with a simple greedy algorithm which can be easily proved.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to proove it pls

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        write final vector as an initial vector plus some vector from space spanned by vectors of form $$$(0, .., 0, 1, 1, 0, .., 0)$$$ (two consecutive ones somewhere). Then you can write out constraints on the coefficients, notice that if $$$n$$$ is odd you can find such coefficients always, and if it's even you can check in linear time if these constraints are satisfiable with the given $$$a$$$ vector.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yes , c is easiler than a and b

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I like interactive problems but this was extremely hard to understand

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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!!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +59 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What was Test 2 in Div1-C ?

»
6 months ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

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

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Div1 B

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

This submission get WA on test1, but why?

I tested it by myself, the result was allright.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I tried testing your code manually, and this is what I got, perhaps there was some miscalucalcution in answering the queries as per the interaction, the same happened with me before and it was frustating :')

    Test Case 1
»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Guys, is Div2 C binary search?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    No, at least I don't see it

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I felt like it. Cuz when I debug with all values in a range, it was monotonic. Was it not?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Then how to do C?

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +4 Vote: I do not like it

      I just did two iterations over the initial array.

      In the first iteration we check if a[i] > a[i+1]. If that is the case then we increment both a[i+1] and a[i+2] until a[i] = a[i+1].

      For the second iteration we go from behind and check if a[i] < a[i-1]. If that is the case then we decrement both a[i-1] and a[i-2] until a[i] = a[i-1].

      If the array we get is non-decreasing, the answer is YES, otherwise NO.

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    No, given an array (2, 1, 4, 3) for example, take the sum of "even" subarrays of size 2, or subarrays that start on an even index number. (2, 1, 4, 3)'s even subarrays are (2, 1) and (4, 3). Subtract right element from the left and if the sum of all the even subarrays numbers are <0 it cannot be transformed, otherwise it can. (2, 1) = -1, (4, 3) = -1, -1-1 = -2, this is impossible. This is not the complete answer but an important concept, find out the other part on your own given this!

»
6 months ago, # |
  Vote: I like it -9 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    Probably something like $$$(0, 0) \rightarrow (1, b-1) \rightarrow (a, b)$$$ (I can't be bothered to think if there are any edge cases to this)

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Just realized that's why my solution passed so quickly, my loop started at 1 which was always an answer lol.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    it can be solved O(1) TC...exmple, two points are: (a-1,1) (a,b)...

»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

ABCForces XD. D is too hard for me now.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell the idea behind the problem C.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    if n is odd then answer always exist...otherwise carefully notice that you can just transfer value from even pos to even pos and odd pos to odd pos...so compare between sum of even pos ans odd pos...

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Let b(i) be a number added to a(i) and a(i+1)

    Then you can find equations of b(i)s from the non-decreasing condition

    if n is even

    a(2)-a(1)+a(4)-a(3)+...+a(n)-a(n-1)>=0

    if n is odd

    No condition

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      How to become better at these type of problems.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Detail solution to Problem C: Link

»
6 months ago, # |
  Vote: I like it +7 Vote: I do not like it

D problem ORZ

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester, I was sleeping during the test.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

how to solve div2A?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    move to (a-1,1) then move to (a,b)

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    If the gcd of (x2 — x1,y2 — y1) does not equal 1 (x1=0, x2=0) then there will be a lattice point in the segment so in order to fix this you fisrt need to jump to a point such that the the gcd of (x2 — x1,y2 — y1) becomes 1, you can do this in many ways, one of which jump to (1, y2 — 1) first then to (x2, y2)

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    10 wrong submissions 💀 💀

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Div 2 F :skull:

»
6 months ago, # |
  Vote: I like it +34 Vote: I do not like it

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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 months ago, # |
  Vote: I like it -9 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    do + n and + (n+1), you can get a chain. then it's much easier to get relative order of nodes on the chain

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The permutation just exists. It doesn't affect the construction of anything else. The only way to get information about the permutation is by doing type $$$2$$$ queries. The permutation exists as a mapping of integers to other integers (nodes) when doing type $$$2$$$ queries and you need to figure out what that mapping is.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohk, now it's clear to me. This really make me mad -_-

      thnx a lot

»
6 months ago, # |
  Vote: I like it +45 Vote: I do not like it

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?

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it
If you thought jiangly would do better than tourist
»
6 months ago, # |
  Vote: I like it +129 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    I totally agreed with this. I would be pissed if my entire solution failed because of such case. Feel bad for the guys I hacked because they couldn't fix their codes in time :(

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    If the array is already sorted , we’re done and answer is yes. If the array size is odd the answer is always yes ,proof: we can make the first n — 1 elements equal to the first element by applying operations on every two adjacent elements a[i] and a[i + 1] for 1 <= i < n — 1. We will have x x x x .. x x y where the number of x's is (n — 1) which is even , since have even number of x’s we can decrease all of them if they are greater than y by dividing them into pairs and applying the operation on each pair.

    If the size is even We will do the same and try to make the first n — 1 element equal by doing the same work above , but then we will have odd number of x’s so we cannot decrease them , the only possible way for the answer to exist is if y >= x.

    My Solution
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    You can create bamboo even in two moves. add(n) and add(n+1)

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As Mr.Greedy I really overthink ABC T^T

»
6 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I messed up on this problem because I assumed that cycles would lead to an infinite series.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Easy construction:

    Let $$$max_{d}$$$ equal the maximum value of $$$dis[i]$$$

    The answer sequence is as follows:

    $$$[[max_d], [max_d-1], \dots, [2], [1], [0],$$$

    $$$[max_d], [max_d-1], \dots, [2], [1],$$$

    $$$[max_d], [max_d-1], \dots, [2],$$$

    $$$\dots$$$

    $$$[max_d], [max_d-1],$$$

    $$$[max_d]]$$$

    where $$$[n]$$$ gets replaced by a sequence containing one of every integer $$$i$$$: $$$dis[i] = n$$$

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Construction: Let $$$S_i$$$ denote the sequence of points at distance $$$i$$$ from $$$1$$$, ordered arbitrarily. Let $$$K$$$ be the largest distance any point has from $$$1$$$. Then the following construction works:

    $$$(S_K + S_{K-1} + S_{K-2} + \cdots + S_{0}) + (S_K + S_{K-1} + \cdots + S_{1}) + \cdots + (S_{K} + S_{K-1}) + (S_{K})$$$

    $$$+$$$ denotes sequence concatenation

»
6 months ago, # |
  Vote: I like it +7 Vote: I do not like it

I guessed all the questions I solved today :clown:

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    :clown: I was in the first 60 solves for C and had 0 penalties then took 2h for A and B with 4 penalties

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was in the top 300 after solving A and B and then couldn't solve C :)

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you think that's bad, realized after the round that my code for C wasn't passing because of a int overflow :(

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You always start at (1, 1), so it's added and it should be maximum possible. Note also, that you when you end at (2, $$$n$$$) you add that number too, since $$$n$$$ is even, so it should be second biggest number.

    Now, when you start at (1, 1), you go either right or down, and both these values are on minus, so we should minimize them, so put at (1, 2) and (2, 1) 1 and 2 respectively. Now, when you are in either of those cells you can go to (2, 2) or (1, 3) where you maximise. Then you will end up in either (2, 3) or (1, 4), which you minimize, and this goes on and on.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    I haven't proven it but consider these observations.

    There are some squares that contribute positively to the sum, and some that contribute negatively. These different types of squares form a checker pattern.

    For each of the squares that contribute positively that are in the top row, we can go to two squares that contribute negatively, either the square under it or the square that is to the right.

    Since we want to maximize the minimum sum, it would be a good idea to get as little fluctuation in the different answers we can possibly get in the end (again, this is not a proof just observations), so we should put two consecutive numbers in those two negative squares so that if we choose either of them, the difference in the sum they make is at most equal to 1.

    So we want to put the biggest half of the numbers (from n+1 to 2*n inclusive) in the positive squares, and the smallest half (from 1 to n inclusive) in the negative squares.

    The last thing is that we should put the biggest two numbers at the positions (1, 1) and (2, n). This is because we want the biggest numbers to be included in every single path possible.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone give some idea related to div2b

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The blue cells will be the positive integers so you need to maximize the integers in the blue cells in a certain order

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to approach problems which are similar to C? Can you please suggest some more problems like C?

»
6 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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")
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try this test case 1 7 1 1000000000 1 100000000 1 1000000000 1

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thank you so much. I was still trying to figure it out.

»
6 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +12 Vote: I do not like it

abcforces

»
6 months ago, # |
Rev. 6   Vote: I like it +56 Vote: I do not like it

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.

»
6 months ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

when is the next contest MikeMirzayanov sir?

»
6 months ago, # |
Rev. 4   Vote: I like it +97 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My idea was similar with $$$n + \lfloor \frac{n}{2} \rfloor + 2$$$ queries total.

    It also gets AC(201561852) but need some optimizations.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great, that's an interesting idea! I think some co-author / tester mentioned the existence of a $$$1.5n$$$ solution during the round preparation. Maybe the problem could have been split into an easy and hard version, but it seems like the current version is difficult enough.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This idea has been linked in the official editorial as the "harder version". Thank you!

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    sorry for necroposting , but I didnt get why would your approach fail for n <= 6 like for n = 5 you would first update 5 and 4 , so right now graph is smthng like 4 — 1 — 3 — 2 5 in worst case it would take us 2 queries to figure out the isolated vertex and we would need one more to connect 5 with 4 (query : 9) till now we used 5 interactions , after these we can use 3 more queries to find the position of each index

    so why would 8 queries fail ? ( ok Im stupid for n = 5 it took 9 queries , ig as n gets smaller we will get higher interaction numbers )

»
6 months ago, # |
Rev. 2   Vote: I like it +68 Vote: I do not like it

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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good problems especially problem D!

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    If you have any problems regarding the statement, you can use the ask a question feature. A lot of the questions asked are regarding the ? i i case, we think that it might have been confusing to most of the contestants.

    Hope you still enjoyed the other problems!

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I never used that before so didn't think about it. Will make sure to do it next time.

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In Div1 legend show their rank

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I agree. I barely managed to solve them because I kept tripping up on them. :/

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Today D was much harder then regular D

»
6 months ago, # |
  Vote: I like it +21 Vote: I do not like it

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!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    For test case:

    1
    6 8
    

    it gives

    1
    6 8
    

    which is wrong since the line joining (0,0) and (6,8) also has other integer co-ordinates lying on it. For example, (3,4).

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone recommend some good pattern problems similar to div2b?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You're not alone... I also noticed the solution but I'm not sure, and I searched for evidence that led to nothing.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The rating updates of round 864 were too fast, but for this round, what will happen?

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
Rev. 2   Vote: I like it -33 Vote: I do not like it

After getting so many downfalls, In today's contest tourist to jiangly:- let me show you who is the real boss!!!!!!

»
6 months ago, # |
Rev. 2   Vote: I like it -51 Vote: I do not like it

In today's contest tourist to jiangly:- "buddy aapke father aaye hai"

»
6 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    My approach If you tried to see there are two cases for n even and n odd.. for n is odd it is always possible to make array sorted, you can try every different possible case for n is odd. I have not proved it but by intution, I can say I have one extra element when n is odd which is helping to sort the array every time.

    I just implemented for second case.

    for n even what i did, I just simply traversed an array an start making it sorted by doing the operations given, If at end i got sorted array then yes, othewise no. let see how I did if array is [3,2,5,4]. what I did I first convert first element two 1; [1,0,5,4] by subtracting 2 from first element and second element.

    [1,2,7,4] by increasing 2 to second and third element.

    [1,2,3,0] by subtracting 2 from third and fourth element.

    Now I am at index 2,I can't perform any operation further. I can't increase 0 by any means, I just checked is it sorted or not.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For N=odd, the idea is that if you have a bad index i where A[i] < A[i — 1], then if i is odd, A[1:i-1] has have even length, and you can decrease these values pairwise until A[i-1]=A[i]. Otherwise, i is even, and A[i:N] has even length, so you can increase A[i:N] to achieve the same result.

      Example:

      A = [2, 2, 1, 1, 1] → [1, 1, 1, 1, 1] (bad index i=3, so decrease A[1:2])
      
      A = [2, 2, 2, 1, 1] → [2, 2, 2, 2, 2] (bad index i=4, so increase A[4:5])

      This way, you can remove any bad index without introducing any new ones.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can reformulate the problem in the following way :

    given an array of $$$n$$$ integers $$$a_1 , a_2 ,.. , a_n$$$

    check if there exist some array of numbers $$$k_0, k_1 , ... , k_{n}$$$ such that the array:

    $$$a_1 + k_1 , a_2 + k_1 + k_2 , ... ,a_{n-1} + k_{n-2} + k_{n-1} , a_n + k_{n-1}$$$ is sorted in non-decreasing order.

    That means that : $$$a_1 + k_1 \le a_2 + k_1 + k_2 \le ... \le a_{n-1} + k_{n-2} + k_{n-1} \le a_n + k_{n-1}$$$

    We can assign $$$k_n = k_0 = 0$$$

    We have a system of inequalities : $$$k_{i-2} + a_{i-1} - a_{i} \le k_i \le k_{i+2} + a_{i+2} - a_{i+1} \ \forall \ i \in [1 , n-1]$$$

    So we can assign $$$k_i$$$ to its maximum value $$$k_i := k_{i+2} + a_{i+2} - a_{i+1}$$$ and in particular $$$k_{n-1} = +\infty$$$

    After doing this process we have to check if $$$k_0 \le a_{2} - a_1 + k_2$$$

    Code : 201581485

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    here's my understanding: Let's assume N is even. We should end up with a(1) <= a(2) <= .... <= a(N), which in turn means that a(1) <= a(2), a(3) <= a(4), ...., a(N-1) <= a(N) should all be true.

    Summing up a(1) + a(3) + ... a(N-1) <= a(2) + a(4) + ... a(N). Let's say initially before operations are applied, Sum(odd) = a(1) + a(3) + ... + a(N-1) and Sum(even) = a(2) + a(4) + ... + a(N). Also let's note that increasing/decreasing consecutive elements of a by 1 doesn't affect the value of Sum(even) - Sum(odd). So if Sum(even) was initially greater than Sum(odd), it will always be.

    Now if Sum(even) >= Sum(odd), there is a solution: 0, 0, 0, ..., 0, Sum(even) - Sum(odd) (N-1 times zero and then Sum(even) - Sum(odd)). On the other hand, if Sum(odd) > Sum(even), then one of the a(1) <= a(2), a(3) <= a(4), ...., a(N-1) <= a(N) should become false. (Otherwise Sum(odd) <= Sum(even)

    Now let's assume N is odd. Now we have a(1) <= a(2), a(3) <= a(4), ...., a(N-2) <= a(N-1). Notice that a(N) doesn't participate in above inequalities, but it does contribute to sum(odd). In this case, we can turn initial sequence to -inf, 0, 0, 0, ...., 0, Sum(even), inf + Sum(odd), which will satisfy all requirements, where inf is very large number.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

which div2 was tougher in your opinion ?

from last two.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For me personally, this one. While I loved the round, expecting around -150 delta, while last round was close to +100.

    Thanks to the authors for the amazing problems. I had fun solving D2A, and, D2B during the contest, and up-solving D2C. Will be trying D2D next.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think for A — D if you compare problems at the same positions the problems on this contest were much harder than the last one except for C. Especially if you look at the B for this contest, maybe it's not so hard to guess the right construction but I think the proof that it's optimal takes quite a bit of thought and B on the last contest is much more straightforward in comparison.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, i had no proof but at last 4 mins i found the pattern but failed to finish implementation within 4 mins

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this round get's unreated?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Let T be the top path which moves right n times and moves down at the end, and let B be the bottom path which moves down first then moves right n times. For a path P let C(P) be its cost.

    Now color the grid with a chessboard colouring so a square (i, j) is black if and only if (i + j) % 2 == 0. Then we have:

    C(T) + C(B) = (sum of the numbers on the black squares) — (sum of the numbers on the white squares) + (value at (1, 1)) + (value at (n, 2))

    Now what is the maximum value of the right hand side? We should make the numbers on the black squares as big as possible, so take n + 1, ..., 2n, and we should make the numbers on the white squares as small as possible, so take 1, ..., n. The squares (1, 1) and (n, 2) are both black and counted twice, so we should make them as big as possible as well, so we take them to be 2n and 2n-1.

    In this optimal situation, the right hand side is ((n + 1) + .... + 2n) — (1 + ... + n) + 2n + 2n-1 = n^2 + 4n — 1. So in any configuration we have C(T) + C(B) <= n^2 + 4n — 1, so we either C(T) or C(B) is <= n^2/2 + 2n — 1, and so this gives an upper bound on the maximum min cost path.

    And then there are many ways to prove this bound can be achieved. You just have to come up with some pattern and check that all of its paths have cost at least n^2/2 + 2n — 1. Necessarily the top and bottom paths in an optimal configuration would have to have costs n^2/2 + 2n — 1 and n^2/2 + 2n, so that immediately constrains the search. For example, one pattern which I'll illustrate for n = 6 is to take

    12 2 10 4 8 6

    5 7 3 9 1 11

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

No more contests in the coming week?

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for the great contest! D was such a cool problem. It was one of those problems where you jump up from your seat when you figure it out.

»
6 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Why there is no upcoming contests ?

We really want more CF rounds!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is this unrated?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i miss my photo so much
thank you codeforces

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wasnt this rated contest?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When the ratings will get updated?

»
6 months ago, # |
  Vote: I like it +34 Vote: I do not like it

As Rating of Div 1 is already updated but why there is delay in Div 2 rating update?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This round was really good!

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Please MikeMirzayanov fast :)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

when will the ratings update :( . I have started to feel like they will make this unrated.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

speedforces

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester im testing your patience u could show in the comment section

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

SlowRatingForces

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this round unrated for div2?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    i suppose this is just slow ,maybe they are bussy now ,but it make me feel not good that they update the rating change for div1 already , but just don't update for div2

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      the system has already finished , it isn't testing now , will it roll back?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nice div2 hope no interactive problem next time XD

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Was this round, rated for Div 2 , cause the last one 864 div 2, showed rating much earlier

»
6 months ago, # |
Rev. 3   Vote: I like it +12 Vote: I do not like it

As a newbie, I'd like to share my solutions to Div.2 ABC. I solved all three problems in a constructive way.

Problem A: The statement "jumping from one lattice point to another without touching other lattice points" directly hints that the delta x and delta y of the jump should be relatively prime. However, it's impossible to traverse all the possible jumps. I tried several cases and the cases where the delta x or delta y equals 1 caught my attention, e.g., (1, 3) and (4, 1). I realized that two jumps that form an "L" shape would always be possible. Solution: 201604536.

Problem B: I misunderstood the problem at first, thinking the path will traverse all the points and gives an easy construction[submission:201606323]. I got WA and read the statement again. I realized that the path with minimum cost was not required to go through all the points. I studied the sample cases and found the answer has some fixed patterns. - P1: Each grid with the coordinate (1, 2k — 1) or (2, 2k) will contribute a positive term to the loss while grids with the coordinate (1, 2k) or (2, 2k — 1) will make negative contributions. To maximize the minimum loss, we can put n + 1, ..., 2n to grids with the coordinates (1, 2k — 1) and (2, 2k), and put 1,..., n to grids with the coordinates (1, 2k) and (2, 2k — 1). - P2: The path with minimum loss should not go down more than once. Based on P1, each time the path goes down, it will get an additional positive cost. So the path with the minimum cost should go down only once, i.e., (1,1) to (1, n) to (2, n) or (1, 1) to (2, 1) to (2, n). Note that this has not been proved rigorously. - P3: The path will always go through (1, 1) and (2, n). So we can put 2n and (2n-1) into these two grids. To maximize the minimum cost, we put -1 and -2 to (1, n) and (2, n-1), as the path will always go through one of them. For the left -3, -4, ..., n and n+1, n+2,..., 2n -2, to maximize the minimum cost, we pair them evenly, e.g., (-3, n + 1) and (-4, n + 2), and put these pairs into adjacent grids. Solution: 201608912.

Problem 3: This a tough one for me. I was not following the editorial and thought about a[i+1] — a[i]. Instead, I start with sequences with a length of 3. I found it is always possible to reach a solution. Moreover, we can always get a solution with three same numbers. For example, with a sequence {a1, a2, a3}, we can make it {a1, a1, a3'} by adjusting a2 and a3. Then we can get {a3', a3', a3'} by adjusting {a1, a1}. Based on this observation, we can extend to sequences with a length of 5. For example, with a sequence {a1, a2, a3, a4, a5}, we can first get {a3', a3', a3', a4, a5}. Then for {a3', a4, a5}, we can also get {a5', a5', a5'}. Then by adjusting {a3', a3'} to {a5', a5'}, we can get {a5', a5', a5', a5', a5'}. We can extend this construction to all the sequences with an odd length. So, when n % 2 == 1, always output "YES". For sequences with an even length n=2k, we already know that {a1, a2, a[2k-1]} can always be adjusted into {a[2k-1]', a[2k-1]', ..., a[2k-1]'}. To judge whether the whole sequence can be turned into a non-descending one, we only need to judge a[2k-1]' and a[2k]. To make it possible, we expect a[2k-1]' to be as small as possible and satisfy a[2k-1]' <= a[2k]. So the problem turns into finding the minimum a[2k-1]'. We can get the answer by traversing the sequence. Note the construction for the odd-length sequences is based on the last three consecutive elements in the sequence, we record the current minimum a[2k-1]' with $cur and take the next two elements into consideration, i.e, {$cur, a[i], a[i + 1]}. If $cur <= a[i], we can decrease a[i] to $cur and take a[i + 1]' = a[i + 1] + $cur — a[i] as the new $cur. Note the new $cur cannot be smaller in order to keep it non-descending. If $cur > a[i], we need to increase a[i] to $cur. Solution: 201627091.

I am still not familiar with interactive problems.

»
6 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Why there are rating changes in div 1 but no rating changes in div 2?

»
6 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

@culver0412 Please look at the matter of div 2 rating update.[user:culver0421]

»
6 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Why div.2 rating still haven't updated?It's not the normal speed,is it?

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Why the rating of div 2 not updated yet, it has been done for div 1.

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I hope the div2 rating update is just a delay, not only me but many people have worked hard in this contest

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it unrated for div2?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

may be it is unrated

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I will be deeply sad if a great round unrated,,,qwq

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

when will the ratings be out ??

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This round better be rated; it would make me blue.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please Do update the ratings fast;(

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Isn't it taking unusually long to update the ratings for the Div 2 contest? It's almost been 24 hours. culver0412 any updates?

»
6 months ago, # |
  Vote: I like it +10 Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Feeling like Educational contest.

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

what happened???

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Questions rating is updated but our rating is not update till now LOL.

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

May be Mike forgot about Div2 people (:

»
6 months ago, # |
  Vote: I like it +23 Vote: I do not like it

We should work hard to participate in Div 1 for a fast rating change ^^

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

No updates on rating for div 2?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this contest was un-rated ?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it rated — 3

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why the rating hasn't been updated? This seems unusual.

»
6 months ago, # |
  Vote: I like it +7 Vote: I do not like it

what's taking them so long, hope this contest stays rated

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me what's wrong with my code 201696829 for D (Div 2.).

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Read instructions for interactive problems. You should add cout.flush(); after all your cout’s.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      won't "endl " do the same;

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry, yes it does. As far as I understood, you just restore the order of your permutation, however your tree is not 1-2-3…n and it is 1-n-2-… You should restore the indices by multiplying 2 permutations .

»
6 months ago, # |
  Vote: I like it +13 Vote: I do not like it

[ ]

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    HMMMM ill probably have grandchildren by the time they will update the ratings

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      I think they are waiting for their parents to decide their names :-}

»
6 months ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

As far as I know, the round is rated for both divisions. Please wait patiently, we have contacted our coordinator regarding rating changes (but we haven't received a response yet).

UPD: Ratings have been updated. Thanks for being patient. Although it would be better to not spam so many comments under this blog post as I have already clarified the situation.

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

When there is going to be a rating changes?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Are there no contests this week?

»
6 months ago, # |
  Vote: I like it +18 Vote: I do not like it

If I waited for my ex for this long I would be happy married with her rn

»
6 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

when DIV2 rating will update? culver0412

»
6 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Please update the rating fast. I can't wait anymore :(

»
6 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

An Eternity has passed but the codeforces rating is still not updated.

»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it
Spoiler
»
6 months ago, # |
  Vote: I like it 0