4qqqq's blog

By 4qqqq, history, 12 days ago, translation, In English

Hello, Codeforces!

On Nov/26/2021 14:15 (Moscow time) Codeforces Round #757 (Div. 2) will start. This round will be rated for participants with a rating less than $$$2100$$$.

All the problems were authored and prepared by vaaven and me.

You will be given $$$5$$$ problems, one of which has two subtasks. You will have 2 hours to solve them.

We would like to thank everyone helped a lot with round preparation:

Score distribution: $$$500$$$ — $$$750$$$ — $$$1500$$$ — $$$(1500 + 1000)$$$ — $$$2750$$$.

Good luck everyone!

UPD: Editorial

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

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

I hope that you will enjoy the short and concise statements. Also I hope that the hack I found will make people FST less (yes, it is in pretests )

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

    I think you should change your mind about concise statements. Statements wrote very bad and statements are only stories that waste our time.

  • »
    »
    11 days ago, # ^ |
    Rev. 5   Vote: I like it +243 Vote: I do not like it

    Well, you and lollihunter's translations are very bad, and I'm angry at it.

    • Problem B, sample explanation is wrong. Later you post an announcement, so I don't have any words to say but just very annoyed.
    • Problem E, even the statement is wrong. You write $$$P+1,P-1$$$ instead of $$$T+1,T-1$$$, and later you fix the mistake without posting an announcement.

    So many people test this contest, but why don't any of them find these obvious mistakes? I think you should reflect on yourselves.

    UPD

    After the talk with errorgorn, I realize that it isn't his fault.

    When I tested the round, the statements were much worse. That is why I told the coordinator that I would help clean up the english statements.

    I am very sorry to make this trouble. The mistake of problem E is maybe the problem setter's fault.

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

      Agree.

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

      I wasted a long time on the wrong statement of E,I've even written the code.I'm angry now.

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

      I think that problemsetter should tell competitors about statement-update quickly.

    • »
      »
      »
      11 days ago, # ^ |
      Rev. 7   Vote: I like it +22 Vote: I do not like it

      I edited the statements for problems A,D,E only (and a removed problem). Problem B was added very late into testing so I did not look at it. I wrote problem E with only using $$$T$$$, I am not sure why it is changed as well. (I believe it was added quite late into testing as well so please do not blame the rest of the testers.)

      I tried to do my best as a tester but I did not want to interfere too much with the content of the problems. I personally felt that I was pushing it when I removed some backstories in the statements (you will notice the english statement for A is much shorter than the russian statement).

      I don't really have anything to defend myself but I did not know the statements were changed from what I edited it to until today.

      I can understand your frustration but there is only so much a tester can do...

      If there are any comments that are actually about translation and making the statements easy to read, I would be happy to read them. The problems you listed have nothing to do with translation. Do you really think they are the translators fault? They also appear in the russian version of the statements you know.

    • »
      »
      »
      11 days ago, # ^ |
      Rev. 2   Vote: I like it +23 Vote: I do not like it

      That's not lollihunter's or errorgorn's mistake, because they made translation before some edits in english texts.

      So, sorry for such terrible statements :(

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

    Someone please give hint for Problem D1

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

      use dp

      also , $$$\sum_{i=1}^n(\lfloor\frac{n}{i}\rfloor)$$$ is about $$$n \ln n$$$

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

    error

    I don't know, when will the editorial release so, I am commenting here.

    In problem B I have just used

      sort(all(a), [&](auto &a, auto &b)
             {
                 if (a.first != b.first)
                     return a.first > b.first;
                 else
                     a.second < b.second;
             });
    

    to sort the array and I got TLE.

    Even if I remove else a.second < b.second;, still I am getting TLE.

    I used this sort(all(a), greater<pair<ll,ll>>()); after the contest, the solution got accepted.

    Solution1

    Solution2

    If possible, kindly resolve this issue, as according to me this should be a problem.

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

      Eh, I am only a translator... I guess i can help fix your code

      The issue is with the code below,

      sort(all(a), [&](auto &a, auto &b)
           {
               if (a.first != b.first)
                   return a.first > b.first;
               else
                   a.second < b.second;
           });
      

      you have missed out the return statement in the else I think changing it to the edited code below should work

      sort(all(a), [&](auto &a, auto &b)
           {
               if (a.first != b.first)
                   return a.first > b.first;
               else
                   return a.second < b.second;
           });
      
    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You missed a return in the compare function in solution 1.

»
12 days ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it

This is my first time testing the round and I hope my feedback helped to balance it! I encourage you to read all of the problems — as they are very interesting.

»
12 days ago, # |
  Vote: I like it -10 Vote: I do not like it

A great time for Chinese people. Hope everyone can gain rating.

»
11 days ago, # |
  Vote: I like it -17 Vote: I do not like it

Score distribution looks promising

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

Note the unusual timing

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope to perform well in div2 contest.

»
11 days ago, # |
  Vote: I like it -14 Vote: I do not like it

D1>D2? That's weird. I hope everyone can solve them.

»
11 days ago, # |
  Vote: I like it -155 Vote: I do not like it

Specialist setting rounds on CF. Pathetic! One day we will see newbies doing same.

»
11 days ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

I always see, when the contest is held in unusual time, there are relatively less people who participate in the contest. And that is why we get less rating changes as compared to a usual time contest (because rating change also depends on no. of participants).

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

    Ok so you participate in contests just to get some ratings?

    This mentality of just gaining ratings and not enjoying CP as a sport has led to so many cheating cases these days!

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

      haha...go and check my profile...still stuck on specialist after giving around 70 contests. If I were a cheater I'd have been orange or red till date after giving around 70 contests. Moreover I have 192 days problem solving streak(and counting) till date. If I were a cheater, why would I have been practicing CP this much. These things are enough for anyone to understand that I don't cheat.

      Reward is something people wants when they works for it. People first need expectation to gain something in life provided that they are working fair. Yes I give contest for rating, but that is not greed. Because your school teacher has not taught you the meaning of greed. Greed is something that we want without working, and expectation is something that we want when we work hard for it. That is called 'achieving', not 'cheating'. I hope god made you smart enough to understand this.

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

    Looks like you have cheater mentality of just giving contest for Greed(ratings). Stop it or you will be banned..

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

      who are you, the thought police? no one's getting banned for their mentality

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

      haha...go and check my profile...still stuck on specialist after giving around 70 contests. If I were a cheater I'd have been orange or red till date after giving around 70 contests. Moreover I have 192 days problem solving streak(and counting) till date. If I were a cheater, why would I have been practicing CP this much. These things are enough for anyone to understand that I don't cheat.

      Reward is something people wants when they works for it. People first need expectation to gain something in life provided that they are working fair. Yes I give contest for rating, but that is not greed. Because your school teacher has not taught you the meaning of greed. Greed is something that we want without working, and expectation is something that we want when we work hard for it. That is called 'achieving', not 'cheating'. I hope god made you smart enough to understand this.

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

        respect++

      • »
        »
        »
        »
        11 days ago, # ^ |
        Rev. 2   Vote: I like it -21 Vote: I do not like it

        respect -= -1;

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

          XD too many downvoted this comment which was simply respect++.

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

            I'm sorry for my poor English *

            it's much easier to get downvoted when your rating is low. But of course there is sometimes an exceptions

            3

»
11 days ago, # |
Rev. 3   Vote: I like it +31 Vote: I do not like it

First time being a tester, so excited (^.^). Although the start time is unusual again, hope you guys could spend time participating the well-prepared round with interesting problems >~<

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

    your graph is really motivating :)

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

      Thanks! I have focused on CP since last year in order to have an opportunity to participate in the national OI in my country. If I could proceed to the national round, my next target is reaching yellow color on CF ;)

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

      look at my graph and be demotivated again lol

