Ormlis's blog

Codeforces Round #857 (Div.1, Div.2, based on Moscow Open Olympiad in Informatics, rated)
By Ormlis, history, 13 days 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, antony191, 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
  • -1032
  • Vote: I do not like it

»
13 days ago, # |
  Vote: I like it +164 Vote: I do not like it

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

→ Reply
»
13 days ago, # |
  Vote: I like it +118 Vote: I do not like it
Finally a new round after 5 days :)
→ Reply
»
13 days ago, # |
  Vote: I like it +64 Vote: I do not like it

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

→ Reply
»
13 days ago, # |
← Rev. 5   Vote: I like it -24 Vote: I do not like it

Good luck guys :) ♡

→ Reply
»
13 days 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
»
13 days ago, # |
  Vote: I like it -10 Vote: I do not like it

the round will probably be heavy on math problems

→ Reply
»
13 days ago, # |
  Vote: I like it -74 Vote: I do not like it

Please, change the time. Unusual for weekdays.

→ Reply
  • »
    »
    11 days 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
»
13 days 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
»
13 days ago, # |
  Vote: I like it -71 Vote: I do not like it

I am still relatively new, why are there so many contests on weekdays? Feel like Leetcode does this so much better (2 contests 12 hours apart from each other on weekends).

→ Reply
»
13 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Timings for India are just after lunch.

Perfect.

→ Reply
  • »
    »
    12 days ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    You seem to be in Australia though.

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

    After lunch if you manage not to sleep in the contest then it's perfect XD. And yes summer days another catalyst for sleep during afternoon.

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

So goooood time don't need to stay up late

→ Reply
»
12 days 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
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of luck everyone

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

Best of luck to all!

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

Just noticed it is 3 hours long contest.

→ Reply
»
12 days 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
»
12 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Best luck to all wish you all gain a good rating ;)

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

Perfect time for Asian region. It's 1801th contest in CF. Great!

→ Reply
»
12 days 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
»
12 days 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
»
12 days 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
  • »
    »
    12 days ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

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

    → Reply
  • »
    »
    12 days 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
»
12 days 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
»
12 days 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
»
12 days ago, # |
  Vote: I like it -8 Vote: I do not like it

Thanks for great contest, i think a lot of people get possitive rank:)

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

Div2B is a terrible problem

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

I will never take part in div1 again.

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

Very hard contest

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

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

→ Reply
  • »
    »
    12 days 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
  • »
    »
    10 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Until you notice the pattern in 1st and 3rd testcase.

    Set a[0][0]=548 and traverse over rows and columns separately and proceed like below.

    Code
    → Reply
»
12 days 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
  • »
    »
    12 days 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
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why fixing a maximum does not work in D?

→ Reply
  • »
    »
    12 days 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
    • »
      »
      »
      12 days 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
      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          12 days 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
          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            what was your mistake? im stuck at 71 test

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

    It works ig, U need to sort first element and iterate over first and check best for each first using a multiset.

    → Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 days 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
»
12 days 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
  • »
    »
    12 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
  • »
    »
    12 days 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
»
12 days ago, # |
  Vote: I like it +38 Vote: I do not like it

How to solve Div1D?

→ Reply
  • »
    »
    12 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    Spoiler
    → Reply
    • »
      »
      »
      12 days 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.cc/contest/1802/submission/196657563, I did the exact same thing which you are telling but got TLE.

      → Reply
      • »
        »
        »
        »
        12 days 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
        • »
          »
          »
          »
          »
          12 days 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
    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ahh that makes so much sense. Thank you.

      → Reply
    • »
      »
      »
      11 days 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
      • »
        »
        »
        »
        11 days 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
        • »
          »
          »
          »
          »
          11 days 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
