By dargelirli, history, 4 weeks ago, translation, In English

Hi all!

This weekend, at Dec/20/2020 18:05 (Moscow time) we will hold Codeforces Round 692. It is based on problems of Technocup 2021 Elimination Round 3 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup 2021 website and take part in the Elimination Round.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

The Elimination Round authors are neckbotov and dargelirli. Thanks to Nebuchadnezzar and KAN for their coordination. Also huge thanks to testers for their invaluable help: isaf27, 300iq, Kaban-5, low_, Shinchan01, wiwitrifai, Ashishgup, spar5h, Nemo, Gauravvv, Vax, XLor, Um_nik, ADJA, jiufeng, RobeZH, Daryusz, antontrygubO_o, Normie28, rkm62, gratus907, Manik!

Have fun!

Elimination Round will feature 7 problems, preliminary costs are
500 — 1000 — 1750 — 2000 — 2250 — 2750 — 3250.

Div. 2 will feature 6 problems, preliminary costs are
500 — 1000 — 1750 — 2000 — 2250 — 2750.

Div. 1 will feature 6 problems, preliminary costs are
750 — 1000 — 1250 — 1750 — 2250 — 3000.

The analysis is published.

The round is over, congratulations to the winners!

Technocup 2021 - Elimination Round 3

  1. almogwald
  2. serg3000
  3. Pechalka
  4. denisrtyhb
  5. 777

Codeforces Round #692 (Div. 1, based on Technocup 2021 Elimination Round 3)

  1. EricHuang2003
  2. jiangly
  3. hos.lyric
  4. ecnerwala
  5. ugly2333

Codeforces Round #692 (Div. 2, based on Technocup 2021 Elimination Round 3)

  1. KanbeKotori
  2. xmt
  3. RNG-Ming
  4. YANK01
  5. Kalecgos
 
 
 
 
  • Vote: I like it
  • +295
  • Vote: I do not like it

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

))

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

Don't forget to notice the unusual start time!!!

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

I think some registration cleanups need to be done after the rating update from the previous contest

https://codeforces.com/contestRegistrants/1465?order=BY_RATING_DESC

https://codeforces.com/contestRegistrants/1464?order=BY_RATING_ASC

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

Hoping for a good contest :)

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

I am unable to type in the city name in the Technocup registration page(the input box isn't working ).Can anyone help?

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

As a person who is familiar with the dargelirli and neckbotov, I think that Russian-speaking high-school students are in good hands. I can assure you that everything will be all right with the contest, because dargelirli's passport is in my pocket.

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

How can I improve?

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

I hope that I reach Pupil after this contest.

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

As a tester, I say that Problems are Interesting :)

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

In letter from Mail.ru was said that contest will start 20.00 MSK, but here there is other time.

»
4 weeks ago, # |
Rev. 4   Vote: I like it -58 Vote: I do not like it

.

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

    There are literally thousands of blogs related to your question (Google?) and why are you asking this here in the contest announcement blog? :/

    P.S: registered 7 months and still new KEKW

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

Scoring distribution??

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

    Elimination Round will feature 7 problems, preliminary costs are 500 — 1000 — 1750 — 2000 — 2250 — 2750 — 3250.

    Div. 2 will feature 6 problems, preliminary costs are 500 — 1000 — 1750 — 2000 — 2250 — 2750.

    Div. 1 will feature 6 problems, preliminary costs are 750 — 1000 — 1250 — 1750 — 2250 — 3000.

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

I am gonna reach pupil.

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

Is it just me, or does the scoring distribution of Division 2 seems a bit scary?

»
4 weeks ago, # |
  Vote: I like it -37 Vote: I do not like it

is it rated?

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

    Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

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

*Me after doing A and B: Let's check comment section

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

Pretest 4 ruined the party for me... Looking forward to the solution to this one! :D

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

I have a doubt, for a problem if i did wrong submissions and didn't solve that question in the contest, will these wrong submissions have any effect on my ranking?

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
The comment removed because of Codeforces rules violation
»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

What's test 5 in div2C (after contest)

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

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