»
11 days ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

Hope that my streak of underperformance ends here

»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

I hope to solve four problems in this round. Looking forward to it :).

»
11 days ago, # |
  Vote: I like it +39 Vote: I do not like it

As a tester I'm a tester

»
11 days ago, # |
  Vote: I like it +62 Vote: I do not like it
»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

fingers crossed for some non negative delta

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Are Ratings going to update before the round starts ?? Any Idea ??

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Can we participate in a contest without rating update from the previous contest?

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

Will this round take place with the current ratings or would it be considered after yesterday's round rating changes are updated? MikeMirzayanov

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Thxx for the unusual timing. Its better for us (russians)

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

hey I have confusion as previous contest rating is not updated yet so this contest rating will be calculated with change in rating or rating before previous contest ? please someone clearify

»
11 days ago, # |
  Vote: I like it +6 Vote: I do not like it

The contest was delayed by 10 minutes!

»
11 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Why delay??

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why you made changes in timings??

»
11 days ago, # |
  Vote: I like it +237 Vote: I do not like it

Sorry, I postponed the round. I would like to have time to update the rating based on the results of yesterday's Div3. I'm in a hurry!

»
11 days ago, # |
  Vote: I like it -17 Vote: I do not like it

I have not copied or shared any information with anyone, but I got this message from the system that my submission significantly coincides with someone else. Can someone please look into this

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

    don't use ideone. Its the major reason for this type of issues.

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

      I did not use any online editor and am sure I kept my submission private.

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

    I did the ideone rookie mistake. Hopefully will recover in this contest. OP is right. Keep it all private.

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

    Edit: Problem solved. I have got my rating.

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Good decision to increase 10 minutes , i didn't drink coffee

