Ormlis's blog

Codeforces Round #857 (Div.1, Div.2, based on Moscow Open Olympiad in Informatics, rated)
By Ormlis, history, 21 month(s) ago, translation, In English

Hello!

Right now happens the first tour of the Open Olympiad in Informatics, and tomorrow will be the second one. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Team Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707, 727, 751, 775, 802, 829, 852).

Open Olympiad consists of the most interesting and hard problems that are proposed by a wide community of authors, so we decided to conduct a Codeforces regular round based on it, which will happen on Mar/09/2023 12:35 (Moscow time) and will be based on both days of the Olympiad. Note the unusual time of the round. Each division will have 7 problems and 3 hours to solve them.

We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of Moscow Open Olympiad (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification.

Problems of this competition were prepared by Mangooste, Artyom123, teraqqq, Ziware, vaaven, Tikhon228, Ormlis, Kirill22, ViktorSM, isaf27, DebNatkh and DishonoredRighteous guided by grphil and Helen Andreeva.

Thanks to Aleks5d for the round coordination, statement translation and preparation of problems for the second division, and also thanks for MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

Due to the official competition source codes of other participants will not be available for an hour after the end of the round.

UPD1: Please note the number of problems and the duration of the round have been increased for each of the divisions.

UPD2: Great thanks to the testers of the round: BucketPotato, valeriu, 4qqqq, Aaeria, FedeNQ, olya.masaeva! As well as the testers of the main Olympiad: Siberian, Maksim1744, sadovan, Kapt, Pechalka, alexxela12345, Be_dos, princebelkovetz, Jatana, KiruxaLight, cute_hater!

UPD3: Scoring distribution:

Div.2: 500 — 750 — 1250 — 1750 — 2000 — 2500 — 3500

Div.1: 500 — 1000 — 1250 — 1750 — 2500 — 3500 — 3500

UPD4: Editorial, we apologize for the delay:(

  • Vote: I like it
  • -1038
  • Vote: I do not like it

Comments Comments (309)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +164 Vote: I do not like it

Waiting for Div. $$$0.5$$$, Div. $$$1.5$$$ round

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +118 Vote: I do not like it
Finally a new round after 5 days :)
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    LoL now we got more depressed because of this round!

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +64 Vote: I do not like it

Why the cat in Kirill22's profile is looking sad? ⚫⁔⚫

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +14 Vote: I do not like it

I really love the contests you hold.

Sadly, this is the second time I can't participate because of the time of the contest

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -74 Vote: I do not like it

Please, change the time. Unusual for weekdays.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Usual for weekdays, but the time is good because not 22:35 :)

    (But the problems...)

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +31 Vote: I do not like it

