As a specialist tester, i specialist tested.

This may be a way of speaking for the question group. They may be saying this in another way to wish us a better ranking!

as a newbie, i wish i will become like you

As an average setter, I average setted.

As a non tester, I didn't test.

As a specialist competitor, I'll compete specially.

Get a life?

We were asked by the Codeforces admins to shorten the author list.

Practice, hard work, and dedication.

" keep one or two edges cases so contest could be fun with hacks "

Its not fun for the guy who gets hacked.

We've started working on the round over half a year ago and we most likely won't be making radical changes one day before the start of the round.

I hope you enjoy the round regardless :thumbsup:

Do you really think that you are giving something new for community with this comment? You are just saying obvious things.

All the best to heard-mentality-crew... have positive delta... xD

Get your prioties straight. This contest doesnt clash with leetcode biweekly, leetcode biweekly clashes with this.

Thy wish has come true

LeetCode is not real CP

It's not the longest, there were several contests that lasted 3 hours.

TBD = to be determined

Vuw

sus

You can only participate in div 1

isn't div. 2 open for CM? It's neither a combined round

Don't know why, but I never care about scoring distribution O.o

fighting!!!

the real question is,,, Who let the dogs out...

who.... who... who.... who.... !!!

Yes

Finally BCCI postponed IPL

CF>> IPL, even god postponed the IPL Final to today so that we can enjoy both!

why are you sad when your comparison has 4 >

Lol it rained

why are you asking me

WTF 1053 problems solved for the last month?

just don't use hashmap lol

I spent around 1 hour switching between unordered map, gp_hash_table and cc_hash_table and trying various optimizations to remove TLE and MLE :/.

In the last 5 mins, I replaced it with a binary search on a vector containing deduplicated pairs, and their count and got pretests passed, though I still expect TLE during systests.

Sometimes it is faster to just use regular (tree) map and check whether the element exists in the map before accessing (avoids unnecessary insertions). Not sure if this was intended though.

Is it still possible to increase the time limit and rejudge submissions at this point? I'm another affected participant who tried messing with unordered_map and stuff which didn't work, while some solutions that just used binary search instead of map (207592515, for example), which should have the exact same complexity, passed.

Try a stronger hash function

lowerbound in vector works faster than hashmap in this kind of problems, from my experience

207591419

Not sure if it will pass system tests: https://mirror.codeforces.com/contest/1831/submission/207626584

I am not sure about B constraints, I wrote the first thing which came to my mind and it passed in 2.1s. It's not optimal, surely it can be easily optimized to 1.5s and probably to <1s with some effort. But tbh I am not completely sure it will pass systests, I did not prove complexity. Upd: passed systests in 2.1s

Regarding C, I did not solve it but I think one of the important insights is that any 2 intersecting (but not nested) segments [A;B] and [C;D] can be replaced with 3 non-intersecting segments [A;C) [C;B] and (B;D]. Then we can somehow remove all intersecting segments and solve a much easier subtask where segments can be only nested (build a tree from them).

Yea I'm kinda bummed out because for d2D/d1B I had a java solution early on that got TLE, and I tried a lot of things but just couldn't get it under the TL. Then I converted the same code into c++ (which I barely know) and it passed, but by then I already wasted 1+ hours.

Great explanation for C. Finally got it.

idk

you need to use the fact that the values of a[i] and b[i] are less than "N".

So, for each pair (a[i],b[i]), we have to traverse till sqrt(N) at max, and see if the reverse pair exists or not.

first of all, shard the pairs(a[i],b[i]) based on the first value (a[i]). Also sort each shard for applying faster search operation using binary_search.

We also need to keep track that how many times particular pair has been encountered in past, to do so we need a map < pair <int, int > , int > where map[(x,y)] denotes, how many times particular pair (x,y) has been encountered yet.

for(int i = 0 ; i < n ; i++) {
   shard[a[i]].push_back(b[i])
}
for(int i = 1 ; i <= n ; i++) { // sort each shards
   sort(shard[i].begin(),shard[i].end())
}
// suppose shard pairs are (1,2),(1,3),(2,3),(2,1),(4,8),(4,12),(4,4)
// shard[1] = { 2 , 3 }
// shard[2] = { 1 , 3 }
// shard[3] = { empty , because no pair has a[i] == 3 }
// shard [4] = { 4 , 8 , 12 }
// Hope part 1 is clear...

Core logic part is here now, suppose (a[i] , b[i]) and (a[j] , b[j]) are expected pair, then we will a[i] * a[j] - b[i] = b[j] , for better understanding I will use (x,y) and (p,q) instead of (a[i],b[i]) and (a[j],b[j]) from now on. so, (x*p — y == q) must hold in order to count the pairs.

if shard[x] has value 'y' in it, that means, we have a pair (x , y) somewhere. Now, any pair (x , y) and (p, q) to be in the answer, we must make sure that x * p <= 2*n, otherwise answer is never possible ( because of the restriction that 1 <= y <= n && 1 <= q <= n,,, their sum will be 2 <= y + q <= 2*n. ) , that's why x * p must be less than 2 * n ;

So, now using above facts, please go through code,

for(int i = 1 ; i <= n ; i++) {
    for(int j = 0 ; j < shard[i].size(); j++) {
        int x = i;
        int y = shard[i][j];
        // now assume that p is 1,2,3... until p * x <= 2 * n;
        for(int k = 1 ; k <= n ; k++) {
            if( x * p > 2 * n ) break; // here answer is never possible, 

            // Now, try to find in shard[k], whether the value x*p - y is available or not
            // to do so, we can use binary_search, or set, or lower_bound() or anything
            auto it = lower_bound(shard[k].begin(),shard[k].end(),x*p-y);
            if(it != shard[k].end() && *it == x*p-y) { // Condition to see if the x*p-y is present or not
                 // if the current value is present, then we have to add it number of times it has been encountered till now, 
                 ans += map[(x,y)]
            }
         }
         // once we have processed a pair (x,y), 
         // we also have to add it to our map of encountered pairs 
            map[(x,y)]++;
      }
   }
   // finally return ans, dont forget to initialise it with 0 by the time declaring it. :) . 
}
           
Final complexity is O (N log N) + O(N * sqrt(N) * log N) in my case of implementation. With unordered maps and more further optimisations u could reduce log N factor to O(1) in the second part. but that's unnecessary to get AC.

$$$b_i\le n$$$, so you only need to maintain a bucket with size $$$n$$$

Every time you search in a map / unordered_map, if value you are searching for is not present, it always creates new element for it. So it is $$$O(n\sqrt{n})$$$ memory if you use them.

I see, maybe it needs to be some online version of it?

what's the new idea ?

Link

My approach was to split everything into buckets by A. Then we need to iterate through small buckets (A <= sqrt(MAX*2)) in an outer loop because otherwise, a*a will be too large and iterate through all buckets in an inner loop.

At each iteration, calculate the answer for pair of buckets. To do it efficiently, sort elements in buckets, and use the smaller (by the number of elements) bucket as a needle and the larger as a haystack, do a binary search to find the number of matching elements.

Also, we need to match every A <= sqrt(MAX*2) bucket with itself but it is fast so can be done in a variety of ways.

I think my submission 207627709 is pretty clear but I am not sure if it was the supposed solution. Passed in 2.1s, probably could be optimized to 1s.

Congrats! What extension do you use?

congrats