»
11 days ago, # |
  Vote: I like it -7 Vote: I do not like it

Why it's start time is 19:15(in China)?

It's usually 22:45(in China).

»
11 days ago, # |
  Vote: I like it +14 Vote: I do not like it

Congratulations to 4qqqq to get 107 ratings. XD

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to everyone

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow! MongoliaTop has AKed this contest!

»
11 days ago, # |
  Vote: I like it -6 Vote: I do not like it

Is it div.3?

»
11 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Another mathforces round :(

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

Retired_MiFaFaOvO participating .. after a long time

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

The amount of ad hoc contained in problem C frightened me.

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

pretest 2 of problem c has cost me my mouse and sanity

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

    How do you solve it? Pretest 2 killed me

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

      In my case I missed the input like:

      1

      1 1

      1 1 1073741823

      it took my last 40 minutes during the contest...

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D2? How to optimise from O(Max(ai)*log(max(ai)))?

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

The problems themselves are good, but the contest is unbalanced. There are so many math problems. Problems A and B are too easy, and problems D E are too hard. If you have some problems with problem C, like me, wasting too much time for mistaking "OR" by "XOR", you will be finished.

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

    I saw it after seeing your comment I thought it's xor of subsegment.. I'm doomed

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

    Same thing happened to me also :(.

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Hint for C I wasted my 30 minutes in thinking this logic. Could have googled it early and got a decent rank!

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

    Same

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

      Two Friends Of Mine Tried Solving It Using Lazy Propagation xD, only one got ACC

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

    I was able to figure this out — but what was the logic for finding the frequency/number of each bit present in the array? e.g. in array [1, 2] — 0th bit freq is 1, and 1st bit freq is 1. How do I get that info from the subsegments?

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

      if an element is covered by more than 1 subsegments, then its largest possible value is the bitwise AND of all values corresponding to the subsegments that are covering it.

      For example, if we have n=3 and subsegments 1 2 7, 2 3 14, then the largest possible value of a_2 is 7 & 14 = 6. Moreover, a possible value must only have the bits occur in the binary representation of the largest possible value. But we can safely just use the largest possible value here.

      I used a segment tree (range update + point query) to process this information, and I wonder whether there exists a simpler approach.

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

        What i did was, took OR of all the OR's given (irrespective of l,r) and just multiplied it with pow(2,n-1). This passed pretests as well as sys tests.

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

          It's like we don't need to reconstruct a valid sequence, am I right?

          Could you briefly explain the intuition (or proof) behind this? Thanks

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

            Yeah, we don't need to construct a valid sequence.Try this link here for a formal proof

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

            If X is the bitwise OR of a segment, then for each set bit of X, there exists an element with that bit set. Then consider all subsequences excluding that element (2^(n-1) of them): they either XOR to 1 or 0 times 2^(bit). If they XOR to 1, then subsequence with our set bit XORS to 0; if they XOR to 0, then subsequence with our set bit XORs to 1. Either way, we are guaranteed a contribution of exactly 2^(bit) times 2^(n-1) from that bit, i.e. its contribution to x. So we just need to know if a given bit is set anywhere in the whole sequence, and if so we add that contribution. Otherwise, the bit is skipped.

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

            i am such a stupid that i started figuring out a valid sequence and I figured out how to find a valid sequence.But when i used combinatorics to find the number of subsequences i realized that we just need to know whether there is a particular bit on in any of the element in the array which can easily be figured out by just looking OR of all elements.

            2^(num of on jth bit-1)*2^(n — (num of on jth bit)) you can see that num of on jth bit cancels out but you can see num of on jth bit — 1>=0 num of on jth bit >=1

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

          Yes, I'm seeing some submissions with this logic. Could you explain the intuition plz

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

          Why does this work? I got that OR of all the ORs given will be the OR of the original array. But why does it become sum of XOR of all subsets after multiplication with pow(2,n-1) ?

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

            In binary, look at digit r (aka the bit corresponding to the place 2^r) of all numbers in the original array. Say a of them are 1s and b of them are 0s. From the set of a numbers, choose i to be in some arbitrary subsequence, and from the set of b numbers, choose j. Note that making such a choice corresponds to forming exactly one subsequence (for now, dealing with digit r only). Clearly, the bitwise XOR will yield a 1 for digit r iff i is odd. If a>0, this corresponds to aC1 + aC3 + aC5 + ... = 2^(a-1) ways of choosing a set of i numbers from the original a, where i is odd, and simply 2^b ways of choosing any j numbers from the b with 0s at digit r. Hence, when a>0, the total contribution from all subsequences to coziness by digit r is 2^(a+b-1) * 2^r = 2^(n-1) * 2^r, as a+b=n. When a=0, however, the contribution to coziness is 0. The coziness can thus be written as 2^(n-1) * sum(2^r, where a>=1 at position r). Observe that this sum is the bitwise OR of the n numbers, and we're done.

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

              Thanks a lot. This seems fine. Although I found this another explanation by going through the comments-

              If at a given place, if at least one of the numbers has its bit = 1 :

              1) lets remove any number from the array whose bit is 1 at that place.

              2) now, rest of the numbers(n-1) will make pow(2,n-1) sets, now all the sets with xor of bits = 1 will contribute to the solution (addition of XORs)

              3) but if xor of the bits in a set is 0, the it will become 1 when the excluded number with set bit is added to all the sets, and then it will contribute to the solution.

              4) So if at least one of the numbers has its bit 1 at a place, it ensures that this place will contribute place_value*pow(2,n-1) to the solution (sum of XORs)

              5) Now to ensure if at least one number has its bit 1 at place, we can find OR of all the numbers and check if the it is 1 at that place.

              6) OR of all the given ORs will be the OR of the array.

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

    I wasted a lot of time in solving this, however, I still didn't solve it. Thanks for your hint. My rating must be reduced a lot. :(

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

    So its googleforces :/

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

    i just cannot become friendly with XOR, doesnt matter how much i try.

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

      Yea me too. In theory XOR has the same abstract complexity as AND and OR. But I feel like our (at least mine) minds don't understand XOR the same, natural way they understand AND and OR. Also XOR has so many weird characteristics that aren't easy to come up with on spot.

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

        exactly, XOR questions according to me are hard to visualize, but AND and OR are so easily visualized...

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

    for m segements, [l, r], we can just think it as there is a x in the array, no matter the position.

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

