s_jaskaran_s's blog

Codeforces Round #841 (Div. 2) and Divide By Zero 2022
By s_jaskaran_s, 23 months ago, In English

Hello, Codeforces!

The Programming Club, IIT Indore is proud to present the 8th edition of its flagship event, Divide By Zero — Codeforces Round #841 (Div. 2) and Divide By Zero 2022, under the annual code-fest, Euristica'23.

You can check some of the previous editions of Divide By Zero prepared by us : Codeforces Round #399 (Div. 1 + Div. 2), Codeforces Round #474 (Div. 1 + Div. 2), Codeforces Round #714 (Div. 2).

The contest will take place on Dec/27/2022 17:35 (Moscow time). This round will be rated for all participants with a rating lower than 2100.

People who had a great contribution to making this round possible:

You will be given 6 problems, and 2 hours to solve them. The points distribution will be updated later.

UPD1: Score distribution is 500 — 1000 — 1500 — 1500 — 2000 — 2750

UPD2: The editorial is up.

PRIZES: Twenty T-shirt will be given to:

  • Top 10 Indian Participants

  • Random 10 from top 100 (rank 11-100) Indian participants

Hope you guys enjoy the contest! See you on the leaderboard :P

About Euristica

Euristica is the annual flagship programming event of The Programming Club of IIT Indore. As part of Euristica, we conduct a variety of online competitions spanning different programming domains. These events are open and free for all, and there will be exciting prizes and goodies for the winners.

Head over to our website to find out more about the competitions.

UPD3: Here is the list of winners who won T-shirts. We will contact you guys soon. Congrats!

Top 10 Indian Participants

Random 10 from top 100 (rank 11-100) Indian participants

We have uploaded the link to the code for generating random numbers and ranklist here.

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

Comments Comments (259)
| Write comment?
»
23 months ago, # |
  Vote: I like it +47 Vote: I do not like it

As a tester, I am first.

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

Top 10 Indian Participants

Rated ? Unrated ? Also, do we have to register anywhere to be eligible for prizes ?

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

    It's rated of course. And no, you don't have to register, we would contact the prize winners.

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

      To clarify what the previous commenter meant, prizes are only for rated contestants?

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

        No, the prizes are for all the Indians, irrespective of the rating.

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

    Thanks to the authors for this amazing div 3 round!

    → Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it -52 Vote: I do not like it

:sadge:

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

Am i indian or not ? How will you find out?

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

    based on whether you will cheat or not

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

    Ofc you'd have to keep your nationality as Indian for that. We will be asking you for details like mobile number and address.

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

My first contest

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

As a tester, problems are quite nice and I feel like you can learn from this round, especially if you are newer to CP.

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

Why are gifts only for Indians ):

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

    Because its kinda impossible for us to deliver them overseas keeping in mind the cost and tediousness of that.

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

Why only 9 testers? Also why only 5 div2 testers?

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

As a debut tester, I am confident you will enjoy the problems.

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

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

T-shirt! :)

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

Finally, my first unrated div 2. Yaaaaaaaay!

I waited a whole year to become LGM :)

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

Good luck to all participants.

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

great initiative from IIT Indore. I appreciate that :)

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

Hope to not find any problems related to binary strings, had enough of them in the past contests

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

All the best everyone

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

Just checking my rank

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

I need pants!

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

Well,so good,this is my first round on CodeForces.

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

I am looking forward to the problems of this contest, hoping to surprise me.

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

just curious what happened with codechef?

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

Finally contest after long time..

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

best of luck everyone going to participate after a long time

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

Hope to have a great round!!!!

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

glhf!

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

Hope i will get a +ve delta, multiplied by 2022 too.

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

madarchod b problem first telling take modulo after and ans comes after taking modulo #badproblemsetting #reporttostter

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

    I face a lot of difficulty in solving in c++ than I coded in python

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

      There is no restriction on the size of integer in python right?

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

Trash Indian round, no even one interesting problem on the problemlist.

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

    Even though you have solved max of the problems!!!! Indian rounds are quite good but this one was little bad

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

