4qqqq's blog

Codeforces Round #757 (Div. 2)
By 4qqqq, history, 3 years 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

Comments Comments (194)
| Write comment?
»
3 years 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 )

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

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 5   Vote: I like it +243 Vote: I do not like it

    Well, you and phyzzmat'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.

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

      Agree.

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

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

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

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

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

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

      So, sorry for such terrible statements :(

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

    Someone please give hint for Problem D1

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

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

    → Reply
    • »
      »
      »
      3 years 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;
     });
      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

Note the unusual timing

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

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

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

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

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

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

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

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

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

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

    your graph is really motivating :)

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

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

      look at my graph and be demotivated again lol

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

Hope that my streak of underperformance ends here

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

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

As a tester I'm a tester

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

fingers crossed for some non negative delta

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

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

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

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

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

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

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

The contest was delayed by 10 minutes!

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

Why delay??

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

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

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

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

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

Congratulations to 4qqqq to get 107 ratings. XD

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

Good luck to everyone

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

Is it div.3?

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

Another mathforces round :(

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

Retired_MiFaFaOvO participating .. after a long time

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

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

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

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

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

    How do you solve it? Pretest 2 killed me

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

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

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

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

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

    Same thing happened to me also :(.

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

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

    Same

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

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

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

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

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

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

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

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

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

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

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

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

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

    So its googleforces :/

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

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

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

How to solve D1?

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

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

D1 was really interesting!

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

    Really curious to know, How to do it ?

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

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

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

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

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

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

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

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

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

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

its O(nlogn).

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

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

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

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

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

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

My D2: TLE on test 1[main tests] https://codeforces.net/contest/1614/submission/137008202

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

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

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

    line 4

    #define ll int

    and your "meaningless changes" include changing it to #define ll long long int

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

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

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

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

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

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

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

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

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

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

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

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

worst problemset i've ever saw...

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

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

Finally Specialist Today !!!!

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

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

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

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

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

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

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

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

137041121 137027753 This is not ok. One parnthesis off

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

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

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

→ Reply
»
3 years 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.net/contest/1614/submission/137041237

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

→ Reply
»
3 years 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.net/contest/1614/submission/137040944

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

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

changing from long long to int, made the solution pass just fine [submission:https://codeforces.net/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?

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

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

Problem COrigial problem at Leetcode 1863

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

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

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

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

Can there be more than 1 answer in problem C?

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

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

How to solve D?

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

Tutorial video by jqdai0815 (in Chinese)

→ Reply
»
3 years 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.net/contest/1614/submission/137021260)

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

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

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

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

.

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

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

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

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

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

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

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

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

nice problems, bad contest

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

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

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   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 looking for $$$2*i$$$, $$$3*i$$$, $$$5*i$$$, $$$7*i$$$, ... is enough). Reason is that these 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.

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

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

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

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

→ Reply
»
3 years 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.net/blog/entry/97309

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

→ Reply