How to solve D1?

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

    Sorry for my poor English.

    Let we call $$$b_i=\gcd(a_1,\cdots a_i)$$$,then we have $$$b_i|b_{i-1}$$$.

    And $$$b$$$ is like $$$[c,\cdots c,d,\dots d,e,\cdots]$$$.

    $$$dp_i$$$ Means the max value when you choose all $$$j$$$ That $$$i|a_j$$$.

    Add some $$$i$$$ after $$$[\cdots,ki,\cdots,ki]$$$,so $$$dp_i=\max(dp_{ki}+i(t_i-t_{ki}))$$$ where $$$t_i$$$ means $$$\sum\limits_{j=1}^n[i|a_j]$$$.

    Then we can solve it in $$$O(a\log a+n\sqrt a)$$$.

»
11 days ago, # |
  Vote: I like it -45 Vote: I do not like it

D1 was really interesting!

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

    Really curious to know, How to do it ?

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

    This is certainly not the right place to talk about it but I saw you video reviewing profile of users, I am stuck in green here. Would be glad If you could suggest something. Many thanks

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

      I don't have a lot to suggest. It seems like you left CP for a long time. Anyway, if you continue to solve problems in rating [1300:1500], you should be good to go. Also, up solving at least 1 problem after every contest is a must.

»
11 days ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