»
12 days ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
  • »
    »
    12 days 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
  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    make every 2*2 block xorsum equals zero

    → Reply
    • »
      »
      »
      12 days 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
      • »
        »
        »
        »
        12 days 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
        • »
          »
          »
          »
          »
          11 days 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
          • »
            »
            »
            »
            »
            »
            11 days 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
      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i tried to make 0 in 2 by 2 blocks and then put in out matrix

        here my code for that `

         ll ans[n+1][m+1];
   for(int i=1;i<=n;i++){
     for(int j=1;j<=m;j++){
        ans[i][j]=512*(i)+j;
     }
   }

   for(int i=1;i<=n;i++){
     for(int j=1;j<=m;j++) cout<<ans[i][j]<<" ";
      cout<<"\n";
   }
        → Reply
  • »
    »
    12 days 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
    • »
      »
      »
      12 days 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
    • »
      »
      »
      12 days 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
  • »
    »
    12 days 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
  • »
    »
    12 days 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
  • »
    »
    12 days ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    What I did is

    Spoiler
    → Reply
»
12 days 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
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Participated after such a long time and clutched D , ahh feels good to get back to that feeling again

→ Reply
»
12 days 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
»
12 days ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    12 days 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
  • »
    »
    12 days 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
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve DIV2 B

→ Reply
  • »
    »
    12 days 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
»
12 days ago, # |
  Vote: I like it +15 Vote: I do not like it

Very bad statements ):

→ Reply
»
12 days ago, # |
  Vote: I like it -9 Vote: I do not like it

Bforces

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

The descriptions of problem Div2 A,B are terrible.

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

    please all of DIV 2 participants

    put a dislike to this round as the statement of Problem B was totally misleading and wrong.. i wasted 2hour just to think on it..

    and statement changed in the last one hour of round ...

    → Reply
  • »
    »
    12 days 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
»
12 days ago, # |
  Vote: I like it +46 Vote: I do not like it

The most difficult part of this round is to understand statement

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

Tired of reading long and unnecessary statements

→ Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 days 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
»
12 days ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve div1F?

→ Reply
  • »
    »
    11 days 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
    • »
      »
      »
      11 days 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
      • »
        »
        »
        »
        11 days 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
      • »
        »
        »
        »
        11 days 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
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

like a fish

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

Annoying and useless statements :(

→ Reply
»
12 days 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
  • »
    »
    12 days 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
    • »
      »
      »
      12 days 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
»
12 days 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
  • »
    »
    12 days 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
»
12 days ago, # |
  Vote: I like it +8 Vote: I do not like it

div2 B English statement make me so confused

→ Reply
»
12 days 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
»
12 days 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
»
12 days ago, # |
  Vote: I like it +23 Vote: I do not like it

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

→ Reply
»
12 days 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
»
12 days 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
  • »
    »
    12 days 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
»
12 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Please share some more problems like Div1 D.

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

Nice pretests！

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

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

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

f**king pretests of B.

→ Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Inappropriate time

→ Reply
»
12 days 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
  • »
    »
    12 days 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
  • »
    »
    12 days 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
»
12 days ago, # |
  Vote: I like it +29 Vote: I do not like it

One more day at Codeforces!

Spoiler
→ Reply
  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Second time I solve Div2ABCD. Thanks for the round!

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

very bad statement for B ):

→ Reply
»
12 days 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
  • »
    »
    12 days 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
    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Even tourist got FST

      → Reply
    • »
      »
      »
      12 days 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
    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what is FST

      → Reply
  • »
    »
    11 days 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
»
12 days 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
»
12 days 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
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

It it to difficult.

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

Can pretests be stronger?

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

weak pretests

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

My GM :(

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

Really disappointed in the contest dear Sir.

→ Reply
»
12 days 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
  • »
    »
    12 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    gyh bot/cf

    → Reply
  • »
    »
    12 days 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
  • »
    »
    12 days 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
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

OMG, 2 FST

QAQ
→ Reply
  • »
    »
    12 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    introspection
    → Reply
»
12 days ago, # |
  Vote: I like it +48 Vote: I do not like it

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

→ Reply
»
12 days 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
  • »
    »
    12 days 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
  • »
    »
    12 days 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
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Happy Newyear!

→ Reply
  • »
    »
    12 days 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
    • »
      »
      »
      12 days 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
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 days 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
»
12 days 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
  • »
    »
    12 days 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
  • »
    »
    12 days 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
»
12 days 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
»
12 days ago, # |
  Vote: I like it +21 Vote: I do not like it

This contest gives GreenGrape contests vibe.

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

FST-forces

→ Reply
»
12 days 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
  • »
    »
    12 days 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
»
12 days 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
»
12 days ago, # |
  Vote: I like it +17 Vote: I do not like it

I have an FST, but my place became better)

→ Reply
»
12 days 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
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hardest Div2B I've ever faced.

→ Reply
»
12 days 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
»
12 days 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
»
12 days ago, # |
  Vote: I like it +13 Vote: I do not like it

A really simple solution for Div1A / Div2C:

Spoiler
→ Reply
»
12 days 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
  • »
    »
    12 days 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
    • »
      »
      »
      12 days 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
      • »
        »
        »
        »
        12 days 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
      • »
        »
        »
        »
        12 days 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
      • »
        »
        »
        »
        12 days 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
        • »
          »
          »
          »
          »
          12 days 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
  • »
    »
    12 days 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
»
12 days 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
»
12 days 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
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Better edu rounds than weak pretests.

→ Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

seriously, I don't understand how hard it is to create strong pretests. If you have a good amount of testers, you can notice the test where they fail on, and prioritize those testcases. Except, you're making the pretests weak intentionally.

→ Reply
»
12 days 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
»
12 days 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
»
12 days 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
  • »
    »
    12 days 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
»
12 days 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
»
12 days ago, # |
  Vote: I like it +13 Vote: I do not like it

The statements made me feel dyslexic

→ Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Loved Problem C But Hate Problem B

→ Reply
»
12 days 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
  • »
    »
    12 days 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
    • »
      »
      »
      12 days 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
      • »
        »
        »
        »
        12 days 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
        • »
          »
          »
          »
          »
          12 days 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
»
12 days 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
»
12 days 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
»
12 days 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
  • »
    »
    12 days 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
  • »
    »
    12 days 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
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

why are the problems not accsesible right now?

→ Reply
»
12 days ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Nice contest

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

Is this round gonna be unrated?

→ Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

why everyone hated problem b ?? its a very nice problem .

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

    Well, many contestants were not able to understand the problem statement. Because simpler cases were explained, but tough ones weren't explained. So its obvious many hated the problem B for that :)

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

      even those simpler cases are not understandable

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

        Well problem was medium but explanation wasn't up to the mark for majority, that's all I can say then hehe :)

        → Reply
»
12 days 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
  • »
    »
    12 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    oops, I just saw it was xor not or.

    LOL

    → Reply
  • »
    »
    12 days 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
    • »
      »
      »
      12 days ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I don't know symbol of xor that's why i said!

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

        I did same mistake in Div 3 this year and got 9 wrong submissions on problem B only. Can feel u from deep of the planet Saturn

        → Reply
»
12 days 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
  • »
    »
    12 days 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
»
12 days 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
  • »
    »
    12 days 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
    • »
      »
      »
      12 days 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
  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    didn't you read the problem statements, can't you see how bad they are?

    → Reply
»
12 days 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
»
12 days 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
»
12 days 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
»
12 days 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
»
12 days 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
  • »
    »
    12 days ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    why in the world it can be unrated?

    → Reply
    • »
      »
      »
      12 days 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
      • »
        »
        »
        »
        12 days 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
      • »
        »
        »
        »
        12 days 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
»
12 days ago, # |
  Vote: I like it +9 Vote: I do not like it

C>D>E

→ Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

is this round rated?

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

    yup, if it wasn't rated they might have added another update that round will be rated and why? But since no such update is there, it's definitely rated and ranks will be updated too :)

    → Reply
  • »
    »
    12 days 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
»
12 days 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.cc/contest/1802/submission/196698368

→ Reply
»
12 days 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
»
12 days 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
»
12 days 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
  • »
    »
    12 days 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
»
12 days 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
»
12 days ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

Totally didn’t FST on Div1B / Div2D :(

Spoiler
→ Reply
»
12 days 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.cc/contest/1802/submission/196720503

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

Good problems, shit pretests.

→ Reply
»
11 days 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
»
11 days ago, # |
  Vote: I like it +7 Vote: I do not like it

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

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

Worst Contest!

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

FSTforces

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

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

→ Reply
»
11 days 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
  • »
    »
    11 days 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
»
11 days ago, # |