make 2A easy pls, so you don't scare participants away. The timing already reduced the amount of participants, and you wouldn't want to reduce that further (

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it -71 Vote: I do not like it

[deleted]

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Timings for India are just after lunch.

Perfect.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +12 Vote: I do not like it

So goooood time don't need to stay up late

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +154 Vote: I do not like it

I'll be taking this contest on a plane... Hopefully it's my highest placement ever.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

Just noticed it is 3 hours long contest.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -56 Vote: I do not like it

Looking forward to my first Div.1 contest on Codeforces. Hope it be good!

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -56 Vote: I do not like it

    Now I am back to Div.2. Thanks a lot. :(

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +99 Vote: I do not like it

Ouch, I was looking forward to the contest but will skip the round because of the increased duration :( We need shorter rounds, they are more fun!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +29 Vote: I do not like it

It would be nice if duration change is not announced last minute.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +44 Vote: I do not like it

Just when did it become 3-hours-and-7-problems instead of 2-hours-and-6-problems?

Really guys,

  • increased duration

  • in a non-standard time slot

  • announced in the last minute

is quite some combo :( .

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    The announcement letter, 14 hours ago, still says "2 hours duration".

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    • longer round because multiple harder problems
    • time slot related to the olympiad it's mirroring
    • the announcement was late but I saw it scheduled for around a week already
    → Reply
»
21 month(s) ago, # |
  Vote: I like it +59 Vote: I do not like it

Task D1G, the very first line of the statements: "Philip is very fond of tasks on the lines."

Google translate, is it you? :D

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +80 Vote: I do not like it

I'm from future, this contest is FST, and I will failed main test in problem 1801C

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

Div2B is a terrible problem

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Terrible problem description.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's nice. The statement sucks

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What's nice about it?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Well not really nice, but it isn't terrible either. It's an average problem

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

I will never take part in div1 again.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

Very hard contest

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +22 Vote: I do not like it

div2 C is very very annoying (╯°□°)╯︵ ┻━┻

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    It's annoying until you reach the insight: treat columns and rows separately. You can use for example first 10 bits to encode the row and the last 10 bits to encode the column. The solution is basically 1 line a[i][j] = ((i<<10) + j). Also, writing a checker to validate solutions was simple and very helpful for me.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

D was out of mind .. don't know how it crossed 1200+ submissions

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Idk, it was pretty standard. If you have two things, sort by the first one, iterate over it in ascending order and select the second in a proper way using some data structure (in this case just [multi]set).

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why fixing a maximum does not work in D?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It kinda works actually. But you need to iterate over all possible maximums (for A).

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      Sad u and me both got FSTed. Still a little smile to get FSTed on test 69.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        I don't even have this, mine is FST 70 :(

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I got an FST at 71 :( Probably the dumbest mistake I could have ever made. I don't know how the hell it passed 70 other test cases.

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            what was your mistake? im stuck at 71 test

            → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, do we need to use binary search on answer ?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +60 Vote: I do not like it

Oh no... I didn't receive a notification that my solution in C was hacked, and I didn't notice it until the contest ended ;(

→ Reply
»
21 month(s) ago, # |
← Rev. 8   Vote: I like it +53 Vote: I do not like it

First time solved div1 A-D (div2 C-F) in contests. I've tried a dp solution for F but got WA on pretest 15. Hoping for no FST and positive delta this time!

D1A(D2C): Let's solve a stronger version of the problem: Build a matrix A with size (1<<n)*(1<<n) where A[i][j]^A[i+1][j]^A[i][j+1]^A[i+1][j+1] = 0, for all valid pairs of (i, j). When n=0, we can let A=[0] (matrix with a single element), and if we have a solution for n, then for every a[i][j], let t=a[i][j], we can replace it with 2*2 matrix [4*t, 4*t+1; 4*t+2, 4*t+3], then we get a solution for n+1. For the original problem, we can build such a matrix for n=8, and any sub-matrix of it will be a valid solution.

D1B(D2D): Let pair[i]={a[i], b[i]}, and sort it increasingly, and let suf[i] be the suffix-maximum array of b[i]. Let s1 and s2 be the set of gifts chosen from a[] and b[]. Let's consider a maximal segment [L, R] with same value of a[i], and let m1=a[L]. Then for i>R, we must put b[i] in s2, so m2>=suf[R+1]. If suf[R+1]>=m1, then when m1=a[L], all gift combinations will have abs(m1-m2)>=suf[R+1]-m1. Otherwise, we can add some value b[i] to s2 for i<L in order to increase m2. (If R-L+1>1, we can also add b[i] for L<=i<=R) Therefore, we can use a ordered set to maintain candidate values for m2, and use binary search to find the nearest to m1.

D1C(D2E): DP. First we can remove useless elements in every albums and make them strictly-increasing. Then we can let dp[i] be the maximum length of all possible strictly-increasing coolness subsequences in which the maximum value is no more than i. By checking every albums with maximum coolness i, if there's a song with coolness j, and there are k songs with coolness >=j in this album, we can get dp[i]>=dp[j-1]+k.

D1D(D2F): First because n<=800, we can calculate dist[i][j] by dijkstra for every pairs (i, j), and assume there is direct edge (i, j) if i can reach j. Then we can solve by greedy: In any optimal solution, assume the amount of coins we get by performance is w1, w2, w3..., it must be a non-decreasing sequence. So we can sort cities by w[i] (and discard cities with w[i]<w[1] because they are useless), and assume we only go to city with higher w[i], let dp[i] = the minimum number of performances we need to reach city i, remain[i] = the amount of coins we left after reach city i, we can solve the problem.

Update: I've got FST on D1B on test 70. Perhaps I'll get another negative delta this time.

Update2: Now I've fixed my solution for D1B. The keypoint for no FST: set suf[n+1]=-inf (instead 0).

Update3: Fortunately I still got little positive delta. Maybe that's because too many FSTs.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Hey can you please tell how did you solved Div2 D ?

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    YocyCraft: finnaly +ve delta in a div1 contest
    Div1B: hold my beer

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

    Hi YocyCraft. I had the exact same idea as you for D1D. I have no idea why my submission 207484281 is failing testcase three. I have tried to debug it for hours and also went through your code line by line to see if there is something that I have missed. I would be grateful if you could take a look at my code and point out why it is failing.

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      Perhaps this line is wrong:

      tc = (dis[b[j].S][b[i].S]-coins[j])%b[j].F;

      I've got AC by change the code like this (submission:207504840):

      ll dp_inc = (dis[b[j].S][b[i].S]-coins[j]+b[j].F-1)/b[j].F;
td = dp[j] + dp_inc;
tc = coins[j] - dis[b[j].S][b[i].S] + dp_inc * b[j].F;
      → Reply
»
21 month(s) ago, # |
  Vote: I like it +38 Vote: I do not like it

How to solve Div1D?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    Spoiler
    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Hey, if possible, can you please have a look at my this submission https://codeforces.me/contest/1802/submission/196657563, I did the exact same thing which you are telling but got TLE.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The greater<> comparator is prioritizing the least number of performances first, then the least number of coins (it should be the greatest number of coins). You can fix it by inserting negative values for coins on the priority queue.

        AC submission

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          Hi, thanks for your reply. Silly mistake :( got ac now.

          But I still have a doubt: why was it giving tle, basically if I am preferring lesser number of coins (with that mistake) then why would it give TLE and when I prefer more coins then it's within the TL.

          Update: got the reason that actually, after a (i,j) pair is popped out of the priorioty queue, after that if we get more number of coins possibility with the same number of performances then we will again push it into the queue and it will again be processed. So tle.

          → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ahh that makes so much sense. Thank you.

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

      Why is it always optimal for a node to choose a pair with the least amount of performances?

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

        Because in an optimal strategy, the cities you perform must have increasing profits (if you perform in a city with less profit than some city $$$C$$$ you have been, why not do the performance in $$$C$$$ instead).

        So if you perform in a later city you can gain more with each performance, and you should try your best to "delay" the performances to a later city. So the least amount of performances is always optimal.

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

          I tried to create a counterexample, but eventually it helped me to understand your reply. Thanks!

          → Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve Div 2. C ?? Any hint?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Look at the test cases and observe diff between a[I][j] and a[i-2][j]

    You will get a hint

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    make every 2*2 block xorsum equals zero

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried this but didn't got how to do it. Can you explain your solution?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 4   Vote: I like it +5 Vote: I do not like it

        one observation is that 0^1^2^3=0

        so in my solution, i tend to make a matrix like this first:

        $$$ \begin{bmatrix} 0 & 1 & 0 & 1 & 0 \cdots \\ 2 & 3 & 2 & 3 & 2 \cdots \\ 0 & 1 & 0 & 1 & 0 \cdots \\ 2 & 3 & 2 & 3 & 2 \cdots \\ 0 & 1 & 0 & 1 & 0 \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{bmatrix} $$$

        and the later code is just make them different. though the impl contains some magic number, but the idea is keep the two least siginificant bits and change the higher bits. like xxxxx[00~11]

        also, if we "seperate" the origin matrix every 2 rows/cols, there are some 2*2 blocks "cross" the seperator. so this case we'd better make the modification only depends on row number(in my code (i / 2) << cnt) or col number(in my code (j / 2) * 4).

        and i recommend you to see jiangly's code, much simpler

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

          UUUnmei I tried doing this but can't think of encoding in order to make all different and also still satisfy the condition.

          → Reply
          • »
            »
            »
            »
            »
            »
            20 months ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            well, you can run my code and output the result after each step and do some obsversation.

            think first two rows for a start, and modify them based on coloumn number. each result col will be like (0 2)(1 3)(4 6)(5 7)(8 10)(9 11)(12 14)... in other words, add 00000,00100,01000,01100.. to every 2 coloumn respectively. this is keep the two least siginificant bits and change the higher bits. we do so for all coloumns.

            then we modify by row number. the idea is same. but we have to keep not only two least siginificant bits unchange, but more. this is exactly what code while(t<2*m) t*2, cnt++ does — count the number of bits. and finally add on a proper number like (i/2)<<cnt will be ok

            → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    isn't all elements of the matrix being == 0 a possible answer? or am i missing something? nope thats not it i misread

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      you need to maximize different colors(values in matrix). All elements must be as much different as possible. Taking all zeros make it only 1color

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nope we can't make all elements 0 as the arrays needs to have as many distinct elements as it can have to achieve all the conditions

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just fixed the 1st 2*2 box as

    8192 8193 8194 8195

    Then I just filled the next 2nd box as 8196 8197 8198 8199

    Just like this I filled the first 2 rows and then from the 2nd row considering 0 based indexing I just did a[I][j] = a[i-2][j]+8192

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    generate a matrix of 256*256 and fill it with natural numbers (0,1,2,3,4,5.......). then print the the first n*m matrix for each test case. Done..

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    What I did is

    Spoiler
    → Reply
»
21 month(s) ago, # |
  Vote: I like it +125 Vote: I do not like it

Trash round.The pretest is so weak.And there are too many hacks.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Indeed.And the example of Div2 D is so weak.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I made the following two submissions on D2D, the first one sorts a vector, and the second one set. Overall time complexity should be $$$\mathcal{O}(n \log n)$$$ acc to me.

AC: https://pastebin.com/PNZMN6LW

TLE: https://pastebin.com/ZDmtxJNm

Basically, I want to know why did the second with sets TLEd ?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

How to come up with div 2C other than guesswork?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Notice that in each 4x4 matrix we use 2 rows and 2 columns. And each is used twice. Solve for row and columns separately, use non-intersecting bits (for row and columns).

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Hint : Binary

    For every 4 elements in a quad, try and keep the XORs for every digit of the numbers to be 0.

    To be more precise -> { 1100 1101 1110 1111 }

    0th digit -> 0 ^ 1 ^ 0 ^ 1 = 0 1st digit -> 0 ^ 0 ^ 1 ^ 1 = 0 2nd digit -> 1 ^ 1 ^ 1 ^ 1 = 0 3rd digit -> 1 ^ 1 ^ 1 ^ 1 = 0

    Try and build upon that

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve DIV2 B

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    mainatain a counter variable initially 0, notice that if your a[i]==1 then it means just add 1 to your counter because if you buy a new pig then u will be needing an extra cage as you dont know the gender. when a[i]==2 assume that half of them are males and other half females (any one can be assumed to be one greater in number in case counter is odd). why half of them and why not all same? because then you would be needing just (counter+1)/2 cages which is not the maximum considering the presence of 2 genders in the distribution. further, just divide the animals and calulcate the max no of cages required considering (counter+1)/2 and counter/2 males and females resp. it will turn out to be (2*counter+5)/4. update it and store the maximum of all of them.

    196612008

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +15 Vote: I do not like it

Very bad statements ):

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -9 Vote: I do not like it

Bforces

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +14 Vote: I do not like it

The descriptions of problem Div2 A,B are terrible.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can't agree more, I originally thought Div2 A was asking for the max/min possible votes for each position i.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +46 Vote: I do not like it

The most difficult part of this round is to understand statement

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +18 Vote: I do not like it

Tired of reading long and unnecessary statements

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Failed to solve C again. Expert is waiting for me:(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

C The matrix in the error report after submission starts from 0! This doesn't match the question! This took me an hour!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve div1F?

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

    Let $$$\displaystyle f[i][r] = \max\left\lbrace\prod_{j=1}^{i}(\frac{1}{a_j}\lfloor\frac{a_j}{b_j}\rfloor) : \left\lceil\frac{k}{b_1b_2\cdots b_i}\right\rceil=r\right\rbrace$$$

    Then we can use $$$\displaystyle f[i][r]*\frac{1}{a_{i+1}}\lfloor\frac{a_{i+1}}{b_{i+1}}\rfloor$$$ to update $$$\displaystyle f[i+1][\left\lceil\frac{r}{b_{i+1}}\right\rceil]$$$

    Take notice of: There are no more than $$$2\lfloor\sqrt{n}\rfloor$$$ different numbers in $$$\displaystyle\lbrace\left\lfloor\frac{n}{1}\right\rfloor,\left\lfloor\frac{n}{2}\right\rfloor,...,\left\lfloor\frac{n}{n}\right\rfloor\rbrace$$$

    And $$$\displaystyle \left\lceil\frac{n}{i}\right\rceil=\left\lfloor\frac{n+i-1}{i}\right\rfloor =\left\lfloor\frac{n-1}{i}\right\rfloor+1$$$

    So all possible $$$\displaystyle r\in R=\left\lbrace\left\lfloor\frac{k-1}{i}\right\rfloor+1 \bigm| i\geq 1 \right\rbrace$$$ and $$$|R|\leq 2\lfloor\sqrt{k-1}\rfloor+1$$$

    If we want to update $$$f[i+1][t+1]$$$ with $$$f[i][T+1]$$$,

    it is optimal to choose the smallest $$$b_{i+1}$$$ satisfying $$$T/b_{i+1}=t$$$.

    Then we can solve the problem in $$$\displaystyle O(nk^{\frac{3}{4}})$$$ time

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

      I suppose you mean $$$f[i][r] = \max \prod\limits_{j=1}^i$$$ instead of $$$f[i][r] = \max \sum\limits_{j=1}^i$$$?

      Could you explain more on the complexity? It seems to me that you're updating $$$f[i + 1][r']$$$ with $$$f[i][r]$$$ where $$$r, r' \in R$$$, so the complexity should be $$$\mathcal{O}(n \times |R|^2) = \mathcal{O}(nk)$$$. Why is it $$$\mathcal{O}(nk^\frac{3}{4})$$$?

      You might say that the complexity is $$$\mathcal{O}(n \times \sqrt{k} \times (1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{k}}))$$$, but as far as I remember $$$(1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{k}}) \approx 2\sqrt{k}$$$ (reference) so it is still $$$\mathcal{O}(nk)$$$.

      Update: OK I understand where I missed. The complexity is actually $$$\mathcal{O}(n \times \sqrt{k} \times (1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{2\sqrt{k}}}))$$$ because there are at most $$$2\sqrt{k}$$$ elements in $$$R$$$. So the complexity is $$$n \times \sqrt{k} \times 2\sqrt{2\sqrt{k}}$$$, that is $$$nk^{\frac{3}{4}}$$$.

      → Reply
      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        OK. QwQ

        If we always simply enumerate all $$$r\in R$$$, it will take $$$O(|R|^2)=O(k)$$$ and get TLE.

        Again, for each $$$T$$$, the number of possibly $$$t$$$ is $$$O(\sqrt{T})$$$.

        If we enumerate $$$t$$$ for $$$T$$$ by the same way as enumerate $$$r$$$, we will take

        $$$\displaystyle \sum_{r\in R}\sqrt{r}\leq \sum_{i=1}^{\sqrt{k}}(\sqrt{i}+\sqrt{\frac{k}{i}}) \leq 2\sum_{i=1}^{\sqrt{k}}\sqrt{\frac{k}{i}} \leq 2\int_{0}^{\sqrt{k}} \sqrt{\frac{k}{x}}\text{d}x =4\sqrt{kx}\bigm|_0^{\sqrt{k}}=4k^{\frac{3}{4}} $$$

        → Reply
      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        For each i, we need to compute $$$f(i, x)$$$ for each $$$x$$$ in the form of $$$\lfloor{k-1\over j}\rfloor$$$ with a complexity $$$O(\sqrt x)$$$. You can see that the total complexity for each stage is $$$\sum_{j\leq \sqrt{k-1}} \sqrt{k-1\over j} + \sum_{j\leq \sqrt{k-1}} \sqrt j = O(k^{3/4})$$$.

        → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

like a fish

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Annoying and useless statements :(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

My idea for $$$D$$$:

Let $$$dist[v][s]$$$ is the minimum number of representations if we finished in vertice $$$v$$$ and the best representation cost is in vertice $$$s$$$ which is on path. Let $$$rem[v][s]$$$ is the number of coins at the end in this answer.

I do Dijkstra, since the edges values are $$$\ge 0$$$. Fix vertice $$$v$$$ and best representation cost $$$w[s]$$$. Look at neighbour $$$to$$$. If $$$w[to] > w[s]$$$, then we go to $$$s_{new} = to$$$, otherwise $$$s_{new} = s$$$. Then if $$$rem[v][s] < cost$$$ then I add $$$ceil(\frac{cost - rev[v][s]}{w[s]})$$$ to number of representations.

Answer is $$$dist[n - 1][i]$$$ for some $$$i$$$.

However, I get $$$WA19$$$. Is this idea correct?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Maybe you should also use $$$rem[v][s]$$$ in your priority queue, as a tie breaker.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Thanks, yes, this is incorrect, as it can be, that there are two pathes to some vertice with same "best representaion cost", but different edges cost, and I will propagate less $$$rem$$$ further. (Interesting, that it got wrong answer only on 19th test)

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Why is the time limit in Div1C set to 1 second? What solutions did you try to cut off? Why not set 2 seconds?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    Why they should? 1 second is standart time limit and there no reasons to increase it more.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

div2 B English statement make me so confused

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +40 Vote: I do not like it

The duration increase was a total bs, 2h -> 3h is a massive change and it only happened just before the start. This was only communicated in this post, so some people could easily not see that (myself included).

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +65 Vote: I do not like it

Pretests for D are so weak that I don't even know if there are any pretests

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +23 Vote: I do not like it

I spend 30 minutes in reading problem statment of 2a.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +64 Vote: I do not like it

FST.

Pain.

R.I.P. +264 Delta and 7th

upd: why +274 with 10th

→ Reply
»
21 month(s) ago, # |
← Rev. 4   Vote: I like it -6 Vote: I do not like it

Nice pretests, excellent excercise for debugging, dry-running and hacking! Makes the contest results a rng! Lots of suspension and surprises!

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I remember in the old days every second contest was like this. But tbh I do not miss those times.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Please share some more problems like Div1 D.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Nice pretests！

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +32 Vote: I do not like it

Very weak pretest for D1B and D1C. Welcome to Hackforces.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +16 Vote: I do not like it

f**king pretests of B.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Inappropriate time

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +45 Vote: I do not like it

does case like

3

1 7

4 1

9 5

intentionaly removed? I can't imagine these case doesn't appear if case was randomly created. If it was on purpose, I can't believe power of multi-testcase any more...

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    For D1C they didn't add pretest like

    100 1 2 3

    I guess there were no pretests :)

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My D1B solution fails on a test

    2

    2 4

    8 3

    Like, n is 2...

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +29 Vote: I do not like it

One more day at Codeforces!

Spoiler
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Today is a nice day to drop out of masters...

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Second time I solve Div2ABCD. Thanks for the round!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +16 Vote: I do not like it

very bad statement for B ):

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +283 Vote: I do not like it

So I guess people will be hating the round because of very weak pretests in C (and also B and maybe D I guess, I'm testing right now and more than 10% of random testcases make my solution fail, so the fact that there are $$$11$$$ pretests, each with $$$t \geq 1$$$, is very strange), but that's not the case. It isn't bad that the pretests are weak, the problem is that their strength is inconsistent between rounds.

This inconsistency actually randomizes the contest, as people have to guess between "if it passed the pretests then there's no reason to look into this problem anymore" and "pretests don't mean anything and I have to decide myself on how much extra time I should spend". It's coordinator's job to keep the things right and imo this time this job was done poorly. The fact that the problems were "ready", as they were used on some olympiad, doesn't mean that there isn't much to do. You still have to check if everything fits codeforces standards.

Also, scoring distribution totally sucks, as you can see in the standings. Idk who came up with it.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -42 Vote: I do not like it

    No matter what it's abnormal that over half of contestants on a single page of the scoreboard get FST.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +54 Vote: I do not like it

      Yeah, "abnormal" is a word connected to the word "inconsistent". Many years ago it was totally fine and people were simply using different strategy, but as cf evolved this strategy was being punished -- there's usually no need to waste time if your solution passed the pretests and that's fine, the contest became more "comfortable".

      Yeah, by saying more I'd start repeating myself.

      → Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I've Just submitted 1D (not participated in the contest), and got WA on test 84 (out of 85!!!). IIRC it's my record for the largest failing test so far. The test is clearly seem to be designed specifically for the type of mistake I've made (which is: sometise user-defined infinity not infinite enough). Not sure whether it is authors' generated tests, or tests from the successful hacks are added to the final test set. But if it is authors' generated, I'd move it to pretests.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

In a single page of standing there are 12 FSTs on the scoreborad. How crazy it is!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -87 Vote: I do not like it

The authors should be banned, and the round should be made unrated

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

Can pretests be stronger?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

weak pretests

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +33 Vote: I do not like it

My GM :(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

Really disappointed in the contest dear Sir.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +132 Vote: I do not like it

Hello!

In contest I passed E with 43 pretests in 3385ms.

And now I received TLE on test 30 in final test.

After contest I submitted again and passed all tests.

Could you please deal with this Ormlis MikeMirzayanov?

Thanks!

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    gyh bot/cf

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got TLE in F on systests and now submitted the same code and got AC :(

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This blog had the similar situation before, but got many downvote. Why this comment got so many upvote?

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

OMG, 2 FST

QAQ
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    introspection
    → Reply
»
21 month(s) ago, # |
  Vote: I like it +48 Vote: I do not like it

Forgot to add 1 line, lost 200 ranks, thanks pretest!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +45 Vote: I do not like it

Here is one solution for Div2C that does not require you to think too much (unless a probability calculation is "thinking too much")

Fill the first row and column with fully random numbers in the range of $$$[0,2^{63})$$$. After that, fill the rest of the grid as $$$arr[i][j]=arr[i-1][j] \oplus arr[i-1][j-1] \oplus arr[i][j-1]$$$. Now all submatrices with size $$$2 \times 2$$$ have a XOR of $$$0$$$. Probability of a collision will be at most $$$\frac{40000}{2^{63}} \approx 4 \times 10^{-15}$$$. I believe that there is a tighter bound of the probability but I am lazy to prove it.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    I was even lazier and stress test all the cases before submitting :)).

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    even simpler. a = [[ j ^(i<<10) for i in range(m)] for j in range(n)]

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yes that is indeed simple but I am lazy to think

      → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Happy Newyear!

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    I think the pretests are constructed to make participants get FSt.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      And FST on Test 69 was intentionally created to tease the participants xD

      → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why am I getting Runtime error https://codeforces.me/contest/1802/submission/196666198 ?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Never call erase() method of a container while using its iterator, store elements need to be erased and call erase() after iteration instead.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone share an intuitive idea of div2 C ...waiting for editorial

I am guessing some property of xor of consecutive number has to be utilized, couldn't figure out :(

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i made xor of all elements of each square 2 x 2 equal zero

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Try to assign some bits to each row and each column such that no row's bits are same as any columm's, and to get value for an element of matrix, sum up it's corresponding row's and column's values. In each 2*2 matrix, we have we have even elements corresponding to a row and a column so their individual xor becomes 0. Reason behind separating bits is that addition doesn't make any bits to get carried further. Like: $$$a_{ij} \ = \ 512 \cdot i + j$$$

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +50 Vote: I do not like it

I've said this before, and I'll say it again. Aleks5d is not a good coordinator.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +21 Vote: I do not like it

This contest gives GreenGrape contests vibe.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

FST-forces

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +343 Vote: I do not like it

Thanks to Aleks5d for the round coordination, statement translation

Probably should have chosen someone who knows English. And can coordinate rounds.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 4   Vote: I like it -60 Vote: I do not like it

    I believe that contestants should just learn russian. It is statistically proven that it increases rating (and you maybe just found out why)

    upd: idk why I'm downvoted that much, my comment was obviously irronical and not serious

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2-D had a very weak pretest. I got a WA in actual testing. It was : 

1
2
10 100
10 100

Which cost me +ve delta.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +17 Vote: I do not like it

I have an FST, but my place became better)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Not good! The f**king English statement in B confused me a lot. I literally spent about 30-40 minutes on it just to understand the statement and, respectfully the test cases! And in C, the test cases are hilarious! Abused the fckn time + delta! Unfair and unbalanced round!!! Please consider these problems next time!!!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Kirill asks you to help her weave a very beautiful blanket, and as colorful as possible!

He gives you two integers n and m

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +37 Vote: I do not like it

The system test is weak too.

My solution for Div.1 D is wrong with the following input:

hack

Can't believe that it really passed system test.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

A really simple solution for Div1A / Div2C:

Spoiler
→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it 
vector<vector<int>> a;
sort(a, a + n, [](vector<int> x, vector<int> y){
    return x.back() < y.back();
});

Why this got TLE? Since cmp is O(1) and swap is also O(1), I think the time complexity is correct.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    this has to copy construct two vector as parameters every time.

    try use const vector<int>&

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Oh, thanks a lot. Another question is, does copy construction affect to the time complexity or it's just a huge constant?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        It just copies every time, which takes too much time and memory to copy every time. It is not a constant if I am not mistaken.

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It depends on the sorting method we are using. Suppose we have $$$n - \sqrt{n}$$$ vectors of size $$$1$$$ and $$$\sqrt{n}$$$ vectors of size $$$\sqrt{n}$$$, and we are doing quicksort on them. We randomly choose one vector and compare it with all other vectors, so there is a $$$1/\sqrt{n}$$$ probability to cost $$$O(n\sqrt{n})$$$ time on this step.

        Similarly we can construct a testcase to let merge sort run in $$$O(n^2)$$$. Heap sort seems to have a correct time complexity, but I am not sure.

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        i think it will affect to the time complexity, because the time of memory allocation must be proportional to the size. very roughly O(n) time.

        we usually neglect this because problem will guarantee "the sum of n over all test case is no more than 2e5(for example)". so we can write something like 

        for each testcase
   read n
   vector<int> a(n)

        and we will just use O(2e5) memory in total, and it is kind of inevitable.

        but say if you write something like 

        for each testcase
   read n
   vector<int> a(MAXN)

        then it will certainly TLE/MLE if there are many testcases

        and copy is another part of cost which won't be less than allocation

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          Memory usage isn't a concern here unless you do something weird with the vector like moving it to the heap. It will be deallocated when you get to the end of the scope it's declared in, so it won't ever take up more than about MAXN*sizeof(int) bytes at any one time. TLE is definitely an issue though.

          → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Vector by copy i guess.

    Maybe sort(a, a + n, [](const std::vector &x, const std::vector &y){ return x.back() < y.back(); });

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

This blog is getting downvoted a lot, problem A story gonna become real kekw

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

if my mom saw the div2B she would be disgusted and will forbid me from ever participating in codeforces rounds.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Better edu rounds than weak pretests.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I solved E as we were allowed to skip any index we want but still passed the pretests x_x

my solution was failing at this case:

1 3 3 1 2

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Why not put some of the corner cases in the pretest???

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +52 Vote: I do not like it

Codeforces Round #857 (Div.1, Div.2, based on Moscow Open Olympiad in Informatics, rated, Weak Samples, Weak Pretests!)

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Codeforces Round #857 (Div.1, Div.2, based on Moscow Open Olympiad in Informatics, rated, Weak Samples, Weak Pretests, Unclear Problem Statements!)

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Maybe not the worst contest as some comments mentioned, but why is E much harder than F?

By the way, the pretest of B is too weak that I and most of my classmates got FST...

Note that I participated in Div.1.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

The statements made me feel dyslexic

→ Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it

As usual, I'll give my advice about this round here :)

A
B
C
D

I didn't have time to try the other problems I'll post another comment when I'll upsolve them

Anyway, thanks to the authors for this round which was pretty cool!

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No one is asking for an INF amount of pretests. But there are some stupid solutions that shouldn't even pass pretests.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I mean if you get WA because you guess some random stuff and implement it without having any proof, you can't complain about getting systested...

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        That's not what I mean obviously, why would anyone just submit random things? I mean the pretests should be able to cover details in the problem statements. In this contest it was possible to misread the problems and still pass pretests.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          ← Rev. 2   Vote: I like it +7 Vote: I do not like it

          Yes I updated my initial comment because I learned someone has been systested on div1 B for not seeing each friend should have at least one gift...

          → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I thought just i screwed up D in system testing.But there are many participants whose code passed pretests but failed in main testing in D.

Hope you guys make better Pretests next time. Negative Delta coming towards me. Anyhow i enjoyed the round. xD

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I thought with 11 pretests for 2D my solution would surely pass but nope

Luckily my delta is still barely positive

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

What's up with E's statement ? At first I though they can change the prices each year, the problem will be unsolvable then unless they pulled some Chinese data structure. This problem is easiest in last 4 problems and could've got hundreds more of submission if not for the statement.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've misunderstood it too. If each of equality constraints are independent, the problem will be unsolvable. But if the (i+1)-th constraint is laid over previous constraints, we only need to keep components by DSU (and calculate the intersection of valid price ranges when merging 2 components).

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    I understood the statement and came up with a solution, but that's like an hour of coding for me. "Hundreds more submissions" seems too hopeful

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

why are the problems not accsesible right now?

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Nice contest

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +16 Vote: I do not like it

Is this round gonna be unrated?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Why they write in problem C bitwise exclusive or instead of bitwise xor.I was confused.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    oops, I just saw it was xor not or.

    LOL

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The symbol of XOR was given so i didn't even read the above part XD

    → Reply
»
21 month(s) ago, # |
  Vote: I like it -21 Vote: I do not like it

Why so many downvotes ?The contest was difficult but interesting (even though I could solve only first two).The setters deserve respect

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

    Because statements are very bad and unclear. Pretests were very weak. Many people got FST, but passed pretests.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

It's ok to comment to help the setters improve but I don't think that it's fine to downvote just because you got FST on d1 B/d2 D...

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    That's way problem setters need to control the amount of FSTs by prepare pretests carefully.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Don't forget increasing the duration by an hour right before the contest.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

not able to figure out what is wrong with my div2 D solution, here's the code

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -24 Vote: I do not like it

Idk if i feel happy i didn't experience this clowning or sad that i didnt capitalize on the fsts for infinite delta

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

I don't get the downvoting. Yea there were fsts but the tasks were nice

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +32 Vote: I do not like it

It's sad when one person who published a post gets a negative contribution because of mistakes by the team and the coordinator in particular.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

So, is the contest going to be rated? $$$5$$$ hours have passed since the end of the contest and yet no news have been published regarding the situation.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    why in the world it can be unrated?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      I mean, yeah, (possibly intentionally) weak pretests shouldn't be a reason to make a contest unrated, since there have already been a few rated contests with extremely weak pretests in the last couple of years (and I have a positive delta, so I want it to be rated)0). However, the rating change hasn't happened yet and that's why I'm asking it here.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +31 Vote: I do not like it

        My guess is that there is no rating changes, because people who can do it are busy with on-site contest. I will be very surprised if the round is declared unrated due to weak prеtests, correct me if I am wrong, but there has never been such a precedent in the history of codeforces.

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        rating change has happened if you click on all contests it saying unrated contests.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          it shows like that on all the contests whose ratings haven't been updated

          → Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

C>D>E

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

is this round rated?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think yes.

    But it's taking a lot of time in giving the final rating changes.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me find out the mistake in my solution for Div1C/Div2E ? https://codeforces.me/contest/1802/submission/196698368

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

Why is it taking so long to publish the rating changes ??

I guess the round is rated !

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Me: Seeing likes of this post.

All others: Taking Div2 — A problem seriously

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

This doubt is related to Problem div2E I have a doubt regarding how inbuilt sort function works. I actually want to sort a vector of vectors on the basis of the last element of the vector.

First I implemented an comparator function but It gave TLE on some testcase. For more details please check my submission 196715506

Then I made a map of <int,vector<vector>> and then reconstructed the vector of vectors in a sorted fashion by simply iterating over the map. For more details check my submission 196715303

The only change between both the submission is of the way I choose to sort my required vector of vectors. Can anyone explain the TLE in first case??

In advance Thanks a lot for your help :)

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    You have used copy construct function in your sort part:

        sort(all(v), [&](vi a, vi b) {
        return a.back() < b.back();
    });

    This copy construct funcition takes O(size) time. and std::sort method will compare one element with others at most O(n) times. That's a O(n^2) method. Just modify like this:

        sort(all(v), [&](const vi &a,const vi &b) {
        return a.back() < b.back();
    });

    const is not least but suggested. In the implement in map, the compared method takes O(1) time, either the swap method.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me find the mistake here..

verdict is: " wrong answer 42nd numbers differ — expected: '1', found: '0' " 196716275

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Find any correct solution and look in the tests for example test N36. For example you have the wrong answer on that one:)

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Try testcase:

    1
