zwezdinv's blog

Codeforces Round #909 (Div. 3)
By zwezdinv, 13 months ago, In English

Hello, Codeforces! ☀️☀️☀️

We are glad to invite you to our second Div. 3 round, which will take place on Nov/17/2023 17:35 (Moscow time). The round will be rated for all participants with rating less than 1600.

You will be given 7 tasks and 2 hours 15 minutes to solve it.

The tasks were prepared by zwezdinv, meowcneil, EJIC_B_KEDAX, Sokol080808 and molney.

Remember, that only trusted Div. 3 participants will be included in official standings. To qualify as trusted participant you need:

  1. Participate in at least five rounds (and solve at least one problem in each of them)
  2. Do not to have a point 1900 or greater in the rating

We would like to thank:

Good luck everyone!

UPD: Editorial

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

Comments Comments (157)
| Write comment?
»
13 months ago, # |
  Vote: I like it +58 Vote: I do not like it

As a tester I recommend you to participate in round, and don't forget to read all problems statements

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

    the codeforces round 881 div 3 which was by the same setters was also a really good round !!! hoping for a positive delta :)

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

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

    This is one of the best DIV 3 rounds I have ever participated in. Thanks for organizing such a great round!

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

As a tester, I recommend you to take part in this round!

→ Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it +32 Vote: I do not like it

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

as a tester, this round is awesome

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

    as a setter, this round is awesome

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

      as a setter’s friend, this round is awesome

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

        as a setter's friend's friend, this round is awesome

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

          as a reader , this round is awesome

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

            as a reader's friend this round is awesome... TNT

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

              as a contestant, this round was amazing.

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

                as a contestant's not friend, this round was awesome.

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

                  as a human being, this round was awesome.

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

As a tester, this round is very rofl.

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

as a not tester, I hope this round will be great

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

Does participating in at least five rounds count this round? Because I have been in exactly 4 contest before this :D

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

petition to give Gornak40 black handle (as he is, in fact, huge male gorilla) :spinning_gorilla_emoji:

→ Reply
»
13 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Score Distribution?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope everyone enjoys this contest ^_^

→ Reply
»
13 months ago, # |
  Vote: I like it -38 Vote: I do not like it

Good thing that Gornak40 didn't create the tasks too, his problems are special

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

    Don't be rude, most of his problems are pretty funny!

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

Green testing crying in the corner

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the contest page shows 2 hrs but in the blog page shows 2 hrs 15 minutes how is it possible?

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

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

CR7 > MESSI

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

Coming back to give contests after long time, feels good to be back!!

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

I hope this round will help me reach 1200+ rating. As a participant, I wish you good luck!

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

hope this round will help me reach cyan

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

I really enjoyed your first div 3 round (Codeforces Round 881 (Div. 3)). Very much looking forward to this one =)

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish I could be a pupil tonight！！！

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester I recommend you to participate in round, and don't forget to read all problems statements, it can be usefully)))

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

m1, m2, m3 codeforces sites are not working.

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