Totally a trash round. This was not expected from my people

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

C is very frustrating

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

Problem B, with C++ wasted alot of time while fixing for large input.

2022 was divisble by 6 .. was good while using it at last !!

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

D < C

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

Time limit too strict for C

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

Thanks for the contest! Even though problem B is a little bit too cringe in my opinion, problems D and E are really interesting!

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

Print your final answer * (seconds passed since 1 JAN 1970). Why multiplied by this ? Because we are never gonna see this number again!

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

I envy those who did not participate in this trash round.

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

    Did you create a new account just to hate this round? really? xd

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

C and D are the worst problems ever existed. Eager to give up cp after doing those

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

My solution O(count_of_squares_up_to_(1<<18)=450 * n) for C TLE'd in java :( What was the intended complexity?

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

How to solve D ? -_-

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

    Do binary search on $$$l$$$. Now you need to check if there is a square of size $$$l$$$ with all $$$a_{ij} \geq k$$$. To do so, we can find the maximal square and just compare its side to $$$l$$$. Finding maximal square is a well known DP problem and can be solved in $$$\mathcal{O}(nm)$$$. Total compexity $$$\mathcal{O}(nm*log(n))$$$

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

What's the solution for F?

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

anyone how to solve B . i got TLE .

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

Can someone explain to me why my code gives WA for n = 1000000000 for problem B? :( 186932175

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

Any hints for D please?

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

Was 'D' a 2D segment tree problem??

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

Was D so easy? Seems like everybody and their mom did it. Best I could think was 2D RMQ then binary search at each point (assuming it to be bottom right corner of square) to find the best L. I think it should pass but haven't ever did 2D RMQs so gave up. What's the intended way?

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

    i also thought the same but sadly dont know anything about 2D segment tree is this a rare topic as i not found much on GFG also ??

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

    Binary search + histogram to find max square removing all numbers <= x (binary search for the answer)

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

      Ah! Leetcode largest histogram. My leetcoding has gotten rusty these days,

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

    Binary search with 2D prefix sums. I’m pretty sure that this exact problem appeared before multiple times.

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

    I did binary search on the answer L. For a certain $$$l$$$, we can decompose the checker function into checking a grid of numbers $$$a_{i, j}$$$ — $$$l$$$ for the largest square of positive numbers, which can be done in O(NM) time using a stack.

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

why is n*1.5 solution for C giving TLE

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

is D a graph problem? How to solve** D**

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

    D is a binary search problem

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

    By using monotonous queue and binary search.

    monotonous queue will help you to find the minimum value of all possible sub-matrices.

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

    Binary search for l and dp for each l.

    When doing dp, let dp[i][j]={r[i][j],c[i][j]}, where {r,c} is the max size of good rectangulars which rightbottom corner is {i,j}. if a[i][j]<l, r=c=0, or we can calculate r,c by value of dp[i-1][j], dp[i][j-1] and dp[i-1][j-1].

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

How to solve E? Any hint please?

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

For the first time, I am regretting using C++ in CP contests.

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

.

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

I solved E by greedy: pretreat the number of edges with each different weight w (w = 2 to n/2), then try to operate for k from n/2 to 2 as many times as possible

However I got WA. My submission:186947754

Are there any counter examples?

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

    Yes I have also considered greedy but I cannot prove or disprove it.

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

    The greedy is true,but your code may is wrong.

    I solve it in 186980785 by C++.

    My code is strange.You only need the last line.

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

Can someone help me with problem C? I was stuck on TLE my idea was to remove the subarrays whose xor are perfect squares from all possible subarrays I generated perfectSquares till the maximumValue xor can take and then solved the problem "calculate subarrays with xor x for each perfectSquare"

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

    Not sure if you used a hash map, but that's what I did initially and I also got stuck with TLE with a O(N * sqrt(N)) runtime. In the end, I replaced hash map with a fixed size array and it passed.......

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

      i tried using fixed size array also. But it was giving tle.

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

        I am not very good at reading C++ code but if I understand your logic correctly, you can do the following optimization with fixed size array.

        First, the max size can be smaller, 2 * N + 1 is enough. Second, you can keep a running maximum of A[i] and its largest set bit index K, this way for each A[i] you just need check all square numbers v * v < (1 << K).

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

      Thanks for the help dude.. Will try this :) Happy New Year

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

      FK that's it :((

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

        Yeah, it took me 4 TLEs to finally try this as my last ditch effort before the contest was over. :(.

        I think some higher ranked participants are saying the time limit is a bit too tight as well.

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

    I did this using a fixed size array and my blind arss couldn't see that the constraint was till 2e5 not 1e5 so ended up doing wrong submission 5-6 times

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

i used magic to be green cause i love the color but it look like there something hidden in that magic i am coming back to green no plz nooo

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

Good bye 2022!

How to do E? I can't think of anything other than Euler.

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

    Yes, it involves using euler totient function. Basically, try adding (k-1) edges of weight k , starting from the largest such possible k. It's a greedy solution.

    As , k = gcd(u,v). So, obviously k <= n/2 .

    Now, what can be the maximum number of edges (u,v) whose weight / gcd will be k ?

    It will be nothing but the total number of coprime pairs upto n/k. Let's save it in a coprime[] array. This can be easily pre-computed using coprime[i]=coprime[i-1]+ euler_totient(i).

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

whats the idea for c?

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

    Find the number of subarrays whose XOR has an odd number of divisors and subtract that from the count of all subarrays ($$$\frac{1}{2} \cdot n \cdot (n+1)$$$).

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

      thanks, but excuse me did you just transform the problem into its complement? sorry i am a little noob but how can this task be easier than the original task

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

        Claim : Numbers having odd number of divisors are perfect squares.

        Enumerating over squares is easier, so you can try devising in O(n*sqrt(N)) solution

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

        First, n has odd number of divisors <=> there's a integer m where n=m^2

        Then we let xor[0]=0, xor[i]=a1^a2^...^ai, then ai^...^aj = xor[i-1]^xor[j]

        Finally, for each 0<=i<=n we look for how many j such that i!=j && xor[i]^xor[j] is square number.

        We just need to use array count[] to store count of each xor(i), and for each square number sq from 0 to 511^2, we check count[sq^xor[i]] (we check count-1 instead when sq=0, because sq^xor[i]=xor[i] this time), then sum it up over all sq, that's number of bad pairs with i.

        Time complexity:O(n*sqrt(max(a)))

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

      legend

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

E was a very good problem.

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

    In fact, the number of coprime pairs is asymptotically about (n/pi)^2 * 6, so it will likely always be greater than nsqrt(n) if it satisfies it for the first few elements

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

I think Problem D is a straightforward 2D segment Tree. ??

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

Problem C was decent from the point of logic and everything, but worst setting of this problem ever, too tight limits.

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

    Why did you use map instead of array? The value of XOR is just $$$10^6$$$ at maximum.

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

      In retrospect, I regret using map.... Had several TLE :(

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

      Used a HashMap though, but still I think the constrains should have been smaller. No need to keep N = 2*1e5 when it can perfectly work on 1e5 or a bit smaller

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

Someone please share a better than O(n^2) approach for problem C!!! I could only come up with that and had 2 TLE errors.

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

    You only need to search the perfect square numbers because only perfect square numbers have odd number of
    divisors.

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

    Let xor[i]=a[1]^a[2]^...^a[i],xor[0]=0

    For each xor[i], There are at most 512 different values of xor[j] where xor[i]^xor[j] is square number. So we just need to store the count of each xor[i] (i = 0 to n) and check the count of (sq^xor[i]), where sq is square numbers from 0 to 511^2.

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

How to solve C ? my conclusion: Max value of Xor of a segment can't be larger than (1 << 18 — 1) , so we can check every number between 1 and (1 << 18 — 1) if it has even number of divisors or not, that will take about (1 << 18 — 1) * sqrt(1 << 18) which is acceptable.

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

    Think about when a number has an even number of divisors and which numbers are those. Could there be some reason for that?

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

D is just https://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/ and binary search on answer.
Too standard for a Div 2D

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

Can anyone tell me why this solution didn't pass?

https://codeforces.net/contest/1731/submission/186950096 MikeMirzayanov

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

    Because the time limit exceeded. Your code must be able to solve the problem (within the specified constraints) within 2.5 seconds. Your submission was not able to do so.

    If you want any useful feedback, I suggest that you briefly explain your approach and trim your code to remove all unnecessary components, so that anyone reading your code can more easily see what you're actually doing. For this problem in particular, you need a time complexity of $$$O(n^{1.5})$$$ or better. Notably, a $$$O(n^{1.5} \log n)$$$ solution (that utilizes a map/dictionary, which is quite a common attempt) generally should not pass.

    Also, why are you tagging Mike for this? This is not an issue with Codeforces; it's an issue with your solution. Even if you genuinely believed there was an error in the system testing (which is quite absurd when over 2000 people have solved it during the contest), you should be notifying those who prepared the contest, not Mike.

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

I came up with a solution for F that goes like:

do polynomial DP where $$$dp[i][j]$$$ is number of sequences of length $$$i$$$ with exactly $$$j$$$ elements greater than $$$x$$$, where $$$x$$$ is the variable of polynomial. Similar for less than $$$x$$$.

Then to compute answer, we have to sum over powers, which can be done using 622F - The Sum of the k-th Powers.

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

    anyway to do it w/o interpolation :(

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

Is the optimal path in B the path that goes through the middle? If yes then the answer is $$$2022\cdot$$$ [ $$$2\cdot$$$ sum of all squares with $$$base\leq{n}-$$$ sum of all numbers up to $$$n$$$ ] which is $$$2022\cdot\frac{4n^3+3n^2-n}{6}$$$. Now that needs to be output modulo $$$10^9+7$$$. How to do that?! I tried many times but none of them worked...

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

    search for division modulo a prime

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

      Already tried it during the contest, got WA. What did I do wrong? (code).

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

        To do the mathematical mod, you need to compute (x% MOD + MOD) % MOD in the case where x is negative. So line 32 seems incorrect

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

          But in line $$$31$$$ I am making sure $$$rj$$$ won't become negative?

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

            rj could have been negative before line 31, so you need to do while(rj < n)

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

              How? $$$rj$$$ is at least $$$0$$$.

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

                First of all, n^3 itself goes out of long long limit, so anyway you would get wrong answer.

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

                  Yes, but the function power computes $$$n^3$$$ mod $$$10^9+7$$$ so it won't overflow.

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

                  But, then what if power(n, 3) > INT64_MAX / 4

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

                  $$$power(n,3)$$$ is at most $$$10^9+6$$$ which is less then INT64_MAX $$$:4$$$ since INT64_MAX $$$:4$$$ is 2.305843009213694e+18.

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

                  Okay, your code is correct, but the formula you have got is wrong. Actually it should be 2 * (sum of all squares with base <= n) — (sum of all numbers up to n)

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

                  Actually, my formula is correct. It's just written differently. Even 2368 rated person got this formula (comment).

                  But now I got AC, thank you for your effort.

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

      No need for division; 2022 is already divisible by 6, so just multiply that part with 337 instead of dividing by 6 (and don't multiply that part with 2022 later).

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

    __uint128_t (it worked for me)

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

    The optimal path is a zigzag path through the middle, which is the sum of the first $$$n$$$ squares + sum of $$$\sum_{i = 1}^{n - 1}{i(i + 1)}$$$. The first part is $$$\frac{n(n+1)(2n+1)}{6}$$$ while the second part is $$$\frac{n(n+1)(n+2)}{3}$$$, but since we sum up to $$$n - 1$$$ here it becomes $$$\frac{(n-1)n(n+1)}{3}$$$. For the modulo division, in this case we don't need to do anything fancy with the observation that 2022 is divisible by 6 and 3, so we can just multiply by 337 and 674 respectively.

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

      i did the same.. but in 1000000000 ans is incorrect.

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

        I had a slight typo in the formula I typed above. Maybe now it helps fix your issue? Here's my submission: 186895976

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

    Note that $$$2022$$$ is divisible by $$$6$$$...

    Then calculate $$$337 \cdot (4n^3+3n^2−n)$$$ taking modulo each time you multiply or add(sub) any pair of numbers, for example: $$$ n^3 = (((n \cdot n) \bmod{M}) \cdot n) \bmod{M}$$$ and so on.

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

Fuck me

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

Problem B is exactly the same as BAMO 2017/3

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

Oh well. After only solving A and B, I'll be excpecting a crap ton of -ve delta. I had finished A snd B in just 12 minutes, but I just couldn't come up with a fast enough angorithm for C and didn't have time for D (also no ideas for D). Hoping for better luck next time. But it was not a bad contest.

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

Valiant >>> valorant

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

On problem E:

Only need to search for it and find this comment on CF:

https://codeforces.net/blog/entry/55822?#comment-591656

ps. I had runtime error on test 1 several times because of Divide By Zero. 186946890

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

can someone tell me what's wrong in this. i am just literally doing whats told and taking modulo in the end


t=int(input())
mod=1e9+7
while t:
    n=int(input())
    ans=((n)*(n+1)*(2*n+1))/6
    n-=1
    a = ((n)*(n+1)*(n+2))/3
    
    ans = (ans+a)
    ans=((ans*2022)%mod)
    
    # ans=int(ans%mod)

    print(int(ans%mod))
    t-=1
→ Reply
»
23 months ago, # |
  Vote: I like it +29 Vote: I do not like it

For problem E, after counting the frequency array of GCDs, I used the greedy approach of taking the higher weights edges (as that will result in lower cost).

I did this based on the intuition that small GCDs will occur a lot more than higher GCDs, so if it's possible to get m edges, it should be possible by this greedy approach. Can anyone provide any formal proof for this why adding m edges will always be possible by this greedy (Ofcourse for the case when it's possible at all)?

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

    Suppose that by adding from biggest to smallest, we try to add edges of values $$$i + 1$$$, which can be added as blocks of $$$i$$$. At this point, we either use all of these edges blocks and reduce $$$m$$$ (the number of edges that we need so far), or we use some blocks of size $$$i$$$ and leave some blocks unused. In the latter case, $$$m$$$ will be reduced to a number which is $$$ < i$$$, therefore it will be possibile to use smaller blocks.

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

      That's incorrect.

      Let's say if you have three numbers to be taken 2 2 3 and target sum is 4. Then if you take 3 first, you won't be able to make the sum 4 which is otherwise possible by taking 2 and 2.

      Proof would possibly be around the idea that frequency array such as I provided in counter-example above isn't possible because of the fact/property that our frequency array is GCD of all pairs from 1 to N. But I am not sure how to formally prove that.

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

        Maybe I wasn't very clear, but with your example, if we take $$$3$$$, then we would be missing $$$4 - 3 = 1$$$, which is always an available block. That would be a pair of nodes with $$$gcd(i, j) = 2$$$.

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

          Actually, no matter what your proof is, if it's not using GCD property it's wrong. Because without that it can be just any random array for which greedy won't work.

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

            Oh I understand, it's a matter of proving that smaller values have at least one block, which for some reason I assumed to be true, but it's not too trivial to prove I think. The editorial doesn't prove this part unfortunately.

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

      To fix this proof, we just need to assume that we can add any number of edges up until the maximum number of edges possible to add at once. In that case, the values of the edges are just decreasing 1 by 1 so it will always certainly work.

      We surely have all edge of value up until the maximum edge because we have coprime[n/(k+1)]/k edges of weight (k+1) in our graph, where coprime[i] is the number of coprime pairs less than i. This is a decreasing function.

      Thus, this proof applies to our situation — we can add any number of edges from 1 through the maximum number of edges that we can add in a single operation.

      [Rev. 3: Edited proof]

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

        Are you sure about the case $$$n = 6$$$ and $$$m = 6$$$? It should not be possible actually.

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

          Ah, I realize now that I was getting the number of edges $$$m$$$ confused with the total weight of the edges in the graph! So then we do actually have an edge of value 1 because the weight 2 edge only adds a single edge to our edge limit. A lot of what I wrote was confused, I'll edit the post

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

        We surely have all edge of value up until the maximum edge because we have coprime[n/(k+1)]/k edges of weight (k+1) in our graph, where coprime[i] is the number of coprime pairs less than i. This is a decreasing function. ``

        This is what my proof was missing, thanks!

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

ModuloForces

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

ben stokes round bc

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

I tried to get all square summation from 1 to (n-1) then multiply in 2 then added n*(n-1)/2 . extend to this formula 2*n^2 + n . It's work for the test cases but still doesn't work in 10^9.

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

    I multiplied 2022/6 = 337 and 2022/2 = 1011 and it worked. Modulus doesn't go with division

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

in problem B i have applied 2*(sum of first n square numbers)-sum of first n natural numbers,is this correct?

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

Nice leetcode contest

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

I got F's sol but electricity cut when implementing it :(

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

TIL — don't use a map unless you have to

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

For Problem B,

Can anyone help why this code is giving wrong output for n=1e9

t = int(input())
m = 10**9+7
for _ in range(t):
	n = int(input())
	a1 = int((n*(n+1)*(2*n+1))/6)
	a2 = a1-n**2
	a3 = int((n*(n-	1))/2)
	ans =(a1+a2+a3)%m
	print((ans*2022)%m)

All output matches except for n=1e9

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

    The code is giving wrong output because / returns float type, and float causes rounding error for larger numbers.

    I recommend using //. $$$n // i$$$ is equivalent to $$$\text{floor}(n / i)$$$. For example, a1 = int((n*(n+1)*(2*n+1))/6) can change to a1 = n*(n+1)*(2*n+1)//6.

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

      I am dividing after multiplying (n*(n+1)*(2*n+1)). So, this is always going to a multiple of 6. How can this cause rounding errors?

      Did I miss something?

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

        n*(n+1)*(2*n+1) is always a multiple of 6, but float type has no information about whether n*(n+1)*(2*n+1)/6 is an integer.

        It causes rounding errors because float type can keep only a limited number of digits (maybe 53 digits in binary from the top), and when n = 1e9, n*(n+1)*(2*n+1)/6 exceeds the limit.

        n = 1000000000
print(n*(n+1)*(2*n+1) // 6) # 333333333833333333500000000
print(n*(n+1)*(2*n+1) / 6) # 3.3333333383333334e+26
print(int(n*(n+1)*(2*n+1) / 6)) # 333333333833333341369139200
        → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell what is the maximum possible $$$xor$$$ of numbers that goes up to $$$2 \cdot 10^5$$$?

My first answer was $$$2^{18}-1$$$ which is under $$$3 \cdot 10^5$$$ but i got runtime error in problem C when my frequency array was only of size $$$2 \cdot 10^5$$$ or $$$3 \cdot 10^5$$$, but when raised to $$$5 \cdot 10^5$$$ it worked.

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

    The maximum will be all 1s in the binary representation. So it will be 2^19 — 1;

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

      since $$$2^{18} > 2 \cdot 10^5$$$, the $$$xor$$$ of the numbers can't be that large.

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

    I think the reason is not connect with what you're saying.My opinion is that the array overflowed is caused when you perform the operation :Square Number xor (2^18-1).If your Square Number is chosen too big relative to (2^18-1),this will happen.

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

    You never got runtime error when your frequency array was of size $$$3 \cdot 10^5$$$.

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

My N sqrt(N) solution is not passing can you tell me intended time complexity please?

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

    For what problem? In problem E intended complexity is N log N. Reason is that you can compute GCDs in O(N log N) because 1/1 + 1/2 + 1/3 + 1/4 +... +1/N is roughly N log N.

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

    If you're talking about problem C, that is the intended time complexity. Time limit is strict, so if you're using something like a map , try for O(1) alternatives.

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

Chandler trying to give money to Joey

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

Do we have to fill some form to be considered for t shirts?

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

I don't know why I wasted 20 minutes trying to debug my dp solution for B before realising it was a simple math formula :sadge:

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

I literally looked up class 11th ncert maths book online mid contest to get the answer of those two sequences in problem B xD

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

OHHHHHH

I could have solved E but I missed a overflow when doing int32 multiplication......

QwQ

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

Had trouble with taking mod in B so i used BigInt instead lol

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

I reach 2023 problem solving before 2023 year :) Hahaha SHAHEEN

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

Why tasks C and D are so standard? Task C is just prefix-xors, task D is just binary search + RMQ. I don't think such standard approaches are good for a codeforces round.

OK, I'm proposing a codeforces round:

Task A: you are given two integers n and k, find how many i such that 1 <= i <= n and gcd(i, i + k) > 1.

Task B: you are given an array, find count of pairs such that a[i] xor a[j] <= a[i] and a[j]

Task C: you are given an integer n, count number of i such that 1 <= i <= n and i contains two adjacent equal digits.

Task D: you are given an string s and a string t, find count of substrings such that s[i..j] <= t

Task E: you are given a weighted graph, and you have to answer q queries: what is the minimal c such that you can travel from v to w, using only edges with weights less than c?

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

    Raising problems without input scale limit makes nonsense.

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

      Task A: n <= 10^9

      Task B: n <= 2 * 10^5, a[i] <= 10^9

      Task C: n <= 10^18

      Task D: |s|, |t| <= 2 * 10^5

      Task E: n, q <= 2 * 10^5

      → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it 
    Problem C was fine, but D was complete standard problem, more suitable for Edu rounds
I don't know about E.
    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      E is also an extremely standard problem; just generate the MST (because that's how Kruskal works) and then use your favorite LCA algorithm to find path minimums.

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

    This might actually be a decent div 3 with a couple easier problems more at A and B.

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

    $$$A$$$:$$$gcd(i,i+k)=gcd(i,k)$$$;

    $$$B$$$:Use Trie(Is this suitable for the difficulty of DIV2B?);

    $$$C$$$:Digit DP(suitable for DIV2C?);

    $$$D$$$:Binary Search+String Hash(easier than $$$B$$$ & $$$C$$$ imo);

    $$$E$$$:MST+LCA.A problem ten years ago,which appeared in $$$NOIP2013$$$(Provincial contest of Chinese high schools):link.

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

      Task B is actually a task from Codeforces Round 672. It can be solved easily without trie.

      → Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it 
This time I saw pruning, complementary for problem C,
 
I was even trying to exploit the xor property of a^b = c but I am using that property for dp[i][Xor value]
I thought it would be impossible to find subarrays ending with perfect square xor at index i in o(n) time
I missed out the prefix technique of xor which was a standard problem
→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

B was really frustrating.But one who set those examples did a great job by giving a big value. Otherwise we would have end up getting lots of wrong submissions.

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

No offence but these problems are more similar to problems created by 5 or 10 years ago.

D: leetcode style. I like it when I was a teenager.

E: mobius things (or other things anyway) on finding coprimed i and j and greedy. $$$O(\sqrt{n})$$$ observation was cool, like what I first met on 10 years ago.

F: Brute force and use method here. It has been 7 years?! wow...

Maybe we can say even my grandma could solve it, someday in the future.

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

giv rating

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

hmmm，unrated？

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

Can anyone post the top-100 Indian participants list.

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

in C ,can someone find out why does my O(n^3/2) doesn't work submission 187026045

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

I've understood the editorial for problem C. Can anyone explain why o(n) is enough to find subarray XOR i mean we didn’t consider like 2-any 3-any....index.

Just considers 1-2, 1---3, 1----n (index) Thanks.

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

how to get that formula in B task?

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

I recently got a message from Codeforces team that my solution 186944749 matches with 186930712 and 186939456 . But I had used the code from the Leetcode(online site) blog which was posted two years back as given comment (link). So MikeMirzayanov please check it once I had not copied any other contestant's code.

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

Hello codeforces! I just noticed that my contest points were reduced to the level before participating in this contest #841 (div.2). Does anyone have any idea why this happend?

→ Reply