ch_egor's blog

By ch_egor, 4 months 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).

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/06/2022 12:55 (Moscow time) and will be based on both days of the Olympiad. Each division will have 6 problems and 2 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 cookiedoth, shishyando, gmusya, Tikhon228, ligaydima, Siberian, isaf27, I_love_myself, _tryhard, KiKoS, _overrated_ guided by cdkrot, vintage_Vlad_Makeev, GlebsHP, Zlobober, meshanya, ch_egor, grphil, voidmax, fedoseev.timofey, Endagorion and Helen Andreeva.

Thanks to DmitryGrigorev and KAN 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.

Also thanks to low_ and Jeffrey for providing an additional problems that helped to create (I hope) a balanced problem set for the round.

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

Div. 1:

  1. jiangly
  2. ABitstOCHASTIC
  3. maroonrk
  4. 137_345_2814
  5. Elegia

Div. 2:

  1. AC464
  2. Nephry
  3. andyzys
  4. Let_Us_Rebegin
  5. _JacderZhang_

UPD2: Editorial

 
 
 
 
  • Vote: I like it
  • +119
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it
Back at it again :')
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck everyone! :)

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

As a supporter I'd like some contribution pls thanks ^^

»
4 months ago, # |
  Vote: I like it -14 Vote: I do not like it

"Notice the unusual time"

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

(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)

My favorite part of a Moscow round is seeing this list grow one number longer.

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

    My favorite part of a Moscow round is problems with n <= 10^9 with n*sqrt(n) intended solution and Time Limit of 0.1 seconds.

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

Dear contest, I know that you and your siblings feature beautiful problems under short periods of time, which proves to be quite challenging. As a result the rating dropping haters downvote your announcement. Please try not to take this very seriously. the haters don't know what they are doing.

Regards, that one random contest orzer (and rating admirer)

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

Unlike other cf rounds, this one doesn't have testers

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

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

    I now firmly believe that words have power and can change life, I got FST on B :'(

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

gl everyone! My first round with green rating, hopefully i dont lose it after this one :)

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

Another Div $$$0.5$$$ / Div. $$$1.5$$$ round?

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

So much contest this week :)
Intresting!!

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

How many tester you want to make good prestests.

Admins : Yes

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

Notice the unusual time (is quite usual these days) :)

All the best everyone, have a positive delta!

»
4 months ago, # |
  Vote: I like it -23 Vote: I do not like it

Is it ranked? Or not?

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

The unusual timing struck back but fortunately, this time it's a Sunday.

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

great!!! thanks

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

glhf

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

Unusual time with unusual 20 minutes delay

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

Boycott russian olympiads until the war is over! How can they casually host an informatics olympiad while Ukrainian schools lie in ruins? snark already shows his solidarity by postponing GPs, you should do as well

»
4 months ago, # |
  Vote: I like it -25 Vote: I do not like it

Is it rated ?

»
4 months ago, # |
  Vote: I like it -21 Vote: I do not like it

PS — Unusual Timing

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

When we will get score distribution for the contest??

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

Only 40 minutes left, And the score distribution haven't been published!

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

    6 min Left and still no score distribution !! Does Anyone has idea What's going on

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

Good luck everyone!!!!

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

first contest without score distribution? or waiting more delays?

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

good luck everyone!

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

when we'll get to know about score distribution :*

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

SCORE DISTRIBUTION?

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

Damn!! what a contest..Hardforces.. Logic for B??

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

    Sort the array. Take the sum of all elements except the last one. For one football, this sum should be greater than the largest element. Else the count is the difference between those 2.

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

      isn't this the logic for A?? i want B

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

        My bad. Edited the comment

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

        Corner case: if all elements of the array are 0, print 0.

        Else, Calculate the sum of the array and call it s. Let ans be 1.

        Then iterate through the array and make ans equal to max(ans, a[i] — (s — a[i]));

        The idea is that, for each player, you cannot make him pass the ball to himself again but only to the other players, and that means that for one ball, he can do only min(a[i], s — a[i]) passes. For the rest of the passes he has to kick another ball for each hit.

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

          More than that, we have to consider only the maximum of the array. The following code passes:

          const auto mx = *max_element(a.cbegin(), a.cend());
          const auto s = accumulate(a.cbegin(), a.cend(), int64_t(0));
          if (s == 0) {
              return 0;
          }
          return max(int64_t(1), 2 * mx - s); // 2 * mx - s == mx - (s - mx)
          
      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        sort the array and if a[n] > 1+a[1]+a[2]+...a[n-1],the answer is 1+a[n]-(a[1]+a[2]+...a[n-1])-1,otherwise you can always use at most one ball to complete the session,the answer is 1 or 0.

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

    If the highest value — 1 <= rest, then answer is 1.

    Else while (highest value — 1> rest) { highest value -= 2; rest -=1; ans++; }

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