Can C be done using number of cycles count?

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

    Yes, initialise ans = m, for every cycle increment ans, for every rook at (i, i) decrement ans

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

      Oh! I got stuck in debugging the same!!

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

      Implemented this and got WA on test 5. How?

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

        Try this test case — 1 5 4 1 2 2 3 4 1 5 5
        Correct answer is 3. Many incorrect codes will output 4.

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

          Thanks! My code is giving WA on this. I understood my mistake.

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

          Implementation mistake. How to implement correctly?

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

            I wrote a recursive solution Code

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

            I also done it using number of cycles count and same i also got WA in pretest 5 . Maybe you also done same mistake . During checking cycles , some cycles are not exactly cycles. ( means 1 2 3 but 3 to 1 not possible ) But in last i changed and it got accepted .

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

          my answer is 3 and i'm still WA on test 5

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

            Same for me. Was it wrong answer on the 45th output? Did you find what was the error?

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

              i'm WA on the 213rd output

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

                OMG okay. I figured out my issue though. Initialization problem.

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

    Yep, I passed the pretest. Don't know about system test though.

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

    Yeah, any rook on the diagonal contributes 0 to the answer.

    Any rook not on the diagonal contributes 1 to the answer.

    Additionally, any cycle contributes 1 to the answer.

    This is optimal because moving a rook already on the diagonal off the diagonal is a waste of moves. Any rook not on the diagonal needs at least 1 move to get on the diagonal. And any cycle of $$$n$$$ pieces needs $$$n+1$$$ to resolve (you need to move a piece to a free column/row to remove the cycle, put $$$n-1$$$ pieces on the diagonal, then move back the original piece to the diagonal, for a total of $$$n+1$$$ moves)

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

      Can you please share your code?. Mine is bit lengthy and unreadable.

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

        Not sure if you can see it now but it should be visible once system tests finish (and I hope mine passes :P link)

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

Aah! This $$$D2C$$$ today:

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

how to solve c??

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

    ignore all points on diagonals. for every other point, connect every 2 sharing x or y.

    for each connected component, check if at least 1 point can be moved to diagonal in 1 move.

    if so, ans += no of points in the component. otherwise, ans += no of points in component + 1

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

      did the exact same thing , got wrong answer on pretest 5 . any case i may be missing ?

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

    Some hack tests:

    5 4

    1 2

    2 1

    4 5

    5 4

    Then the answer is 6.

    For each rooks $$$(x, y)$$$, add an edge between $$$x$$$ and $$$y$$$.

    For each connect component, if it is a tree, the answer of this component is the number of rooks. And if it is a cycle, the answer of this component is 1 + the number of rooks.

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

      this approach also giving wrong answer

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

        Oh, maybe you forget considering $$$(x, x)$$$ ? And this rook is ok, and needs no move.

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

      can u explain the intuation behind it? pllzzzzzzzzz

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

        When I tested this round, I firstly guess the answer is $$$m$$$ or $$$m+1$$$ (remove rooks at $$$(x,x)$$$).

        The difference between this two case is that the set of x coordinates and the set of y coordinates. You can see that if these two sets are same, then the answer is $$$m+1$$$, otherwise $$$m$$$. Like 2 rooks $$$(1,2)$$$ and $$$(2,1)$$$, the answer is 3 because $$${1,2}={1,2}$$$. If the first rook $$$(1, 2)$$$ wants to go to $$$(1, 1)$$$, but $$$(1, 1)$$$ is banned by $$$(2, 1)$$$. And if the first rook wants to go to $$$(2, 2)$$$, $$$(2,2)$$$ is also banned by $$$(2, 1)$$$. Is it like a cycle?

        And 2 rooks $$$(1, 3)$$$ and $$$(2, 1)$$$, the answer is 2. The first rook goes to $$$(3, 3)$$$, and $$$(2, 1)$$$ goes to $$$(2, 2)$$$, this may be a chain.

        However, the above conclusion does not work only when the board can be split into many parts, like the above hack test. And then add an edge between x coordinate and y coordinate may be a trick with DSU. There is a similar problem 1013D - Химическая таблица. Finally, if you do this, you can get the above conclusion.

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

          Can u explain how you are taking an edge between the two cells of the board?

          If you can explain with your above example it would be really helpful.

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

      Solved. Thanks

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

How to do D2C ?

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

