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:
sksusha8853, Phantom_Deluxe, Anurag203, nishu2002, hk2102, krishanu21saini and somyamehta_24 made a great contribution to the problemset.
Thanks to ajit, awoo, NemanjaSo2005, Nahian9696, Qg3, CARBINE, TomiokapEace, maomao90, MasterRayuga and prvocislo for testing the problems.
Thanks to adedalic for wonderful coordination and for giving great advice throughout the round.
MikeMirzayanov for Codeforces and Polygon platforms.
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
- yash_daga
- vineeth_kada
- GoatTamer
- Yomapeed
- GooglerPraveen
- orientor
- milind0110
- Chimpanzee
- mayankfrost
- hsrb
We have uploaded the link to the code for generating random numbers and ranklist here.
As a tester, I am first.
Rated ? Unrated ? Also, do we have to register anywhere to be eligible for prizes ?
It's rated of course. And no, you don't have to register, we would contact the prize winners.
To clarify what the previous commenter meant, prizes are only for rated contestants?
No, the prizes are for all the Indians, irrespective of the rating.
Thanks to the authors for this amazing div 3 round!
:sadge:
Am i indian or not ? How will you find out?
based on whether you will cheat or not
Ofc you'd have to keep your nationality as Indian for that. We will be asking you for details like mobile number and address.
My first contest
All the Best
As a tester, problems are quite nice and I feel like you can learn from this round, especially if you are newer to CP.
Why are gifts only for Indians ):
Because its kinda impossible for us to deliver them overseas keeping in mind the cost and tediousness of that.
But u can consider bangladesh. Cause we r neighbour :'(
Bhai, then Pakistan will also ask ;)
Why only 9 testers? Also why only 5 div2 testers?
As a debut tester, I am confident you will enjoy the problems.
Orz
Orz.
Orz Qg3
Le Indians:
Indian participants: Great! I am bound to get it!
T-shirt! :)
Finally, my first unrated div 2. Yaaaaaaaay!
I waited a whole year to become LGM :)
not really*
No way. I'm LGM.
can't be your first unrated then*
Why can't О_о? Anything can happen in the new year :)
Because the rating is still calculated according to the real rating, and the New Year's magic just changes color.
How boring are you :(
also in a realistic approach you can't skyrocket from CM to IGM in one round*
You too, don't spoil the magic of the new year
hahaha lol :)
Good luck to all participants.
great initiative from IIT Indore. I appreciate that :)
Hope to not find any problems related to binary strings, had enough of them in the past contests
Also that shit games of 2^n rounds
lmao
Also no constructive algorithms!
All the best everyone
Good luck!
Just checking my rank
I need pants!
Well,so good,this is my first round on CodeForces.
I am looking forward to the problems of this contest, hoping to surprise me.
just curious what happened with codechef?
Finally contest after long time..
best of luck everyone going to participate after a long time
Thank you Messi
messi? seriously i thought i look like johny with hairs
I think you look like walter junior ( the son of walter white )
Hope to have a great round!!!!
glhf!
Hope i will get a +ve delta, multiplied by 2022 too.
madarchod b problem first telling take modulo after and ans comes after taking modulo #badproblemsetting #reporttostter
I face a lot of difficulty in solving in c++ than I coded in python
There is no restriction on the size of integer in python right?
Trash Indian round, no even one interesting problem on the problemlist.
Even though you have solved max of the problems!!!! Indian rounds are quite good but this one was little bad
Totally a trash round. This was not expected from my people
Indeed
C is very frustrating
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 !!
The same thing happened to me, but I solved it with modular inverse
i used int128 then took the mod
D < C
Time limit too strict for C
Thanks for the contest! Even though problem B is a little bit too cringe in my opinion, problems D and E are really interesting!
idk about E, but there is nothing interesting about D.
E is pure math. I like math!
Print your final answer * (seconds passed since 1 JAN 1970). Why multiplied by this ? Because we are never gonna see this number again!
I envy those who did not participate in this trash round.
Did you create a new account just to hate this round? really? xd
C and D are the worst problems ever existed. Eager to give up cp after doing those
No, it's not. You just don't know how to solve it.
Disagree. C was to count all squares using pref-xors. D was binary search with RMQ or 2d two pointers. I just can't get why C is TL'ed (i thought my sol is O(n^(3/2)), but for some reason it isn't), and D was just frustrating to write
RMQ or 2d two pointers? Nope. I used histogram 2d with stacks. An interesting idea I learned years ago.
Well, you do you. idk what is histogram. I will learn it, as you are so passionate about it
Please! Try to solve this problem: https://cses.fi/problemset/task/1147
Also D can be solved using binary search and 2d prefix sum.
D can be solved with matrix window minimum. ref : https://stackoverflow.com/questions/10732841/sliding-window-minimum-maximum-in-2d
That's what i mean by "2d two pointers", ig
My solution O(count_of_squares_up_to_(1<<18)=450 * n) for C TLE'd in java :( What was the intended complexity?
How to solve D ? -_-
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))$$$
What's the solution for F?
anyone how to solve B . i got TLE .
simple math formula. https://oeis.org/search?q=1%2C7%2C22%2C50%2C95%2C161%2C&language=english&go=Search
Can someone explain to me why my code gives WA for n = 1000000000 for problem B? :( 186932175
Any hints for D please?
Binary search
I got the intuition of the binary search thing but how do I do the verification on the grid? More specific hint please
to check if we can have a submatrix of size k, you can just convert the matrix into binary matrix by changing all value greater than k to 1 otherwise 0. Now you can find largest square with all 1s (https://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/) and if this is greater than k we can have a submatrix of size k with all elements greater than equal to k otherwise no.
you can binary search after finding matrix window minimums.
ref : https://stackoverflow.com/questions/10732841/sliding-window-minimum-maximum-in-2d
histogram
Binary search for answer + 2D prefix-sum
can u explain idea for 2d prefix sum for it
Well, I have binary searched level mid. Tab — original table, new_tab[i][j] = 0 if tab[i][j] < mid, else — 1. Then I make 2D prefix sum table for new_tab and iterate over cells looking if sum on square with length mid starting in current cell is n * n or not. If there is at least 1 square with sum n * n then we make l = mid, else r = mid.186936561
Was 'D' a 2D segment tree problem??
No,just 2D sum.
binary search answer + O(n) check for fixed l
(n is the number of cells)
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?
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 ??
Binary search + histogram to find max square removing all numbers <= x (binary search for the answer)
Ah! Leetcode largest histogram. My leetcoding has gotten rusty these days,
or CSES. It's an interesting well known idea everyone should know.
Binary search with 2D prefix sums. I’m pretty sure that this exact problem appeared before multiple times.
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.
why is n*1.5 solution for C giving TLE
Don't use unordered_map
Even map is giving TLE. I think we have to use array instead
If you use map then the time complexity would be O((n^1.5)*log(n)). As the time limit was strict, this was too giving tle. Use a global array instead to remove that log factor.
is D a graph problem? How to solve** D**
D is a binary search problem
By using monotonous queue and binary search.
monotonous queue will help you to find the minimum value of all possible sub-matrices.
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].
How to solve E? Any hint please?
Divide by the gcd and see what happens
Think about Euler's totient function
For the first time, I am regretting using C++ in CP contests.
.
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?
Yes I have also considered greedy but I cannot prove or disprove 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.
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"
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.......
i tried using fixed size array also. But it was giving tle.
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).
Thanks for the help dude.. Will try this :) Happy New Year
Happy new year to you as well!
FK that's 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.
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
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
Good bye 2022!
How to do E? I can't think of anything other than Euler.
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).
Thanks very much. You inspired me.
whats the idea for c?
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)$$$).
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
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
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)))
legend
E was a very good problem.
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
I think Problem D is a straightforward 2D segment Tree. ??
Problem C was decent from the point of logic and everything, but worst setting of this problem ever, too tight limits.
Why did you use
mapinstead of array? The value ofXORis just $$$10^6$$$ at maximum.In retrospect, I regret using map.... Had several TLE :(
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
they wanted to prevent nsqrtn logn, and fyi hashmap is O(n) worst case
check out https://mirror.codeforces.com/blog/entry/62393
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.
You only need to search the perfect square numbers because only perfect square numbers have odd number of
divisors.
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.
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.
Think about when a number has an even number of divisors and which numbers are those. Could there be some reason for that?
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
Can anyone tell me why this solution didn't pass?
https://mirror.codeforces.com/contest/1731/submission/186950096 MikeMirzayanov
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.
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.
anyway to do it w/o interpolation :(
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...
search for division modulo a prime
Already tried it during the contest, got WA. What did I do wrong? (code).
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
But in line $$$31$$$ I am making sure $$$rj$$$ won't become negative?
rj could have been negative before line 31, so you need to do while(rj < n)
How? $$$rj$$$ is at least $$$0$$$.
First of all, n^3 itself goes out of long long limit, so anyway you would get wrong answer.
Yes, but the function
powercomputes $$$n^3$$$ mod $$$10^9+7$$$ so it won't overflow.But, then what if power(n, 3) > INT64_MAX / 4
$$$power(n,3)$$$ is at most $$$10^9+6$$$ which is less then INT64_MAX $$$:4$$$ since INT64_MAX $$$:4$$$ is 2.305843009213694e+18.
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)
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.
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).
__uint128_t (it worked for me)
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.
i did the same.. but in 1000000000 ans is incorrect.
I had a slight typo in the formula I typed above. Maybe now it helps fix your issue? Here's my submission: 186895976
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.
Fuck me
bruh legit the foresight
Problem B is exactly the same as BAMO 2017/3
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.
Better Luck next year!! :-)
Valiant >>> valorant
On problem E:
Only need to search for it and find this comment on CF:
https://mirror.codeforces.com/blog/entry/55822?#comment-591656
ps. I had runtime error on test 1 several times because of Divide By Zero. 186946890
can someone tell me what's wrong in this. i am just literally doing whats told and taking modulo in the end
I think you should multiply by 2022 in the process，cause 2022/3 is not a float
Use integer division (//)
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
medges, it should be possible by this greedy approach. Can anyone provide any formal proof for this why addingmedges will always be possible by this greedy (Ofcourse for the case when it's possible at all)?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 $$$ \lt i$$$, therefore it will be possibile to use smaller blocks.
That's incorrect.
Let's say if you have three
numbers to be taken2 2 3and target sum is4. 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.
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$$$.
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.
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.
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]
Are you sure about the case $$$n = 6$$$ and $$$m = 6$$$? It should not be possible actually.
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
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!
ModuloForces
ben stokes round bc
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.I multiplied 2022/6 = 337 and 2022/2 = 1011 and it worked. Modulus doesn't go with division
in problem B i have applied 2*(sum of first n square numbers)-sum of first n natural numbers,is this correct?
Yes.
Nice leetcode contest
++ lmao
I got F's sol but electricity cut when implementing it :(
TIL — don't use a map unless you have to
For Problem B,
Can anyone help why this code is giving wrong output for n=1e9
All output matches except for n=1e9
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 toa1 = n*(n+1)*(2*n+1)//6.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?
n*(n+1)*(2*n+1)is always a multiple of 6, but float type has no information about whethern*(n+1)*(2*n+1)/6is 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)/6exceeds the limit.Oh.. Now I see the problem!
Thank you so much for helping me with this shobonvip
My pleasure!
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.
The maximum will be all 1s in the binary representation. So it will be 2^19 — 1;
since $$$2^{18} \gt 2 \cdot 10^5$$$, the $$$xor$$$ of the numbers can't be that large.
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.
You never got runtime error when your frequency array was of size $$$3 \cdot 10^5$$$.
My N sqrt(N) solution is not passing can you tell me intended time complexity please?
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.
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.
Chandler trying to give money to Joey
Do we have to fill some form to be considered for t shirts?
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:
I literally looked up class 11th ncert maths book online mid contest to get the answer of those two sequences in problem B xD
OHHHHHH
I could have solved E but I missed a overflow when doing int32 multiplication......
QwQ
The importance of using int64 in CP
Had trouble with taking mod in B so i used BigInt instead lol
I reach 2023 problem solving before 2023 year :) Hahaha SHAHEEN
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?
Raising problems without input scale limit makes nonsense.
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
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.
This might actually be a decent div 3 with a couple easier problems more at A and B.
$$$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.
Task B is actually a task from Codeforces Round 672. It can be solved easily without trie.
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.
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.
giv rating
hmmm，unrated？
Can anyone post the top-100 Indian participants list.
in C ,can someone find out why does my O(n^3/2) doesn't work submission 187026045
try to use array instead of map
yeah it worked but i dont't know why, how is a array faster than a map
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.
Just chill bro, it's New Year＼(^o^)／
how to get that formula in B task?
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.
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?
Maybe removing cheaters