3
0 0
0 0
1 1

    Correct answer should be 1

    → Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

Totally didn’t FST on Div1B / Div2D :(

Spoiler
→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please help me out with my submission for Div2 problem D? link-https://codeforces.me/contest/1802/submission/196720503

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Good problems, shit pretests.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Either the contest time or the delta rating is good. Hardly times both is good =(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

Worst contest... Problems was not clear...

→ Reply
»
20 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Worst Contest!

→ Reply
»
20 months ago, # |
  Vote: I like it +12 Vote: I do not like it

FSTforces

→ Reply
»
20 months ago, # |
  Vote: I like it +10 Vote: I do not like it

My 7k solution to 1E seems to be of medium length.

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think every contest is meaningful.Although there were many accidents in this game,we can still learn that we should solve problems more rigorously.

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

    And the authors can still learn that they should prepare pretests more rigorously.

    → Reply
»
20 months ago, # |
  Vote: I like it -16 Vote: I do not like it

I took too much time to solve A and B , and thus did not submit, I thought I will give contest only if I am able to solve C and that's what I did.

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

trash round

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any editorial?

→ Reply
»
20 months ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Proof for c: The first observation is consecutive even and odd pair of xor of numbers is equal to 2 for example (0 2) (1 3)... So the first two rows can printed like:

  • 0 1 4....
  • 2 3 6...

We observe that the xor of every 2*2 block is 0 So we want the same thing starting from the third row, well we know that the first two rows satisfies the condition, so what we can do is use the numbers in the first two rows again but with a little modification, since we should not use duplicate numbers, we can think of adding an extra leftmost set bit to all the numbers in the 1st and 2nd row and copy them down to the 3rd and 4th row. What is that extra left set bit? The maximum number in the first two rows will be (4*(m/2) + 3).

4 because with every 2 columns we increase our number by 4, for example from 0 to 4 in the first two rows and 3 because in every 2*2 sub matrix, the 4th Number is incremented by 3.

Therefore the max value with m=200 is 403.

The nearest power of two to 403 is 512 which is (1<<9). Therefore we can add 512 after every 2 rows and the numbers won't repeat, since after adding 512 again the left most bit will now be 10th and so on. The last number in the matrix will be 512*(198/2) + (403), i guess which is within the given constraints which is (1<<63).

→ Reply
»
20 months ago, # |
  Vote: I like it +4 Vote: I do not like it

so weak pretest.Why it pass.

pass D in last second ---> BC fst + D hacked.

→ Reply
»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I can't understand these problem statements. Especially div2B. In the past period of time, I worked very hard to do some questions, but this result is hard for me to accept. It also shows that there's something wrong with my approach. What can I do to improve? Should I do something more difficult?

→ Reply
»
20 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Problem A in div1 is a trash problem.

→ Reply
»
20 months ago, # |
  Vote: I like it +7 Vote: I do not like it

There may be too many people failing system test.

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

it is easy to fst in this contest. however, i think this can remind you that you need to code more carefully.

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    Exactly! why blame weak pretests? Yes problem statements would have been more clear but it's for all participants. We just need to understand it carefully and implement accordingly. That's it

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

      Because pretests are not meant to be weak. Especially not VERY WEAK!

      → Reply
      • »
        »
        »
        »
        20 months ago, # ^ |
        ← Rev. 4   Vote: I like it -18 Vote: I do not like it

        you should practice writing the correct code even WITHOUT ANY tests. especially there are NOT ANY "PRETESTS" FOR YOU even something WEAK when you make a project or something else. the meaning of "competition standing list" is to show who is more capable, and who is less capable. for example, A can write the correct code once while B needs to adjust his code to pass all the pretests. you can see A is more capable than B and B may FST because his code is an adjustment from the wrong code so there may be something stronger than pretest in system test. then, this problem can distinguish these two people at different levels. for another example, A can write the correct code once while C's code can only pass the pretest but not the system tests. obviously A is more capable than C and this problem can also distinguish these two people at different levels.

        i didn't have an good grade. i solved div.1 A / div.2 C in 10 minutes, then i "solved" 1C/2E (i might used set incorrectly then i could not pass the pretest of 1B/2D). after a while, i found that my program will execute an operation 2e5 times in each case (the number of cases is 2e5) so i wrote a new one. unexpectedly, it TLE on test 24(system test). guess what?

        i just used cin/cout without "ios::sync_with_stdio(false)". i used to think that the computer of CodeForces is fast so i can use cin/cout without it instead of scanf/printf. this contest gave me a rude awakening.

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

          Well, we are on Codeforces, a platform for competitions WITH TESTS. Why would we practice writing code without tests during an ongoing contest?

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

          I apologize, but I find that statement to be illogical. Writing precise code without any testing to verify it seems counterintuitive. Even in industry practices, it is customary to adopt Test-Driven Development (TDD) by writing unit tests prior to coding. This approach is widely accepted as the norm.

          → Reply
»
20 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Where is the editorial?

→ Reply
»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Why do so many people dislike this scene

→ Reply
»
20 months ago, # |
  Vote: I like it +40 Vote: I do not like it

We still don't see the Editorial for the contest we attended that day...

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B is Worst problem ever

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

still no editorial, please add

→ Reply
»
20 months ago, # |
  Vote: I like it +11 Vote: I do not like it

No Editorial??????

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For div2 d I am getting TLE, but according to me it's in nlogn. can anyone help me to find the issue? here is the code 197206553

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

    Instead of lower_bound(b1.begin(),b1.end(),make_pair(it->first,inf)); use b1.lower_bound() . Former one is O(N), latter one is O(logN).

    → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what FST round!

→ Reply
»
20 months ago, # |
  Vote: I like it -16 Vote: I do not like it

https://codeforces.me/contest/1802/submission/197224405 D2 F 救命 HELP！I'm wrong!I'm going to die！

我快死了 快救救我 wa on 35 救救孩子吧！

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got message from codeforce that my code is coinciding with other code but i havent used any online complier or got code from other place rather i tried to write in new formate which i had learnt recently what can i do to prove i didn't took code from anywhere

→ Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Hello. Why is the content unrated for me? (I think some other participants had the same question in comments). A few days ago I got my rating updated, but now it decreased back...

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think, if you remove all the pretests of div1B, the number of participants who got FSTed will be lower.

→ Reply