Thx. Very nice round. Enjoyed problem G alot!

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

    What is so special about it?

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

      I liked mixture of merge sort tree and dfs. Maybe it was not intended, but i liked my solution.

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

        I solved same way, it's good problem tho, i'm not saying it's bad problem

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

    can you tell me ur idea to G ?

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

      contest running bruh :|

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

      Well, lets count $$$tin$$$ and $$$tout$$$ ($$$tin_v$$$ = first time we entered vertex $$$v$$$, $$$tout_v$$$ = time we leaved vertex $$$v$$$ completely). Vertex $$$u$$$ is an ancestor of $$$v$$$ if and only if $$$tin_u \le tin_v$$$ and $$$tout_u \ge tout_v$$$, but $$$tout_v > tin_v$$$, so it brings us down to this condition: $$$tin_u \le tin_v \le tout_u$$$. Now lets make every $$$p_i = tin_{p_i}$$$. Every query we need to see if there is a number from $$$tin_x$$$ to $$$tout_x$$$, that is included in segment $$$[l; r]$$$. This can be done using segment tree in $$$O(log^2n)$$$ per query.

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

    But why constraints in F are so low? My solution is linear with 10 lines of code...

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
      ← Rev. 2   Vote: I like it +15 Vote: I do not like it

      How do you verify that the answer is correct faster than $$$O(n^2q)$$$?

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it -9 Vote: I do not like it

        We build a bamboo tree and just hung $$$n$$$-th vertex to $$$d$$$-th. In this case path from $$$n$$$-th vertex to $$$1$$$-st vertex will be exactly $$$d$$$.

        → Reply
        • »
          »
          »
          »
          »
          13 months ago, # ^ |
          ← Rev. 3   Vote: I like it +16 Vote: I do not like it

          You didn't understand my question. How does the contest system make sure that your output is correct faster than in $$$O(n^2q)$$$? They can't assume everyone will use the bamboo solution.

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

            Oh, okay, i got it now. Thanks

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

Didn't notice that only people competed in 5+ rounds are rated......

Already spent 1+ hour on the 7 problems

Sad QAQ

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

    That qualification is for being a trusted participant.

    "The round will be rated for all participants with rating less than 1600"

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

      Yeah, I understand the constraint. I really enjoyed the 1+ hour anyway

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

B,C >> D,E

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

    pC has tedious implementations. I'd say E is quite easy as I solved it in 10 minutes (compared to 80 minutes for C).

    However, B and C are easier when it comes to finding ideas. However, proving your idea works and implementing it makes it a lot more difficult, compared to E (can't say anything about D).

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the intended solution to G? The only two solutions I could think of seem completely overkill:

  1. Merge Sort Tree on DFS order times of the inverse values of the permutation.

  2. SQRT Decomposition on whether each node is a parent of at least one node in the buckets $$$[p_1, p_{\sqrt{N}}], [p_{\sqrt{N} + 1}, p_{2 \cdot \sqrt{N}}], \ldots, [p_{k \cdot \sqrt{N} + 1}, p_n]$$$. For the upto $$$2 \cdot \sqrt{n}$$$ remaining nodes that don't lie completely in a bucket check them each in $$$O(1)$$$ using dfs order ancestor checking.

Is there an easier approach?

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

    Euler's tour

    → Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Can you explain why my Mo's algo solution gave TLE on test case 15.Submission

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

    I think sack (DSU on tree) is easier

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I tried implementing Sack (DSU on trees) along with Segment Tree for point updates and range queries but I was getting TLE'd.

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

    Author's solution was MST on DFS order.

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

      You scared me with MST... I thought you were talking about Minimum Spanning Tree, before i read the editorial...

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

        Actually, i have no idea how you can do minimum spanning tree of dfs order... But we'll skip that point

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

    I used a persistent segment tree with DFS order to pass G.

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

    consider DFN.

    We call the dfn interval of the i-th node's subtree is dfn[i] ~ dfp[i]. also we call the dfn[p[x]] is pdfn[x]

    So for a query l r x, we're actually querying is there any pdfn[l~r] in the dfn[x]~dfp[x].

    We can take all queries offline and use seg tree queries

    https://codeforces.net/contest/1899/submission/233153059

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

    It's possible to use small to large merging. Instead of adding a node's ID, add the position in which its ID appears in the permutation. Then a query can just be solved by binary searching on the set of values at each node.

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

    I solved it answering query offline with DSU

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E was easier than B wtf

→ Reply
»
13 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Problem F,on example,2nd test case, in the third query already exist a path with distances 3 between 2 leafs , 5-4-2-3, but the answer wasn't -1 -1 -1.I'm receiving WA veredict for that?

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

Greedy-forces :)

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

oh f i just solve G 1 minute after contest time woooooooow

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

I finished the G at the last minute, and because I forgot to write "return 0" ,I got compilation error and I passed it only 1 minute after the contest.

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

    it's very sad... Good luck in next rounds. My friend got same situation with E

    → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