Problem C & D , both seem very interesting.

Any hints on how to solve C? Also , can D be solved using two pointers method? if so then how , or any other method of solving , if you can help, Thank you !!!!

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

    For C, it seems to be summing the same colors so that we only deal with a row vector and a column vector.

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

    Do you see how you can solve this in 1-D?

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

    Try to think in the way we calculate prime numbers using sieve

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

    For Div2C You can also do the following approach. Solve it for each color separately. Observer that you can calculate x and y parts of M distance separately. WTLOG for x coo: sort the x values and build the solution while processing x-coordinates one by one. If you know the distance needed for i-1 points you can use it to calculate the distance needed for the ith.

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

D logic? can we do it in O(t*c)?

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

How to solve Div1B?

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

    brute force from 1 to sqrt(C)

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

    Sort a. Now, for each unique a_i, iterate over all possible quotients k when a_i divides some a_j. So a_j has to be between [a_i*k, a_i*k + a_i-1]. Check if there is any number in this interval using binary_search. If k is not found in a and there exists an a_j in given interval then "No". I wonder if this would TLE on system tests.

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

    Let us assume that the value of floor(x/y)=a.

    Then the maximum number of distinct values of a for any fixed y is c/y.

    We can bruteforce for all pairs of y and a in ClogC. Once we have bruteforces we have to find if any other number from the array(i.e. x) gives us the required dividend a . This can be done using prefix sum of the frequencies.

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

    If you fix the value of x, then if you take the value of y in range x...2x-1 floor(y / x) will be the same. So the solution is very similar to Sieve of Eratosthenes. First you fix the value of x, then you fix y's like (x, 2x, 3x...) and if there is some number in range [y,y+x-1] you should check whether (y/x) also appears in our array. You just can calculate cnt_x for every x and then calculate prefix sums on this array. Sorry for my bad English.

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

      Bro can you help me...I did the same still tle 148674159

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

        Instead of the map you can use something like a frequency array

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

          Now it's showing tle on test 3 148682603

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

          Now it worked after using unorderedmap 148682987 What was the difference in map/unorderedmap/freqarr ?? map and freqarr didn't work. But u_map worked :|

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

    Problem statement: The array is good if for each $$$x$$$ and $$$y$$$ (s.t. $$$y \geq x$$$), $$$\lfloor{y/x}\rfloor$$$ should be part of array as well.

    First, the number 1 should be present in the array.

    For every number $$$x$$$ in the array, the number of elements $$$\lfloor{y/x}\rfloor, \text{where } y \geq x$$$ is at most $$$c/x$$$ where $$$c$$$ is the largest value in the array.

    If we just iterate for each $$$x, y$$$, the time complexity will be $$$\mathcal{O}(n^2)$$$.

    Instead we can iterate on $$$x, j$$$ where $$$1 \leq j \leq c/x.$$$ For a fixed $$$j$$$, if there exists a number $$$y$$$ s.t. $$$\lfloor{y/x}\rfloor = j$$$, then $$$j$$$ must also exist in the array.

    The condition to check if there exists a number $$$y$$$ s.t. $$$\lfloor{y/x}\rfloor = j$$$ can be translated to check whether there exists an element in the range $$$[j * x, j * (x + 1) - 1]$$$. This can be done by prefix sums.

    Overall time complexity of this algorithm will be $$$\sum_{x=1}^{c} \lfloor{c/x}\rfloor $$$ = $$$\mathcal{O} (c \log c)$$$

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

      Why 1 should be present in the array?

      Answer should be yes whenever we have 1 in our array.

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

    Almost straight up bruteforce in $$$O(N\sqrt{C})$$$ passes: 148611843

    UPD: I am not sure about correctness of this approach, if someone could prove it or hack it.

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

      I thought $$$O(10^{6}\sqrt{10^{6}})$$$ $$$=$$$ $$$1e9$$$ gets $$$TLE$$$ $$$:/$$$

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

      Hey, can you explain the j<i&&j*j<v[i]; part in your code, please? How can I differently type that? I tried to do D like you, I just changed that part, but it fails on 31st test.

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

        Rephrase it as: check only first $$$X$$$ numbers, where $$$X = \sqrt{v[i]}$$$

        You can rewrite it also as: $$$j < min(i, \sqrt{v[i]})$$$

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

          Napokon AC, hvala brate puno! Vrlo gotivno rjesenje imas. :D

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

Looks like my D is $$$O(M \log^2)$$$ but barely fits within TL on pretests. I should be able to make it $$$O(M \log)$$$ but I already spent way too much time on it and was rushing to save at least some points.

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