How to solve D2 ? Does it involve the fact that we only have to consider atmost 25 distinct elements?

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

    I didn't use it . I just made some small constant optimization on the code of D1 .

    If so , I think there is no need to set D2 ...

»
11 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Problem B, i figured out total time, but how can i print the vector? Divan's office at 1 and then sort given vector in decreasing order, then v[0] at 2,v[1] at 0, v[2] at 3 v[3] at -1 ....

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

    you can sort a vector<pair<int, int>> where the first element of each pair is the value, and the second element is the original index. In such way you can preserve the information of the original index.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi everyone, sorry to bother but :( in the contests I participated in during this time, the codeforces page loads very slowly :( this prevented me from submitting my post C at the last minute can anyone give me some advice.

»
11 days ago, # |
Rev. 5   Vote: I like it -11 Vote: I do not like it

Help needed!!!! In q.2 of today's contest I have made a submission :

https://codeforces.com/contest/1614/submission/137006738

Above is the code ,I surely believe that there is some system error that's why it is giving me wrong answer on test case 4 ,which passed when I made some meaningless changes,in short can someone tell me why this code is not passing because I have made this submission after 13th minute ,so if this code passes then I get a very good rank as compare to now...please help

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

Can someone help me understand why https://codeforces.com/contest/1614/submission/136996986 got TLE?

its O(nlogn).

EDIT — Seems like many people who used Python TLE'ed this problem.

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

    Yes, this is happen with me as well. Other language with nlog(n) passes all the test case while python fail

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

    I guess it's because of print(*ans)

    Use join, it's faster: print (' '.join(map(str, ans))

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

D is such a funny problem. The difference between D1 and D2 is that max(a_i) difference is about 4 times bigger. Time for ConstantForces

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

    Author's solutions have different asymptotics for D1 and D2.

    Editorial will be ready soon.

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

      I hope it isn't max(A_i)^3/2 and max(A_i)log(max(A_i)).

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

        It is

        D1: max(A_i) * log(A_i) D2: max(A_i) * log(log(A_i))

»
11 days ago, # |
Rev. 3   Vote: I like it +63 Vote: I do not like it
»
11 days ago, # |
  Vote: I like it +2 Vote: I do not like it
  1. Started 1 hour late
  2. Happy that solved A,B in 15 min.
  3. Figured out C quick
  4. Forgot to take MOD in final answer for C

Moral: No matter what happens, even if it's a life and death situation, never forget to take MOD :(

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Help needed!!!! In q.2 of today's contest I have made a submission :

https://codeforces.com/contest/1614/submission/137006738

Above is the code ,I surely believe that there is some system error that's why it is giving me wrong answer on test case 4 ,which passed when I made some meaningless changes,in short can someone tell me why this code is not passing because I have made this submission after 13th minute ,so if this code passes then I get a very good rank as compare to now...please help

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to approach and solve D1 and D2?

Thanks in advance.

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

Is it possible for pretests to have a worse max runlength than systests? I remember being concerned that both my B and C solves took more than 600ms (vs. tight-for-python 1s TL), but now the latter is down to 327ms after systests.

edit: not a complaint, just hoping to diagnose an issue if there is one... either I'm wrong in assuming systests include pretests, or there was a problem that resulted in wild swings in runtimes (independent of actual individual complaints)

»
11 days ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

Why this submission in C++ 17 gives TLE for D1

And the similar solution to it C++ 20 passes within the given time limits even though the worst case runtime for both the solutions is same.

Why changing in different version of C++ has so much big difference in runtime and if so then should the problem not have much flexible time limits as you can see it cost me an extra penalty just because I choose C++17 version initially

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C is segment tree range-AND for each segment with their beauty and then XOR-sum in O(n) right ? Got TLE on test case 2 sadge

  • »
    »
    11 days ago, # ^ |
    Rev. 3   Vote: I like it +7 Vote: I do not like it

    Doesn't actually need to be this complicated. If X is the bitwise OR of a segment, then for each set bit of X, there exists an element with that bit set. Then consider all subsequences excluding that element (2^(n-1) of them): they either XOR to 1 or 0 times 2^(bit). If they XOR to 1, then subsequence with our set bit XORS to 0; if they XOR to 0, then subsequence with our set bit XORs to 1. Either way, we are guaranteed a contribution of exactly 2^(bit) times 2^(n-1) from that bit, i.e. its contribution to x. So we just need to know if a given bit is set anywhere in the whole sequence, and if so we add that contribution. Otherwise, the bit is skipped.

    In pseudocode terms

    ans = 0
    For each segment:
        get(l,r,x)
        ans |= x
    
    ans *= 2^(n-1)
    

    (Take mods where appropriate)

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

      I wonder how I miss that while still understanding we can do XOR-sum in O(n) for kinda the same argument. Thank you that was helpful.

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

        I actually missed it in contest too. I did a brute force over each bit, setting only those I had to set to 0 (i.e. where we had information on a whole segment that the bit was 0). From there I applied some combinatorics.

        This was all a bit of a waste of time, and my solution just scraped through in the 1s limit.

        I later realised that, by symmetry, all my combinatorics effectively came out at "half of all subsequences" for any set bit.

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

          I guess for Question C, the question should have also asked for the possible values of elements of array, so that Lazy_propagation would have become necessary.

          Here's my submission by which we can also print possible values of array.

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

            lazy propagation wouldn't be "necessary" strictly speaking, because you can apply all the range updates before printing the array

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

              Actually I used LAzy propagation in Segment tree for range updates. So I guess it's necessary.

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

                You can do offline range update (i.e. process all the range update operations, then print the array) without lazy propagation segment tree

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

      I did exactly that still got WA on pretest 3. Any idea why?

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

        Need long long, not int, I think. When you’re multiplying two ints together you’re potentially getting an overflow before you MOD them.

»
11 days ago, # |
  Vote: I like it -30 Vote: I do not like it

worst problemset i've ever saw...

»
11 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Very great contest,but I think the time limit for C can be 2s.

»
11 days ago, # |
  Vote: I like it +14 Vote: I do not like it

Finally Specialist Today !!!!

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

    So seems like you aren't a loser anymore! :)

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B, I failed for the error message for the pretest: "wrong answer answer is wrong: pans = 14 is not equal real_pans = 18 (test case 1)" But the example output is 14 for the test case 1. I checked many acceptable submissions, the answer is still 14 not 18. Do I miss something?

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

    optimal answer is 14 but your output array will give 18 that's why it is showing 18..

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it
  • Tester: "As a tester, I tell you that the problems are well balanced and well prepared!!"
  • CF User: "Ok I will participate then"
Tester IRL
»
11 days ago, # |
  Vote: I like it +11 Vote: I do not like it

Passed pretests of D2 only to see failing on sample in system testing. -,-

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

    I know right. I literally did some stupid optimization and passed D2 right now. To be honest, look at the time variance of any code from any test although solution is independent of N. The time variance is just too large sometimes reaching 500ms in that problem for no reason.

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

    Just noticed system test was run for 3rd time. (Pretest passed, TLE2 on 1st ST, TLE18 on 2nd ST, AC on 3rd ST). What is going on? :|

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

      I guess they decided to give people a fair go (i.e. when the servers weren't overloaded)

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

    My submission TLEs on different test each time I resend it... Time limits should either be tighter or looser.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

137041121 137027753 This is not ok. One parnthesis off

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Still don't get problem 2. I was the only one who struggled due the errors in the examples?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain why this solution of mine for problem B is getting TLE 137017820

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

    large input/output causes TLE, use this instruction before write anything in the main function:

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) ;

»
11 days ago, # |
  Vote: I like it -14 Vote: I do not like it

Why do you set the minimum temperature of question e to 0? Why is it not 1 or -1e9? The important boundary information is written so unobviously, fuck.

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

I can't understand the verdict of [problem:1614B]problem B in my code? https://codeforces.com/contest/1614/submission/137041237

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

    Can you check my code?

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

      check your answer manually it's coming wrong..

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

    2 5 4 3 1 0

    Your array outputs: (3*2)*3+(2*2)*8+(1*2)*10+(1*2)*6+(2*2)*1 = 86 which is not the correct answer.

»
11 days ago, # |
  Vote: I like it +16 Vote: I do not like it

What a painful lesson to learn that $$$2^{30} > 10^9+7$$$. (Problem C)

»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Was this the intended solution for D1?
I used 1D DP over all the possible factors of all the numbers.
https://codeforces.com/contest/1614/submission/137040944

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I wrote a dp solution for probleme [problem:https://codeforces.com/contest/1614/problem/C] , while the complexity of my code should work just fine, the time constraints didn't fit [submission:https://codeforces.com/contest/1614/submission/137034593],

changing from long long to int, made the solution pass just fine [submission:https://codeforces.com/contest/1614/submission/137043656] , it's been a while since the last time I encountered such a problem.

I know It's not the intended solution, but mine should be accepted too, or what do you think?

»
11 days ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

I would like to ask if system test slower than pretest?

When I solve problem C, it says pretests passed (12 test cases) and the time cost is about 820 ms. After carefully consideration, I decided to move on.

But I finally failed the system test, and the maximum time cost for first 12 test cases is 951ms. (And it finally failed test case 15). If I get 951ms in the pretest, I will try to optimize my code.

I see in comment section that @iaNTU failed the first test case in the system test with problem D2, he must passed test case 1 in the pretest, that is why I ask this question.

UPD: Thanks god, my contest code get AC after rejudgement.

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

Problem COrigial problem at Leetcode 1863

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

Was there no pretest in C for the max N? my code TLE'd on test 17. it was O(NlogN*logN) and maybe it can be optimised but I didnt try as the pretests passed. Please try to include max N in pretests. Nice problems tho

Edit: submission rejudged it is AC now

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

    You should always check the max N by yourself, e.g. via the Custom Invocation. There has to be some area for hacking lol

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

      my bad, the submissions are rejudged, i should not have commented before the contest was officially over

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest had some really nice problems and problem C ahh I feel so sad that I forgot to mod after the multiplication of or_of_all_elements*2^(n-1) and like ugh I feel really disappointed, rating's gna drop for sure! After the contest, I was talking to my friend and he told me, dude you forgot to mod and then I was like $h!t such a stupid bug. Overall the contest was really nice orz.

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Can there be more than 1 answer in problem C?

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

    I don't think so. Howsoever the distribution of bits across all N elements is, in the end, it only matters if a particular bit is set in any of the N elements.

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

    don't know but there can be multiple possible values of array, of which one could have been asked to print to make the question better.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

»
11 days ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, there is a chinese tutorial.

Welcome to watch and correct(dls tydy

(https://www.bilibili.com/video/BV1iS4y1R79V/

»
11 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Originally I wrote a solution for problem E which passed pretests, but resubmitted later because I was scared about TLE. Glad I did, because even my faster submission took 1996 ms! (https://codeforces.com/contest/1614/submission/137021260)

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone share their idea of dp solution in D1?

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

I am no Psychologist, but brah this Divan has some serious problems..

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Lol, the number of upvotes of this post is getting fewer and fewer

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

.

»
11 days ago, # |
  Vote: I like it -6 Vote: I do not like it

I hope there will be more rounds like this.

»
11 days ago, # |
  Vote: I like it -10 Vote: I do not like it

I have a pupil title on the site how do I cheat from newbies?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

today, will giving the contest my code coincides with the kingkd code. Sorry for the voilation of the rule but this will not happen again as kingkd id(iamstupiddude26@gmail.com) is my previous id only which due to some reason i lost it,but few days ago i got my id password back so mistakenly given the contest with same id, this will never happen again and i will permanently close my kingkd id, sorry for the voilation of the rules, please provide a last warning.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Attention!

Your solution 136997720 for the problem 1614A significantly coincides with solutions kingkd/136997356, ayushkedia0511/136997720. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

today, will giving the contest my code coincides with the kingkd code. Sorry for the voilation of the rule but this will not happen again as kingkd id(iamstupiddude26@gmail.com) is my previous id only which due to some reason i lost it,but few days ago i got my id password back so mistakenly given the contest with same id, this will never happen again and i will permanently close my kingkd id, sorry for the voilation of the rules, please provide a last warning.

i

»
11 days ago, # |
  Vote: I like it -12 Vote: I do not like it

MikeMirzayanov Have you forget to update the ratings?

»
11 days ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

kingkd and ayushkedia0511 are both my id because kingkd is my old it which is lost but i got it and mastakenly i gave the contest with both id, for for the voilation of rules and i will not use my old (kingkd ) id for more contests

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

    looking at your code, i realised that you submitted your code with kingkd untill you got accepted, and then you submitted with ayushkedia0511.

    it's 100% obvious that you used two accounts in purpose but now you are still lying that it was an mistake.

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

      I wanted to say I don't know that I can't use to accounts if you will see my kingkd account only 4 submission are there , I used it after a very long time and this time I am only experimenting and this account banned happened

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

      That's why I am requesting to give a chance because I don't know about this

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

When will be the editorial published? I think this is already late.

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

Please Update the Ratings . I want to see myself as a Specialist Today :_: before i go to Sleep it Late night in here in India.. Also jee main paper Doesnt decide your Future

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me figure out why these 2 similar solutions for D2 are giving different results? Is there some optimisation I'm missing?

Passing: 137049637 Not passing: 137046389

»
11 days ago, # |
  Vote: I like it -75 Vote: I do not like it

There must have been something special about your round since Retired_MiFaFaOvO took it (his first cf contest in almost 2 years). Congrats on getting this legend back!

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

D problem was tricky.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey! Can anyone please explain C problem. I know it is easy but i didn't get it properly.

»
11 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Here are two of my exact same submissions, which differ by almost 600ms in runtime. Before this, one submission got TLEd on the first submit, and then the same code got accepted on submitting it again. 137066206 and 137066133

Are such large differences common? It seems to me that something is up with the judge.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

nice problems, bad contest

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D2? I cant think of any other way than computing dp for all divisors. I used the same D1 code, compute the factors only if required. But still got TLE. submission.

I also tried to create an array of divisors for all 2e7 integers with complexity 2e7 * number of divisors. Optimized to compute only where all of the prime factors of this number is <= to the max number of prime factors. There I got MLE submission. So how to solve it ?

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

    You can create prime tables in $$$\mathcal{O}(2e7)$$$ and the we can enumerate prime's multiples. Submission

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it
    • We can take primes using classic sieve. This is fast enough.
    • Instead of taking multiples using a sieve-like approach, we can count multiples using $$$sqrt(val)$$$ factorization.
    • For the dp state transition, it is enough to check for "prime steps" (i.e, instead of looking at $$$2*i$$$, $$$3*i$$$, $$$4*i$$$ ..., just look for $$$2*i$$$, $$$3*i$$$, $$$5*i$$$, $$$7*i$$$, ... is enough). Reason is that this prime multiples (or steps) has already taken into account the composite steps.

    Example is when you are at $$$dp(5)$$$, you can look at $$$dp(10)$$$, $$$dp(15)$$$, $$$dp(20)$$$. But $$$dp(10)$$$ has already looked up to $$$dp(20)$$$ earlier, plus it's easy to see that $$$dp(i)$$$ >= $$$dp(i * k)$$$ where $$$k$$$ is some constant. So going for a composite check is unnecessary.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

mysubmission

what's wrong with my code,can anyone help me?? thanks in advance

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

    I think res[i+1]*a[i] is an int multiplication which overflows in your example

»
10 days ago, # |
  Vote: I like it +3 Vote: I do not like it

In question B, it is given how the businessman will travel for first 10 years(5256000 minutes) only. And it is asked to choose the cordinates such that it minimises the time for walking within first 10 years only, no info. about what to consider if he can't visit every building in that time, what to print in that case the minimum time < 10 years by visiting only some good buildings or just try to minimise the time only if buildings can be travelled within 10 years or something else can't decide

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone can explain to me C Problem Properly.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Submission for problem D1

Can anyone explain the time complexity analysis of this solution and also in general for any dp solution. I become little confused sometimes while calculating time complexity of a dp solution.

Thanks in advance:)

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

Submission for C

Could anyone please explain what's wrong in my code? I applied the exact same approach as in the editorial. Thanks in advance. Upd: Found my mistake.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Here's my apology for the mistake I had in the contest.

Please pardon me this time.

https://codeforces.com/blog/entry/97309

»
10 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Could someone tell me how to get the table cnt[x] where cnt[x] denotes how many numbers are there which are divisible by x in o(nloglogn ) or in o(n)