In D it's hard to prove that 1 and 2 the only correct combination without same numbers. Bad problem in my opinion.

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

    Its not that hard to prove :

    Condition of the problem is equivalent to $$$a_i/a_j = 2^{a_i}/2^{a_j}$$$

    WLOG assume $$$a_i>a_j$$$, we get $$$a_i/a_j = 2^{a_i-a_j} \leq 1e9$$$ $$$\iff a_i-a_j <= 30 \iff a_i/a_j \leq 30/a_j+1 \leq 31$$$

    $$$2^{a_i-a_j} \leq 31 \iff a_i-a_j \leq 4 \iff a_i/a_j \leq 4/a_j + 1 \leq 5$$$

    $$$2^{a_i-a_j} \leq 5 \iff a_i-a_j \leq 2 \iff a_i/a_j \leq 2/a_j+1 \leq 3$$$

    $$$2^{a_i-a_j} \leq 3 \iff a_i-a_j \leq 1$$$

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

come onnnnnnn if the time was just one minute moreeeee ohhhhhhhhhhhhhhhhh

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

One of the easier contest I've had in a while

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem Statements are too hard to understand.

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

low quality problems on Greedy_forces

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

In G, if It is guaranteed that the sum of n and the sum of q over all test cases do not exceed 1e5. shouldn't Binary Lifting work?

I got TLE on TC 10. My Submission

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

    bruh the sum of $$$q$$$ over all test cases do not exceed $$$10^5$$$, not the sum of $$$r_i - l_i$$$

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

D will appear in my nightmares

other than that, the contest was great

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Free hack : submission

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the solution to D? I observed something that only 1 and 2 matters.. but couldn't get to the solution

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

    ai * 2^aj = aj * 2^ai

    let suppose (aj>ai)

    2^(aj-ai) = (aj/ai);

    now

    aj/ai can be max 1e9, so aj-ai can be a maximum of 30,

    so now for every ai, chek possibilities for numbers in ai+1 to ai+30;

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

O(n log(n)) solution of G using persistent segment tree 233188158

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

$$$O(nq)$$$ solution for G: 233198776

Limits $$$n, q \le 10^5$$$, TL=3sec should be non-existent in 2023 :)

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

    it is hackable right ?

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

      I don't think so, it's $$$\dfrac{nq}{8}$$$ because of vectorization, so should be fast enough

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

        1e10 / 8

        is 1e9 and I know that O(1e9) is at least need 5 second to run

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

          Of course not, $$$10^9$$$ simple operations is very fast on modern CPUs.

          $$$10^9$$$ executions of some complicated code is slow, but $$$10^9$$$ processor operations is fine

          → Reply
          • »
            »
            »
            »
            »
            »
            13 months ago, # ^ |
            ← Rev. 3   Vote: I like it -7 Vote: I do not like it

            I tested your code ON C++ 17 and the code got TL

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              13 months ago, # ^ |
              ← Rev. 2   Vote: I like it +8 Vote: I do not like it

              Pragmas enable vectorization, without vectorization it's just $$$nq$$$, not $$$\dfrac{nq}{8}$$$

              And C++20(64) matters because 64bit compiler can handle 8 integers at the same time, while 32bit compiler can handle only four (as far as I understand)

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                13 months ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                thank you for answering my questions

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

    sad

    → Reply
»
13 months ago, # |
← Rev. 6   Vote: I like it +4 Vote: I do not like it

D could be solved without knowing the fact that only the combination of 1 and 2 is valid.

The statement equivalents to: Count the number of pair (i, j) such that $$$a_i * 2^{a_j} = a_j * 2^{a_i}$$$. Suppose $$$a_i > a_j$$$, then we have: $$$a_i = 2^{a_i - a_j} * a_j$$$. Knowing this, we can loop for each $$$a_j$$$, how many $$$a_i$$$ could satisfy this equality, and add it to the answer. The case when $$$a_i = a_j$$$ should be handled separately. My solution: submission

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