Problem B was confusing!

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

5 seconds before the end of the contest, I clicked the submit button and... my solution was not sent... Sad...

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

Div2 A wording could have been better. I got WA and couldn't solve the problem because I thought we could make multiple jumps just could not repeat jump of size x.

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

    SAME XD , i forgot to notice that we can only jump once, resulted in 4 WA's thinking what am i doing wrong.

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

      it was written in bold so problem writers cannot be blamed for it :D

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

        Yup ::_;; my eyesight too bad xD

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

        this part is in bold "no more than"? what does that even mean?

        It would be much clearer if this part was bold "you can make a non free jump only once"

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

          no more than one means either 0 or 1

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

      literally same

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

    me too. It was confusing.

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

    wording could have been better? it's literally there, they just put no more than in bold instead of once, your reading should have been better

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

Both D and E are hard to implement .

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

Div 2A should've been translated better, the statement was complicated man ;(

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

    Exactly , use a better translator , not solving A within first few minutes really spoils the mood

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

What even was B? Looked very confusing. Almost cried seeing 4k people solve it and here I was without even any direction T_T

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

I made video Solutions, for Div2 A-E

»
4 months ago, # |
  Vote: I like it -61 Vote: I do not like it

No more contests in unusual timing please. It conflicts with many people's routine and only a few people participate. Also contests around this time turns out to be bad

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

    I am curious to know, on what basis are the timings of a contest decided? Is it according to the availability of contest admins & testers (for clarifying problem statements etc.)?

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

how to solve div2 c?

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

    calculate fox x and y

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

      thank you,I think I get it

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

        calculate ans fox x and y seperatly

        colorx[i] — list of coordinates x with color i

        sort(colorx[i])

        ans +=sufcolorx[i][j] — colorx[i][j]*(colorx[i].size()-j+1);

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

Div1C/Div2E looks like a somewhat classical problem, but i could only think of a quadratic solution. Could anyone give me some hints?

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

    My idea: calculate # of strings such that the first i characters from each one are equal to the first i characters of t. then, i+1-th character from every string must be lexographically smaller than the i+1-th character of t. You also have to use a data structure like bit to know how many "good" characters there are for each i and compute modular inverses for some products.

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

    i used segment tree for problem E

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

Implementation contest :(

Div1F doesn't seem so hard(If it's correct that after contracting three-edge-connected components as single nodes, the graph would be a cactus.), but it requires tooooooooooooo much implementation.

It also needs some effort to code Div1E.

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

Where is the Solution?

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

In Problem F, I figured out how to solve the problem on cacti, but do not know how to find 3-edge connected components :)

My opinions:

All problems are decent OI-style problem, but E and F just do not fit into Codeforces contests due to implementation issue. It will be better to make F on cacti.

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

Why does this TLE?

https://codeforces.com/contest/1649/submission/148571491

It's O(n)

EDIT — it AC'ed now, unsure why it was TLE earlier.

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

    Next time try to store sum(l) and max(l) so you only compute them once

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