I think Div 1 Problem E can turn into : the probability of choosing some number from the sg numbers that =0. Am I right?

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

    If I am right , how to compute? Using basis?

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

    It turns into "compute probability that the resulting Grundy number is $$$x$$$, for each $$$x$$$. You can write a classic recurrent probability formula $$$p(x) = \frac{(x = 0)}{N+1} + \sum_{i=1}^N \frac{1}{N+1} p(x \oplus g_i)$$$ and turn it into Gaussian elimination since the Grundy numbers of vertices are $$$0 \le g_i \lt 512$$$ (approx. $$$\sqrt{M}$$$).

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

      I'm so sad, during the contest I (wrongly) concluded that the grundy values can only be 0 and 1, therefore we have just 2 states in our linear system, and Gaussian elimination isn't needed Q_Q

      Followup question, which might be stupid: is it true that under modulo M, if you have $$$a = P_a*Q_a^{-1}$$$ and $$$b = P_b*Q_b^{-1}$$$, and you take $$$c = a * b $$$ $$$=$$$ $$$P_c*Q_c^{-1}$$$, that the $$$P_c$$$ and $$$Q_c$$$ are automatically coprime and you never need to do any GCD-ing?

      I think it is but I'm not 100% sure, thanks.

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

        You should notice that modulo $$$M$$$, a fraction $$$p/q$$$ is the same as $$$pa/qa$$$ for any integer $$$a$$$ coprime with $$$M$$$. We don't care if the numerator and denominator are coprime with each other, only that the denominator is coprime with $$$M$$$ — which makes sense, they represent the same thing. You'd only care about the exact values when printing fractions or dealing with some operations like "add square of denominator to numerator".

        Of course the Grundy values aren't just 0 or 1, take a semicomplete DAG.

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

      So the time complexity of the Gaussian elimination part is $$$O(M\sqrt M)$$$?

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

        Yes,it can pass in $$$O(M\sqrt M)$$$. Though I found this dp transformation in the contest,but I didn't realize the size of dp status is up to $$$\sqrt M$$$(Maybe I'm not familiar with sg numbers),and I focus in finding the probability of "Xor equal to zero".In fact I have never seen the problem which need Gaussian elimination to update dp. It's a good problem ,thanks!

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

Do you know those annoying implementation problems that have like 100 cases? Well, C is the perfect example of it. :))

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

    C is a graph problem.

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

      can you tell your approach

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

      I think it can also be done using arrays (to find cycles).

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

        Yep storing y coordinate for every x coordinate and then looping till you get the initial x or some x which has no y. If you get your initial x you found a loop otherwise you didn't. Keep marking the visited vertices.

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

    How? :/

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

What's the solution for Div2C/Div1A ? I did it by counting the number of cycles formed in the graph when each rook position (x,y) is connected to (x,x) and (y,y), and then added it to the number of rooks not on the main diagonal.

I'm sure there must be an easy solution.

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

    mine is also the same I don't know why it's getting the wrong answer

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

    For each $$$(i,i)$$$, connect the rook in row $$$i$$$ with the rook in column $$$i$$$ with an edge. Discard self-loops. The resulting graph is a union of cycles and paths, the answer is number of vertices + number of cycles.

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

      can explain the intuition behind it??

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

        Take a path. You can move one rook from one end to the diagonal, shortening the path. For a cycle, you can't do that, so you need at least one extra operation with an unused row/column ($$$M < N$$$ so it's always possible), and using that operation turns this cycle into a path.

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