First contest I could fullsolve, wow!

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really great round! In my opinion, the condition of problem D was too confusing, but the problem is still good

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

What will i receive when i hack a problem successfully?

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

Problem D is fun to understand the statement and enjoyable to solve, I really like it!

Thank you guys for the contest!

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B was difficult to understand

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me why people having fewer solve count and people having same solve count and high penalty have better rank than me. Thanks!

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Which data structure do I need to know to solve G?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Found a cheater Salman_Johir. This 233189111 is his submission. He copied this code from this video's code. Look at the both code. He just has changed the variables' name.

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

    come on problem C is just an application of a known algorithm

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

      Problem C is an application of a known problem, but if you check the code of the video and the code of the cheater Salman_Johir you will see: Their code is exactly same, code with 10-12 lines can be coincident due the algorithm,but if you give it a check you will see every bit of the code is similar.

      And this guy's contest number 904 was totally copied and his both solutions were skipped!

      Check here

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

        kid,focus on your goal not others.good luck

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

          This is why you're still newbie. Imagine cheating in div3 rounds. Skill issue.

          → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

very week pretest in problem C

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

Thank you for the problems!

It's nice there is a short and witty solution to each one (except G).

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

i got an O(n) solution that was hacked for problem D (TLE). The official solution is O(nlogn). Anyone throw some light on this? https://codeforces.net/contest/1899/submission/233176732

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Unordered maps can be hacked because of how collisions are handled. You can use custom hashing functions as parameters to the unordered map to solve that problem. 

    struct custom_hash {
    static uint64_t splitmix64(int64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(int64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
typedef unordered_map<long long, int, custom_hash> safe_map;
    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My submission for D got hacked https://codeforces.net/contest/1899/submission/233134841. Is it cause I used unordered_map instead of map? :)

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

    Nope, but rather because you are using int to store the number of pairs.

    Think about worst case scenario, if I put all the $$$N$$$ values of array $$$a$$$ equal to $$$2$$$, then the number of pairs would be $$$N*(N-1)/2$$$, ain't it?

    And $$$N$$$ can be upto $$$10^5$$$, can u store this value in int? or do u need to use another data type?

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

      I have defined the macro #define int long long Btw hacked by TLE not WA :)

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

        Oh! I did not see that!!!

        Then it must've been the notorious unordered_map collisions resulting in $$$O(N^2)$$$ time complexity from $$$O(NlogN)$$$

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

          Here 233255221 it works by using custom hash for the map.

          Never ever use raw unordered_map in contests, always use the above custom_hashed_map.

          You can read more about it in this blog.

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

You didn't write that there would be hacks...

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

got AC on Problem C during contest but got tle on system testing......?isn't its complexity O(n)!!!

Code : 233167945

UPDATE:: got TLE because of "auto" iterator!

TLE : 233167945

AC : 233276048

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

    No, it's not; you have a nested loop when you iterate through vector v.

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

      overall it would check not more than n times r nested loop is used for the alternating subarrays so it wont iterate over n time

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

        Well, then how else do you explain your TLE?

        → Reply
        • »
          »
          »
          »
          »
          13 months ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          For "AUTO" iterator

          TLE : 233167945

          AC : 233276048

          Thank you for replying!

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

            Either way, your code is not $$$O(n)$$$. Your new submission just passes, when in reality an $$$O(n)$$$ solution would take ~60 ms to pass.

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

              the exact submission got AC after resubmitting?

              AC : 233277883

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

                Basically, you got unlucky because it got TLE during system testing (There is no guarantee that it will run with the exact same time every time, because computers don't work like that)

                But 982ms/1000ms should give you a hint about why there is a high chance it will get TLE and need to optimize your algorithm

                → Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 6   Vote: I like it 0 Vote: I do not like it

    The AC code passed in 982 ms / 1000 ms, that's very very close to the time limit. Maybe the use of the range-based for-loop had something to do with your code getting TLE, maybe it didn't. We can't really know since if your code is that close to the time limit, even the same exact code can pass on one submission and get TLE on another.

    If you're wondering why your "$$$O(n)$$$" solution is on the verge of TLE, it's because you create an array int a[MAXN]; every test case. Creating and initializing an array of length $$$n$$$ is $$$O(n)$$$ and since you're initializing an array of length $$$MAXN$$$, the time complexity ends up being $$$O(t\cdot MAXN)$$$ which is quite slow.

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

    Same... I guess Its just a system failure :\ 233286944

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

      Even though I'm using an unordered map. Everything should work just fine.

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

      And to be honest, I dont even understand why in the contests where the all problem tests are executed during the online sumbmission, the "aftertesting" is the case.

      → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Best contest

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

it was interesting. but, i wasted time to search something good to solve problem B, i thought to bruteforce that 'k' at first, as it was.. but don't know why i felt that stupid and moved to C:). Now i saw it's E was easier than that, it was likely not arranged in increasing difficulty :) also, i felt C easier than B.

→ Reply
»
13 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Can someone explain what is wrong with my solution? My O(n) solution for D got hacked https://codeforces.net/contest/1899/submission/233160169

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

    I'm not a python user so I can't get you an 100% precise answer but : - I found that dictionary using only string keys are way faster than other dictionaries, this would have been enough to get you an AC : https://codeforces.net/contest/1899/submission/233292415 - It's also faster to use pypy instead of python3 (there is even a warning when submitting a code)

    As for the reason of your code being too slow, i tried to rewrite your sum a couple times and couldn't find anything way faster than what you wrote so it's most probably the insertions in the dictionary that are too slow. I saw that the worst insert case is 0(n), which happen if there are tons of conflict in the hashmap. So maybe the hack that got you to be too slow is designed to create lots of conflicting keys... This last part is a guess but I thought the first part was worth sending this answer.

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell why my O(n) solution got tle on problem D. https://codeforces.net/contest/1899/submission/233294769

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please some help me. my rank in common stading is 2198 But in friend standing and profile contest page it is 2619 and and my rating change is calculated on 2619 rank

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

    Common standings, when "unofficial participants" is off, doesn't show all rated participants. From the announcement:

    Remember, that only trusted Div. 3 participants will be included in official standings. To qualify as trusted participant you need:

    • Participate in at least five rounds (and solve at least one problem in each of them)
    • Do not to have a point 1900 or greater in the rating

    Regrdless of these extra restrictions, the rouns is still rated for everyone with < 1600 rating. Your rank among all rated participnts is the 2619, but your rank among trusted participants is 2198.

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

      Thanks bro but i still have a doubt. Participants near 2619 rank have lower solve count than me and participants near 2198 rank same solve count and penalty as mine and still my rank is below to those who have solves less problem than me. Sorry for annoying question and terrible english

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

        The people around 2619 in the trusted participant standings also have a lower rank among all rated participants:

        Your rank among trusted participants (link):

        Your rank among all rated participants (link):

        Near 2619 located random guy's rank among trusted participants (link):

        Same random guy's rank among all rated participants (link):

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

          Thanks bro! If don't mind please give some guidance to me regarding cp

          → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Attention!

Your solution 233122161 for the problem 1899C significantly coincides with solutions sk.dubey/233122161, 21H51A6655_/233126912, ayush_1217/233140420, sudhanshu_2306/233141014, mokamal2003/233141318, quantum_quill/233144312, Dineshsingh10001/233146424, huseyn_quliyev/233146946, fuck_23/233147330, mostakem123/233147919, Ritesh027/233148153, vaibhav0543/233148375, artemfad/233148803, akpalert/233148863, sihare_123/233149177, ayushverma150702/233149667, kanikapunia119/233149712, Anonymous-2002/233149818, Ooppa/233149911, Shreshth/233150012, zakeer_shaik/233150023, jaikiran1027/233150227, gaurang_07/233150492, MADARA1287/233150624, aashish1110/233150766, krishnaP/233150907, O-G/233150925, saurav_24/233151260, Crypto_Wiz/233151484, ajaykumar2004/233151824, ankitsingh7979092/233151869, saigowthamkumar011/233152117, QuickSilver/233152299, ashisharyan/233152315, shivamjha/233152449, Vivek_117/233152467, MK2001/233152516, Vishnu_Shukla/233152625, i_ayush23/233152627, vishalgoud_777/233152721, pratyushraghuvanshi73/233152789, am_2002/233153165, AdarshPandey_24/233153187, ArsheeyaTabassum/233153292, kalluboiiii/233153350, saideepu5692/233153507, 21b01a0526/233153853, Vedula_Aakanksha/233153939, hiteshkumar8642/233153988, Gismodos86/233154249, vishal22101/233154272, mani_gsn123/233154292, Krishnendu016/233154388, rijuoddusual1999/233154603, Hitzjack28/233154628, yashasrikommu/233154943, Gen_Raiden/233155200, 21H51A0557/233155230, priyanshu_kumar/233155254, naruto2022/233155484, ayush_agr0311/233155989, jaiwanth/233156185, FakeCheck/233156461, ashraful_ridoy/233156638, Sadanand26/233157829, Sandeep_Tripathi/233158057, cosmodivine/233158176, aniket_main_/233158715, devil_1627/233159058, nullifier24/233159145, pankaj001/233159970, mamalak08/233160008, akashmaity57/233160166, zddtuus/233160574, BethHarmon/233160824, Harish_74/233161058, Nullpinter/233161472, roytijesha_30/233161900, manoj_kumar__10/233162028, itzkamal22/233162197, Harshitsingh30/233162730, saurabh033/233162777, sameer693/233162943, ja_g_an/233163193, yoshith/233163562, smfaizalam786/233163821, gauravsingh9864/233164082, sauravmh/233164326, imyash_b/233164337, HayatKoujan/233165365, praghavendar/233165583, Aparna165/233165627, SilentSpecterCode/233166087, arifakhtar51/233166627, uncool/233166850, 228r5a6620/233167211, IndianPsycho/233167868, AnialwaysOP/233168083, nithin93/233168736, mynameone/233169012, xcoderdevesh/233169033, Sangeetha_87/233169375, rahul__04/233169658, harsh___mishra/233169692, GoD_GaMerS/233169748, YAGNAPRIYA_2004/233169775, rushikesh_kotkar/233169998, c_dola/233170299, Gaurav_17/233170303, Vaibhav__Prasad/233170399, kiran_2244/233170630, Addictiveboy/233171085, Vaibhavp22/233171185, mnish_0.9369/233171432, Vishwas23/233171627, madhurgupta12/233172083, bvrith_95/233172398, jaythakor/233172632, bdbhatt01/233172642, maharshi1712/233174750, harshitchopra09/233174763, sumanth43028/233174807, yousofkortam/233174877, Terminator2004/233175070, chuvya_24/233175081, gupta05/233175542, A.Hazem_2003/233175598, aadi900/233175898, lakshmi_sowmya/233175992, deepanshu.26.g/233176074, Cpp_Master/233176451, SSingh_248/233176571, isham_026/233176598, Priyank295/233177099, AhmedLaithy/233177384, sanskar.resoluteai/233177489, suraj9192/233177560, HardCoder404/233177647, pravallika1805/233178427, kishanthakor/233178717, vinit__jha/233179019, tesla_11/233179191, komalkbairwa/233179363, NITHINKRISHNA/233179422, Mahin273/233179551, Yuvraj_17/233179572, aakash_811/233179605, ritu_raj_07/233179950, Perhac/233179955, crack__/233180114, falcoln/233180457, sharmahimanshu/233180660, sadhukhansubham588/233180881, mdmahfuzahmed2223/233180900, 21h51a7326/233180993, ankit7890/233180996, gin_spirit/233181047, sidhart25/233181535, AGOLAPUAMULYA/233181573, aryankrsingh4/233181649, vigneshdvs/233181691, Medhavi_Sahgal/233182302, suka_gehu/233182574, tejateju69/233182741, amaanahmad52/233182742, sowmya_04/233183322, mohamed_eltaweel/233183364, gugajcvda/233183394, Aryan_a1996/233183486, uday03meh/233183491, hawdiatarun/233184376, sabbirkhanoni/233184675, manasraj007/233184991, -.........__/233185098, anuragthakurNitrr/233185294, comalonwizme/233185303, verma.shivam2605/233185657, drynor/233185824, giriramireddy/233186059, hexaoctalai/233186216, CMRIT25_21R01A7301/233186650, 777_Raju_Ranjan/233186919, beanomahto/233188428, utkarsh_tyagi437/233188469, sudoaptrana/233188779, anoosh_op/233189369, shivansh2611/233189616, Ahmed_Mahmoud2/233190016, A_mish/233190062, Snehal652/233190096, _Mridul/233190188, rishabh0903/233190516, captive_geek/233190897, subba_reddy13/233191688, kanishks281/233193052, Zakir060/233193086, vishalsaw1092003/233193258, pavanjadhav17/233194069, pyansu07/233194321, blitzzz15/233194411.

I am writing this post in response to the accusation of plagiarism during Codeforces Round #909 (Div 3) for Problem C. I want to express my genuine concern and assure everyone that I did not cheat during this contest.

Firstly, I want to highlight that as an Expert-rated participant, the contest was unrated for me. There was no incentive for me to cheat in a contest that wouldn't contribute to my rating. Moreover, I have consistently participated in Codeforces contests for over 1.5 years, and my commitment to fair play remains the priority.

Regarding the code similarity issue, I understand that there are resemblances between my code and that of others and the number is really huge (I'm shocked too seeing that). However, I want to clarify that I used a portion of the maxSubSum function from GeeksforGeeks. I am unsure whether this is permitted on Codeforces, but I take responsibility for not explicitly mentioning the source.

I urge you to please review my coding style, variable names, and previous submissions. You will find that while I might have used a common algorithm or function, the overall structure and approach are uniquely mine. I also noticed similar solutions from high-rated coders in the contest, which adds weight to my stance.

I want to emphasize that I have learned from my past mistakes during my initial days on Codeforces. I was involved in plagiarism in two contests when I was a Newbie, but I have since rectified my approach and have strictly adhered to honest coding practices. My friends and family know how dedicated I am to problem-solving, I miss family gatherings just to give CF contests. It is my hobby. I

I genuinely fear the possibility of my account getting permanently banned for an unintentional mistake. I fear because I have been working hard to achieve milestones on my account. I feel happy whenever I look at my graph which shows my commitment to CP and fear losing motivation and strength. I can get back to the same rating by creating a new account but this profile shows my struggle and journey.

I urge the Codeforces community and administrators to thoroughly investigate the matter. And I apologize for using third-party code. Please!

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

Hi. I got a plag which I think is wrong, the links to both the solutions are —

his — 233160268

mine — 233148751

The question itself was very basic and majority of the solutions had same approach but even then, both of our solutions are very different and only thing that match is the mantra at the top which is a very famous mantra. Please remove this plagiarism and make this round rated for me once again.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Lmao, guess I gotta write about it here. I got a system message about coinsiding solutions with kiyomaru28 (233110440 — 233185978 and 233115355 — 233171404). The solutions literally have nothing in common other than a giant ASCII art, wich I use in all my codes, that are available on codeforces for everyone to see (one of the first uses: 228909025), except that for some reason they credited a different person for the original art.

No idea how codeforces system desided that it's cheating while a lot of people probably use giant headers, like AtCoder one or something from top competitors here and have no problems with it

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    yea, the exact same thing happened with me as well... I guess they only plag check headers now .. and not bother to look for what is inside.

    → Reply