Well, I am so sad of getting FST on B -__-, Why weak pretests :(((

Why there's no test of maximum n in pretests ?? Why?? I just changed maxn to 1e5 and it got AC :(((

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

What the ridiculous test in Div.1 C, if you don't take modulo in the end, you will print 998244353 and get fst. :(

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

    I couldn't imagine that someone can come with such a test so I just ignored it during the round :((

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

      It's a common thing though and happens all the time in EDU rounds, as such tests are not that hard to come up with. I remember sum did a whole lot of hacks in some recent EDU using this modulo flaw in a couple hundred solutions.

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

    Almost half of my friends are hacked because of it.fortunately,I didn't lock the problem...

    thanks for STRONG pretest!

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

I can't find some sort of report button in messages. Should I report that somewhere and in what way?

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

    Send him your code for B now. Also, don't forget to apologise for not sending your code during the contest. :D

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

    Edit:Sorry for the Advice

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

    Why people are so desperate .. Come on man work hard and be proud of yourself . This guy surely don't have any self respect . Got left ignored for whole contest . Damn guys Life ain't that easy. Don't make it more easier ..

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

148588961 I had FST in a test already had on pretest (test 13) ???? MikeMirzayanov can you rejudge my submission pls. 148606321 I have accepted after contest with exactly code

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

Although I got fst on Div.2 E, my ranking didn't drop a lot, because many ahead of me got fst too. I think this contest showed a good way to deal with the problem of too many people fst.

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

    But on the same problem, Div.1 C, I was not able to keep my rank after getting fst. I'll end up getting a negative rating change. :(

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

    What is fst?

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

148593938

Can some one hack this?

Or is it correct?

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

weak pretest TAT

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

I think Div.2 B is an interesting problem. In my opinion it's even more difficult than C,D and E. I spent more than 40 minutes on it. :D

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

how to solve 1D using segment tree. plz help

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

Back to Master again,Thank you :)

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

weak pretests in problem D. I use this code to pass the pretests.

code

In this statements,the elements in the vector aren't changed,and I suppose it changed and do something else. It passed the pretests,but fst on test 24.

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

D: rewrite the objective function as "maximize{$$$l<r$$$} $$$a_l + b_r$$$ — (cost to cover $$$[l, r)$$$)"

I used divide and conquer to cope with the restriction "$$$l<r$$$" in each step, make graph with edges

  • $$$l$$$->$$$r$$$ with cost $$$k$$$

  • $$$x$$$->$$$x-1$$$ with cost $$$0$$$

  • S->$$$l$$$ with cost $$$-a_l$$$

  • $$$r$$$->T with cost $$$-b_r$$$

calculated the shortest path from S to T In order to shrink time complexity, I had to care edges outside $$$[l, r)$$$ (only $$$\mathrm{O}(r-l)$$$ edges have to be taken into consideration)

Idea itself was interesting to me, but implementation was too heavy for an almost retired person.

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

    to a graph,nice idea!

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

    We found a lot of interesting solutions to this problem, almost half of participants' successful submissions (it was like 5 out of 10) on the olympiad had it's own approach. And all of those solutions weren't easy to code as well.

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

contest is good , except some meaningless corner case which leads to FST

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

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

Codeforces is not trash bin.

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

How to hack problem C in div 1?

How to make the answer multiple of $$$998,244,353$$$ ?

»
4 months ago, # |
  Vote: I like it -31 Vote: I do not like it

ya problem setters really love weak samples and pretests... i dunno the reason.

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

jiangly's codes are so clean ...like seeing latex text

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

Did someone understand what is special in test 53 in div1 C? I can't get it for now

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

I made a submission for problem A. Link I am confused as to why it's failing for the testcase:

1
6
1 0 1 1 0 1

I think its answer should be 4 but it's given 5. Can someone explain how 5 is the answer for this testcase ?

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Cannot describe it with any words.jpg

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

can somebody just explain what does the problem A means; i am not understanding when is free and when is not; Are the jumps free onle at ends;

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

    When the next number is 1, you can just move there for free. If not you need to jump and pay. You can only do such jump once so what you want is to jump over all segments of zeros and get to some 1 from which you can just walk to the end of the array. Hope this makes sense. I was also confused by the problem statement.

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

If you are/were getting a WA/RE verdict on any of the problems from this contest, you can get a small counter example for your submission on cfstress.com

Problems added: "A, B, C, D, E, F" from Div-2, which translates to "A, B, C, D" in Div-1.

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

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

problem A really bad statement..

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

My exactly same code for div2 D got TLE during system test and AC after the contest, can this be rejudged? :'(

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

Hello, please hellp me. I need a hint for problem C. I have no idea

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

    try to solve it for x and y separately

    you can get a list for each color using map/unordered map (i used map) then you iterate through the map and do following thing:

    At first, you have to notice that all points of the certain colour are already sorted by x; you can calculate the distance from the first point, then calculate for others using that value then you have to sort all the points by y and do previous steps again

    i didn't explain the whole implementation, but you can see my submission there: https://codeforces.com/contest/1649/submission/148590975

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

what are the downvotes for on the post this time? did just a lot of people not like the div2A statement?

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

    Weak pretests perhaps? There were quite a bit of people getting FSTed in Div1C.

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

    Ikr, I feel there is much better way of conveying you are allowed to jump once

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

I wanted to be pupil today; Bad luck, (TLE on test case 9, Problem-"C")

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

I have a question in problem A div 2 why this case result is 5, not 4?
6
1 0 1 1 0 1

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

    Because you count the land on which you jump too.

    If it was 4, then it would count that you jumped on the 0 (that is on position i = 4), not on 1 (that is on position i = 5)

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

Thanks for great round!

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

You need tighter controls on cheaters.

»
4 months ago, # |
  Vote: I like it -12 Vote: I do not like it

This Div2 the worst to me!

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

Codeforces Round #776(Div.3) is around the corner and i was wondering as a newbie with not so much experience would you suggest me to participate? I say this because it's Div.3 and i should solve many prolems to get a positive delta so the pressure is high.

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

Can anyone tell me in Div2 problem D why answer of 1 3 3 7 should be no as 3/1 = 3 which is present in the array.

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

    any pair... 7/3=2 not present in the array

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

      Thanks, I thought that if any pair satisfy the given condition then array will be integral array