ch_egor's blog

Codeforces Round #775 (Div.1, Div.2, based on Moscow Open Olympiad in Informatics, rated)
By ch_egor, 3 years 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, talant, KiKoS, _overrated_ guided by cdkrot, vintage_Vlad_Makeev, GlebsHP, Zlobober, meshanya, ch_egor, grphil, voidmax, fedoseev.timofey, Endagorion and Helen Andreeva.

Thanks to gop2024 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. QuietBeautifulThoughts
  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

Comments Comments (150)
| Write comment?
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Back at it again :')
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck everyone! :)

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

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

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

"Notice the unusual time"

→ Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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)

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

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

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

→ Reply
  • »
    »
    3 years 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 :'(

    → Reply
»
3 years 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 :)

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

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

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

So much contest this week :)
Intresting!!

→ Reply
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

How many tester you want to make good prestests.

Admins : Yes

→ Reply
»
3 years 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!

→ Reply
»
3 years 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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Unusual time with unusual 20 minutes delay

→ Reply
»
3 years 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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    Everyone understands your concerns, but I don't know how it is going to help.

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

When we will get score distribution for the contest??

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

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

→ Reply
  • »
    »
    3 years 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

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

Good luck everyone!!!!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

first contest without score distribution? or waiting more delays?

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

good luck everyone!

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

SCORE DISTRIBUTION?

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

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

→ Reply
  • »
    »
    3 years 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.

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

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

      → Reply
      • »
        »
        »
        »
        3 years 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.

        → Reply
        • »
          »
          »
          »
          »
          3 years 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)
          → Reply
      • »
        »
        »
        »
        3 years 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.

        → Reply
  • »
    »
    3 years 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++; }

    → Reply
»
3 years 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 !!!!

→ Reply
  • »
    »
    3 years 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.

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

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

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

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

How to solve Div1B?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -29 Vote: I do not like it

    brute force from 1 to sqrt(C)

    → Reply
  • »
    »
    3 years 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.

    → Reply
  • »
    »
    3 years 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.

    → Reply
  • »
    »
    3 years 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.

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

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

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

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

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

          Now it's showing tle on test 3 148682603

          → Reply
        • »
          »
          »
          »
          »
          3 years 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 :|

          → Reply
  • »
    »
    3 years 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)$$$

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years 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$$$ $$$:/$$$

      → Reply
    • »
      »
      »
      3 years 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.

      → Reply
      • »
        »
        »
        »
        3 years 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]})$$$

        → Reply
»
3 years 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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B was confusing!

→ Reply
»
3 years 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...

→ Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years 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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Yup ::_;; my eyesight too bad xD

        → Reply
      • »
        »
        »
        »
        3 years 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"

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

          no more than one means either 0 or 1

          → Reply
  • »
    »
    3 years 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

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

Both D and E are hard to implement .

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

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

→ Reply
  • »
    »
    3 years 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

    → Reply
»
3 years 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

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

I made video Solutions, for Div2 A-E

→ Reply
»
3 years 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

→ Reply
  • »
    »
    3 years 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.)?

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve div2 c?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    calculate fox x and y

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

      thank you,I think I get it

      → Reply
      • »
        »
        »
        »
        3 years 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);

        → Reply
»
3 years 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?

→ Reply
  • »
    »
    3 years 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.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it -9 Vote: I do not like it

    i used segment tree for problem E

    → Reply
»
3 years 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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is the Solution？

→ Reply
»
3 years 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.

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

Why does this TLE?

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

It's O(n)

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

→ Reply
  • »
    »
    3 years 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

    → Reply
»
3 years 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 :(((

→ Reply
»
3 years 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. :(

→ Reply
  • »
    »
    3 years 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 :((

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
  • »
    »
    3 years 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!

    → Reply
»
3 years 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?

→ Reply
  • »
    »
    3 years 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

    → Reply
  • »
    »
    3 years 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 ..

    → Reply
»
3 years 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

→ Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years 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. :(

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

    What is fst?

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

148593938

Can some one hack this?

Or is it correct?

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

weak pretest TAT

→ Reply
»
3 years 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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve 1D using segment tree. plz help

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Back to Master again,Thank you :)

→ Reply
»
3 years 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.

→ Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    to a graph，nice idea！

    → Reply
  • »
    »
    3 years 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.

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

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

→ Reply
»
3 years 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!

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

Codeforces is not trash bin.

→ Reply
»
3 years 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$$$ ?

→ Reply
»
3 years 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.

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

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

→ Reply
»
3 years 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

→ Reply
»
3 years 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 ?

→ Reply
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Cannot describe it with any words.jpg

→ Reply
»
3 years 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;

→ Reply
»
3 years 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.

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

problem A really bad statement..

→ Reply
»
3 years 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? :'(

→ Reply
»
3 years 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

→ Reply
  • »
    »
    3 years 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.net/contest/1649/submission/148590975

    → Reply
»
3 years 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?

→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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

→ Reply
  • »
    »
    3 years 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)

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for great round!

→ Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years 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

      → Reply