Worst Div2B ever. I thought I'd get TLE with simple brute force approach but then I looked at the number of submissions.

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

    how does that make Div2B worse if lot of people solved it fast and you didn't

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

      Because a lot of people (including me) solved it by looking at speed at which people were getting AC.

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

        How to solve B?

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

          Keep increasing n until you find the one satisfying the required property.

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

            is this a joke?

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

              Only after you get AC.

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

                I need to look at the constraints more

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

                  There exists at least one valid answer every $$$9!$$$ which equals $$$362880$$$. To be more precise, LCM of $$$1, 2, 3, 4, 5, 6, 7, 8, 9$$$ is $$$2520$$$, so at least one valid answer exists every $$$2520$$$. That's why you can do a linear search.

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

                  I wish I had thought this. I wrote the correct ans and them keep worry for next 2 hrs hope system test won't break my solution.

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

          Every 2520th number has this property, so just brute force for each number from N to the next multiple of 2520. You could have also run a simple while loop, but that gives no proof to why it won't TLE.

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

            For anyone wondering how 2520, it is the lcm of 1 2 3 4 5 6 7 8 9.

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

        standings are available to everyone so you can see and guess whatever you want.Though i proved myself .

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

          "standings are available to everyone so you can see and guess whatever you want" ==> And when whatever = solution, that makes a problem worse.

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

      I'm damn sure 90% of the people solved B without even thinking of its complexity ,more like they just guessed it and you dont't expect it from DIV2B level problem.

      Btw were you 100% sure that your code will get AC and not get TLE verdict?

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

        yes i was 100% sure . I calculate 9! and used similar to pigeonhole principle to prove it .

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

        Well I was sure, but again who knows about such a strict time complexity.

        I checked we would get an answer in max 2520 iteration since 5*7*8*9 would include all the numbers in it. But again instead of using 2520 I used 3000 which sadly made me cost -167 rating :(

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

      Good to see I am not the only one who is afraid to implement a brute force solution. I thought about brute force after just reading the problem but i was afraid it might give me TLE. But I did submit it and got ac

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

    Same bruh.... it was only after I saw the brute force implementations that I realized that only a maximum of 2520 numbers needed to be checked. :") I should've moved on to C. :"(

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

    The lcm of numbers from 1to9 is 2520 so it does not take more than 2520 for each test case if one does by simply increasing n and checking its fair or not

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

    I was worried as well, but i've tried generating several cases and noticed that the number of iterations would always be pretty small, hence a brute force would pass.

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

    LCM of first 9 natural numbers is 2520. So brute force will work.

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

Solved A, B , D in last 10 minutes it was thrilling experience.

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

Found Div2D to be not that difficult. Don't know why so fewer solutions.

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

I started 1hr late, solved A and B in <20mins and then lost hope after C and then went to play chess. Does C require some advanced data structure or algorithm?

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

    I don't think it requires some advanced shit. I think it's just something simple that we did not quite figure out.

»
4 weeks ago, # |
  Vote: I like it -137 Vote: I do not like it

why do you use 1e9+7 in D and 998... in E? congratulations, you have trolled me. I hope your problemsetting career has ended today.

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

    Congratulations for not copypasting modulos.

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

      There should have been an example testcase for D which checks for the correct modulo.

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

        Some testers noticed that but we were short on time and I didn't want to change anything. Definitely a thing to consider when problemsetting.

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

        You can't really give big tests in samples.

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

          Actually you can, as a downloadable file.

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

      i was low on time after coding D so i forgot to recheck the modulo...

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

        You're not supposed to "recheck". You're supposed to copy-paste. If you did that, you'd have more time too.

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

    I should've used Zashikhin prime. I'm deeply sorry for your disappointment which I believe is immeasurable.

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

      unfortunately, this is another case because I haven't used any templates

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

    Do you also ignore other parts of statements when solve? I wouldn't write it in this way if you weren't so aggressive. You should try to be more polite

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

      Do you also ignore other parts of statements when solve?

      Tell it to Errichto (comment)

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

      And if I politely asked, "why do you use 1e9+7 in D and 998... in E?", would you apologize?

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

        You impolitely hoped that the authors' problem setting career has ended today. I agree that it would be better to use the same modulo in both problems. I could apologize before someone else who is not so toxic

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

I got absolutely destroyed!

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

My solution to D1C passed the 21 pretests but I found a NullPointerException hack right after contest ended :'(

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

Second day in a row with E<D<C XD

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

    Big fan of yours :)

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

    I found C pretty easy. The last 2 signs obviously have to be + and -, but then for any string, we can always proceed from the last operation and "merge" a sign into the next sign if they're different, so that lets us turn any sequence of — to one -, any sequence of + (except the last, which is fine here) to +, and when we're left with +-+-+, that can be reduced to + as well. The rest is some careful implementation.

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

Can anyone prove why brute force works in B? I calculated such numbers upto 10, 000 only to find a pattern!

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

    LCM of all digits from 1-9 is 2520. So max 2520 iterations

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

    lcm of 1,2,3..9 is 2520. So it is guaranteed that there exists at least one fair number before n+2520

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

    Numbers that divide all possible digits occur at most every 9! numbers, which is 300k

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

I registered for this contest but by the time it started, I was wavering from participating in it as I have never successfully submitted a solution before this. I entered late in the contest and ended up solving and submitting 2 problems...successfully. :/ Weird eh?!

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

In DIV2 C did we have to count the no. of cycles?

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

Hi . This contest was not designed like the previous contests because until the second question the questions were designed at the ideal level, but from the third question onwards the level of questions was very high and this was really a big weakness

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

I read there are solutions to problem E that don't utilize the fact that the nimber is at most $$$\sqrt{M}$$$, and works in $$$O(N\log{N})$$$. How do those solutions work?

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

    Suppose that all Grundy numbers are in the range $$$[0, 2^d)$$$. Then, let $$$c_i$$$ be the number of vertices with Grundy number $$$i$$$, by definition, all $$$c_i$$$'s are nonnegative integer and their sum is $$$n$$$. Let $$$p_{k, i}$$$ be the probability that after $$$k$$$ steps of the first type the current Grundy number is $$$i$$$ (including the fact that $$$k$$$ steps may not even happen, so $$$p_{k, i}$$$ go to zero as $$$k$$$ increases). Then, we have a very simple formula: $$$p_{0, 0} = 1$$$, $$$p_{0, i} = 0$$$ for $$$i \neq 0$$$ and $$$p_{k + 1, i} = \sum\limits_{j=0}^{2^d - 1} \dfrac{p_{k, i} c_{i \oplus j}}{n + 1}$$$.

    In other words, $$$p_{k + 1} = (p_k \cdot c) / (n + 1)$$$, where by $$$\cdot$$$ I mean the Hadamard product of vectors. Because $$$p_0 = 1$$$, we get $$$p_k = c^k / (n + 1)^k$$$ (again, $$$c^k$$$ here means the $$$k$$$-th Hadamard power of $$$c$$$). Hence, the probability to end with Grundy number $$$0$$$ is the $$$0$$$-th coefficient of $$$\dfrac{1}{n+1} \sum\limits_{k=0}^{+\infty} \dfrac{c^k}{(n+1)^k}$$$. Indeed, to finish, we need to make $$$k$$$ steps of the first type (summands on the right) and then a step of the second type (multiplier on the left) for some $$$k$$$.

    Now, we can find the Hadamard transform $$$H(c)$$$ of $$$c$$$. Because Hadamard transform is linear
    ($$$H(\alpha f + \beta g) = \alpha H(f) + \beta H(g)$$$, if $$$\alpha$$$ and $$$\beta$$$ are numbers) and multiplicative ($$$H(fg) = H(f) H(g)$$$), we can get the coefficients of $$$H \left (\dfrac{1}{n+1} \sum\limits_{k=0}^{+\infty} \dfrac{c^k}{(n+1)^k} \right)$$$ just by replacing each coefficient $$$x$$$ of $$$H(c)$$$ by $$$\dfrac{1}{n+1} \sum\limits_{k=0}^{+\infty} \dfrac{x^k}{(n+1)^k} = \dfrac{1}{n+1} \cdot \dfrac{1}{1 - x/(n+1)}$$$.

    Finally, just apply inverse Hadamard transform to $$$H \left (\dfrac{1}{n+1} \sum\limits_{k=0}^{+\infty} \dfrac{c^k}{(n+1)^k} \right)$$$ that we just found. The probability of Bob's win is the $$$0$$$-th coefficent of the result.

    There are no issues with division by $$$0$$$ here: because $$$c_i$$$'s are nonnegative integers with sum $$$n$$$, the coefficients of $$$H(c)$$$ are integers from the range $$$[-n, +n]$$$. Hence, $$$1 - x/(n+1)$$$ can't be $$$0$$$ modulo $$$998244353$$$, because otherwise $$$n + 1$$$ and $$$x$$$ are equal modulo $$$998244353$$$, meaning that $$$998244353 \leqslant 2n + 1$$$. In fact, this solution proves that there are no bad tests (tests, where the denominator of the answer is divisible by $$$998244353$$$): there are no bad tests exactly because there are no issues with division by $$$0$$$ in this solution.

    This solution works in $$$O(n + d \cdot 2^d)$$$, if the input is just $$$n$$$ numbers from the range $$$[0, 2^d)$$$.

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

      It's not an improvement on complexity but you can in fact save yourself the inverse transform, since the sum of all coefficients in the forward transform is $$$2^d$$$ times the $$$0$$$-th coefficient in the initial vector (every other coefficient cancels out).

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

      This is easier. Consider the string as sequence of numbers 2^(s[i]-'a'). Last two numbers always will wid fixed signs: s[n-1] is positive and s[n-2] is negative. Other numbers can be with any signs. There are 2^(n-2) ways to distribute signs, but it's possible to find the desired distribution by the binary search principle. Sort the array of n-2 numbers by descending, then iterate over it. Initially all signs are positive. For each number find out, whether you have to change the sign of this number. This is necessary only if and only if the sum of all n numbers after changing remains greater or equal to t. If after iterating this sum is equal to t answer is Yes

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

        Why don't you like my approach???

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

          You are answering for Div2E whereas the above discussion is for Div1E.

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

            This problems have same letters, I didn’t understand. But 9 contribution points cannot be returned

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

              contribution points are also absolutely irrelevant

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

                It's still a shame that the minus dirts my profile. It's not beautiful!

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

                In past I thought that contribution is how much money are donated by him

                (I still bad know English, I'm Russian. Fixed me if.)

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

      I was very close to this solution during the contest but I didn't know about the linearity property of Hadamard Transform, which is why I couldn't proceed further. I have read a few articles on FWHT(including serbanalogy's blog) but never saw this property anywhere, can you suggest some source where I can learn more Hadamard Transform and its properties?

      Thanks a lot.

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

        You participated in contest ? I can't see the contest in your contest section .

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

I hate D1D...

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

Saw the contest only half an hour late, tried solve ng C directly. Figured everything out found connected components on the fly, ignored the piece on the diagonal. For any connected component with possibility of direct diagonal move, +total pieces in cc, else 1+ total pieces in cc. But pretest 4 failed. Very sad. Three wrong submissions already. Can someone tell me where I went wrong?

https://codeforces.com/contest/1465/submission/101904830

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

Can anyone help explain the idea of D2D? Thanks!

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

In today's Div2 ~ C problem: // after contest

  • I first precalculated number of rooks in each row and collumn.
  • Then I took a queue and put the numbers in which row and collumn both has no rooks
  • Then I cheked m roocks if they are in correct place or can be sent to main diagonal by one move using a mark array and precalculated row-collumn counters.
  • Then If I am unable to put rook in less then 2 moves, I poped a number from the queue and puted that rook in the poped position and marked that position accordingly.
  • Thus I got the ans

My code's link : https://codeforces.com/contest/1465/submission/101896978

As far as I think my complexity is O(3*m) => O(n) But I got TLE can anyone explain me why it got TLE

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

    one of your last lines of code: while(!empt.empty()) empt.pop(); You didn't include that to your complexity. Also, you have this same loop inside of O(m) so you'd get O(m*n), right? Also

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

    You can use heading little shorter .I thought you were giving solution .

    It's because inner for loop can run 'n' times in worst case thus m*n complexity .

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

      I just edited , thanks I used inner loop as a confirmation for not to have runtime error As far as I think the queue should contain the extra index of the empty (row,collumn) so as the queue should always provide that then the inner loop should not work :(

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

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

Am I the only one solve D2C without modeling it as graph and write very long and stupid code 101886029?

»
4 weeks ago, # |
  Vote: I like it -40 Vote: I do not like it

For Problem D (div.2) Greedy Solution WA test case 9: Dude wtf was with that D problem? I figured I would start off the round by solving D first since it would be 6 problems D should have been solvable. Anyway I read it and I figured if I went greedy it would work since for any test case that I could come up with greedy solution worked. When I say greedy what I did was from left to right when meeting a '?' I know the '1's and '0's before (two counters) and after (this can be done with a sum array from right to left) so I can figure which one is better to put. Can anyone please give me a test case where this doesn't work? I was getting WA in test 9 with greedy solution. Also for the cases where I would get the same cost I went recursively and tried both solutions to see which would give the best answer. Again I did not get TLE but a WA in test case 9. So please somebody give me a test case now that the contest is over. Also let's say greedy doesn't work, what kind of a DP solution would work, like I just need a complexity? Though I don't think a DP solution would work either. This problem must have the need of some really sophisticated data-structure/algorithm combination like Treaps with matrix exponentiation or some. But if you are gonna say 6 problems then make D at least solvable. Look at how many people solved C and how many solved D it's insane. Oh I can see why now... it's because they mostly used orange and red testers. Dude like if you are orange you know every algorithm known to man and every technique you have it already memorized. Competitive programming started ageing like chess smh.

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

    If x>y, all ? will filled by one of sequences like 11...100...0, from 000..00 to 111..11. In the other case, iterate over all sequences like 00...011...1

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

my code for div2 C is ans=m, decrease if x==y, increase if a cycle is found. my solution solves all test cases suggested in the comment section. and still WA on test case 5. help pls :) Edit: found my mistake, got AC.

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

Can anyone explain div2D .Thanks

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

    Consider all ? positions. If x>y, in the optimally case all the positions with ? filled by sequence like 11...100...0. Iterate over all possible sequences beginning a sequence with all zeroes. Next sequence is 100..0 then 1100..0 and etc. until sequence with all ones.

    In order to maintain the answer for each sequence, precalc for each position from 0 to n, number of 0 and number of 1 to the left and to the right of this position. While iterating the sequences you recalc the numbers of 0 and 1 to the left after each position with ?

    If x<=y, iterate over all sequences from the other side: 0..000, 0..001, 0..011, ..., 1..111 and recalc the numbers of 0 and 1 to the right after each position with ?

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

why some people are getting TLE in B ?

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

    I saw some of them use unordered map, i believe it has more constant factor(not sure), therefore failing the 2 sec time limit.

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

Why was there so weak pretests in B?

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

    If you mean that actually brute force isn't acceptable, then I will tell you that it can be proved it's acceptable

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

    pretests are not weak, the time limit is too strict :(

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

1000 TLEs for problem B :))

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

    I think you should make the test set to more simple and rejudge. 1000 points to such is rationable.

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

      A strategy to divide n by each digit just once, but adding a small log(n) factor gives TLE. come on!!

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

    It was more than 1000 :( image

    image

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

      And I am one of those people. This contest ruined my sleep. XD. Gonna practice some questions.

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

    At first I thought the brute force solution for problem B would give TLE . But after seeing the rate of AC's on B got me thinking if the brute force solution should just do the job. I did the brute force solution , but ended up getting TLE on test 11 . P.S. I used PyPy instead of Python3 but still got TLE.

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

I got TLE in Div2 B. I used the obvious iterative approach i.e. keep incrementing value until a value is encountered which satisfies the condition.

The only possible reason for TLE I reckon is I used maps to store frequency ( occurrence ) of each digit.

Why such strict time-limit? :| This is really frustrating, even if time limit was INTENDED to be strict, why were the pretests weak? Why so much intricate optimizations were expected in div2B? 101865684 P.S. I am losing 160 points today!

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

    Yeah that's the reason. I used set and got TLE too :/

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

    Yes. anyone who has added a log factor has a TLE. I dont see the point of such tight limits.

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

    I also think it is not reasonalbe to fail. Because we only want to store 9 digits in unordered_map, there is even not much collision for hashing. That strict time limit is meaningless.

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

      Agreed. dargelirli I am not being rude but I'd genuinely like to know, from experienced coders and problem setters about their views on the FSTs of problem B.

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

        I personally didn't expect FSTs. T * LCM * log sounds good in theory.

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

          Sorry it is T*LCM*18*LOG SO 1000*2520*18. Anything extra to that will be costly. 18 can not be ignored as it is too close to TL

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

    i have also got Tle!!!!! why so strict time limit???/

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

    That’s surprising, the exact same code works with std::array<bool, 10>. Does it fail with unordered_set which does the same thing but is constant time? I would guess not since N is only 10, asymptotic complexity doesn’t matter and you’re only comparing constant factors. You Can also cut out division by 1 by adding x%10>1 but like you said that’s really tight.

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

i think problem B is such a bad problem for a contest.

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

When the editorials of this contest will released??

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

Please Check problem B , it is bruteforce i agree but looking at c++ submissions they are getting accepted with fast i/o. Java solutions should be given consideration in such problems.

»
4 weeks ago, # |
Rev. 3   Vote: I like it -15 Vote: I do not like it

I was supposed to get +73 (and get my all-time high), but after system tests for B failed -23. Such a pity that 1000 other people failed system tests. A disgrace.

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

    Next time store the results and get a AC solution xD. Worst problem I have ever seen in codeforces.

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

    Hey, how were you able to determine these +73 and -23 numbers. Can you please tell where I can find them.

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

      download the extension on chrome of Codeforces predictor or use codeforces live bot . BTW Todays contest was horrible for me , I solved C just after 2 minutes of contest ending and thus it is counted as upsolved (which is not wrong), but after this I Got a TLE in B as well , Due to a small log factor , log factor of 10 :(

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

Worst Problem B I ever came across. Problem B is not equally good for all the available programming languages

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

    Agreed 100%. And I've seen quite a few Bs in my life.

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

    NO DIV2 B was simple simplehere is my solution

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

      No one said it’s hard. I just said it’s bad because Python solutions couldn’t pass and pretests were weak.

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

        ohk, btw i don't know exactly how much slow python is than c++.

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

        this soln in pypy passed. ps : but i still support the fact that time limit was strict for py coders and one tester should use py.

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

    Most python solutions got TLE.

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

    Using python the implementation was quite simple and short . That's why most of the people chose python over c++ for div 2B.

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

Interesting to see that all but one Python 3 solutions TLEd in system testing for Div 2 B.

The one that passed test 11 (system), used an LRU cache. Test 11 was all the same number. 101880982

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

    That is not acceptable, problem-writers.

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

    I thought that PyPy should be used most of the time anyway?

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

optimizeForce not codeforce

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

There should be a re-evaluation for B dargelirli neckbotov

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

    Yes, Python solutions with the same logic as C++ solutions should pass.

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

      Come on. There are a lots of problems that if you want to get AC with python, time limit should be 30 second.

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

People with same logic for B, someone getting TLE, someone getting AC. I've seen adhocforces, mathforces, but now optimizeforces ?

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

    True, also almost all solutions in python failed B! B needs re-evaluation!!!

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

      I've seen such solutions in Python itself, where both have same logic, but one is giving TLE and the other is giving AC. The only difference was:- one was using list, one was using string.

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

    But it is not optimization . How can you know your code will get FST after getting pretest passed in 125 ms where limit is 2000 ms . Why will u optimise ur solution in this case?

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

      Yes you are right, I would say that the Testcases were not appropriate.

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

    For example see this two submuissions. AC TLE

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

After having 20+ testers, it is very sad to see there are 1000+ system test fails on problem B (mostly for python3). It is advisable to keep at least one python coder as your tester

»
4 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

This Contest should be unrated, Problem B is not equally good for all the available programming languages

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

Why do I get TLE on main test cases for problem B? What the hell man! I don't think this was supposed to happen

Edit: my solution is cpp !!

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

Worst round ever :(

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

With this problem B, I came from cyan to almost gray in one week and the next contest is 10 days later, how should I survive the depression? XD

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

    start a 9-day vigorous practice session, hope you'll bring out the fire in good bye 2020!

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

dargelirli problem B should be rejudged ... why so strict time limit??

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

Good evening Codeforcess. I got an unpleasant situation, I sent a solution to problem B in Python. The pretests were passed, but on system testing I gave out a TL, on the finalization, I sent the same solution to PyPy and it was within time. I understand that it is hardly possible to do something already, but if suddenly someone tells me where to turn, I will be grateful) In general, this situation, unfortunately, is not the first time, maybe someone can tell you when it is better to send solutions to Python, and when to PyPy. I would also be very grateful. All high ratings)

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

My rating prediction just went from +100 to -100 only because of storing digits xD

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

    mine from -32 to -132 also because of storing digits. RIP ratings :(

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

    The biggest of the poor mistakes I have ever made. I wonder how storing results can make difference in a problem.Such a bad problem in Div2 B.It should give tle in every similar approach . Maybe the test cases are not arranged properly.

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

    mine from +30 to -30 :( for the same.

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

    +40 to -100

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

    -16 to +56 because of others getting TLE on B.my solution

»
4 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

I can't understand people who use python for competitive programming. If you use python for competitive programming, so you won't become good in it.

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

    Ever heard of pajengod bruh?

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

    Most people do competitive programming to learn a language and to get better at data structures and algorithms. I use Python because I can, what is the meaning of "If you use python for competitive programming, so you won't become good in it"? What does a language have to do with algorithms and logic?

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

      You can't do a simple dfs with python, then you want to get better at data structures and algorithms? Is there any LGM that his main language is python?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        1. Don't know much about DFS, but google search gives some implementations in python.
        2. https://codeforces.com/blog/entry/76507?#comment-610648
        3. I can code in C++ but then again, why would I use C++ in a contest where submission time matters and not run time(if within limits). For problems that cannot be submitted in Python, my first choice would be C++
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        why i can't do dfs in python? are you serious

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

        not everyone here is wanting to be LGM, i am here to practice for good placements.

»
4 weeks ago, # |
Rev. 4   Vote: I like it -14 Vote: I do not like it

got tle because of storing digits...

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

    same I used set to store the digits and TLED on test case 11 but pretest were not much strong.

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

This Contest went Tough for me but Contests like these are real tester of our skills like patience , how good we are in making comeback after slow start ,implementation . Overall it was a great contest and we will surely gain a lot of things (keeping aside ratings ) for long run

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

Why Ternary search gave AC for problem D div2/B div1.

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

Python Lives Matter xD

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

Why so much conflict on DIV2 B here is my solution DIV2 B Solution

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

Why Div 2 B rejudge on improved time limits would be fair.

  1. A large number of submissions times out on system test (excl. C++) which are of optimal time complexities.

  2. Had it been a case of TLE on pre-tests, (or even close to time limit), one have the opportunity to re-implement in faster languages. (I saw 93ms and thought it'd be fine)

  3. Languages like Python is not an odd choice for the problem, as it particularly helps iterating over digits without divide and modulo over 10s.

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

    I totally agree with you I was a bit sceptical at first but when I saw that it passed all the pretests so efficiently I didn't think it needed any optimisation at all. Suppose I'd have got something above maybe 1 seconds I would've tried to optimise it or would've thought about my approach again. But those silly pretests kept us clueless. In such cases why to even bother giving the pretests. Just don't tell us anything and let us match the answers just from the example given in the problem T-T

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

Can someone tell why i am getting wrong answer in test case 3 in system testing for div2 B my code :- 101899785

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

    I think it's better if you explain your reasoning/logic as well.

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

      I have counted individually digits for 2,4,8 --> max of three for 6 ---> 6 for 3,9 ---> max of two for 5 or 7 ---> 5 or 7

      then checked if it exits and divides the no. , if it divides then break else increment

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

        Your code is a bit hard to follow. Try not to name variables as 'ttt','se' etc. Why do you check if each digit of 'n'(given number) is divisible by every digit?

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

Div 2 B from OEIS again. A002796