Codeforces Round #886 (Div. 4) Editorial

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

#	User	Contrib.
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Thank you for participating!

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
    int a, b, c;
    cin >> a >> b >> c;
    cout << (a+b+c-min({a,b,c}) >= 10 ? "YES\n" : "NO\n");
    
}
 
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
}

1850B - Ten Words of Wisdom

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
void solve() {
	int n;
	cin >> n;
	int winner = -1, best_score = 0;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		if (b > best_score && a <= 10) {winner = i; best_score = b;}
	}
	cout << winner << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1850C - Word on the Paper

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
void solve() {
	for (int r = 0; r < 8; r++) {
		for (int c = 0; c < 8; c++) {
			char x;
			cin >> x;
			if (x != '.') {cout << x;}
		}
	}	
	cout << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1850D - Balanced Round

Idea: SlavicG

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
void solve() {
    int n, k; cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i];    
    sort(all(a));
    int cnt = 1, ans = 1;
    for(int i = 1; i < n; ++i) {
        if(a[i] - a[i - 1] > k) {
            cnt = 1;
        } else {
            ++cnt;
        }
        ans = max(ans, cnt);
    }
    cout << n - ans << '\n';
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

1850E - Cardboard for Pictures

Idea: flamestorm

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
#define int long long
 
void solve() {
    int n, c; cin >> n >> c;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    int l = 1, r = 1e9;
    while(l <= r) {
        int mid = l + (r - l) / 2;
        int sumall = 0;
        for(int i = 0; i < n; ++i) {
            sumall += (a[i] + 2 * mid) * (a[i] + 2 * mid);
            if(sumall > c) break;
        }
        if(sumall == c) {
            cout << mid << "\n";
            return;
        }
        if(sumall > c) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

1850F - We Were Both Children

Idea: mesanu & SlavicG

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
void solve() {
    int n; cin >> n;
    vector<ll> cnt(n + 1, 0), mx(n + 1, 0);
    for(int i = 0; i < n; ++i) {
        int x; cin >> x;
        if(x <= n) ++cnt[x];
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = i; j <= n; j += i) mx[j] += cnt[i];
    }
    cout << *max_element(all(mx)) << "\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

1850G - The Morning Star

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define int long long
 
void solve()
{
    int n;
    cin >> n;
    map<int, int> up, side, diag1, diag2;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        up[x]++;
        side[y]++;
        diag1[x-y]++;
        diag2[x+y]++;
    }
    for(auto x : up)
    {
        ans+=x.second*(x.second-1);
    }
    for(auto x : side)
    {
        ans+=x.second*(x.second-1);
    }
    for(auto x : diag1)
    {
        ans+=x.second*(x.second-1);
    }for(auto x : diag2)
    {
        ans+=x.second*(x.second-1);
    }
    cout << ans << endl;
}
 
int32_t main(){
    startt
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

1850H - The Third Letter

Idea: SlavicG

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
#define int long long
const int N = 2e5 + 5;
vector<pair<int, int>> adj[N];
int val[N], vis[N];
void dfs(int u) {
    vis[u] = 1;
    for(auto x: adj[u]) {
        int v = x.first, w = x.second;
        if(!vis[v]) {
            val[v] = val[u] + w;
            dfs(v);
        }
    }
}
void solve() {
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; ++i) {
        adj[i].clear();
        vis[i] = 0, val[i] = 0;
    }
    vector<array<int, 3>> c;
    for(int i = 1; i <= m; ++i) {
        int a, b, d; cin >> a >> b >> d;
        adj[a].pb({b, d});
        adj[b].pb({a, -d}); 
        c.pb({a, b, d});  
    }
    for(int i = 1; i <= n; ++i) {
        if(!vis[i]) dfs(i);
    }
    for(int i = 1; i <= m; ++i) {
        int a = c[i - 1][0], b = c[i - 1][1], d = c[i - 1][2];
        if(val[a] + d != val[b]) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

Comments (87)

Show archived | Write comment?

ScarletS

3 years ago, hide # |

+30

It feels like Problem A was directed at someone 😶

→ Reply

SlavicG

3 years ago, hide # ^ |

← Rev. 2 →

+14

It is easy to write verses

When you have not what to tell,

Stinging words and hollow phrases

In a gangling doggerel.

dub-otrezkov

Thanks to authors! The problemset was very cool

MisterGir

This competition is the best for me.

Bosscoder

For E wasn't it worth mentioning O(1) solution with quadratic formula if we ignore time for taking input

https://mirror.codeforces.com/contest/1850/submission/214907399 or https://mirror.codeforces.com/contest/1850/submission/214911845

beaaaan

sqrt is log(n), so in fact there are no O(1) solutions

FritzGeiger

heh) I saw the problem and immediately thought about binary search and solving the equation. I decided to choose the second one and as a result I first wrote the code for pluses, and then for python (I never used int128)

OiNishant

Hey, How come you have reached to this solution? Can you please explain about your quadratic formula approach

pedrosorio

← Rev. 4 →

A painting with side s_i requires a cardboard square with side (s_i + 2*w).

The total area of the cardboard squares (the c input in the problem) is:

sum (s_i + 2*w)^2 = c <=>

sum (s_i^2 + 4*s_i*w + 4*w^2) = c <=>

sum(s_i^2) - c + 4*sum(s_i)*w + 4*w^2*n = 0

The last equation is quadratic in terms of w and we can solve it using the quadratic formula

EDIT: Thanks for the correction solvyce

solvyce

I guess there should be a bit of correction in the last line:

sum(s_i^2) - c + 4*sum(s_i)*w + 4*w^2*n = 0

Here, n = number of pictures. If you see this for 1st test case, 3 and 50 and {3,2,1}, so sum(s_i^2) = 14, c = 50, sum(s_i) = 6, and n = 3. If you put w = 1, it satisfies only if you consider n also, that is,

LHS: 14-50+4*6*w+4*w^2*3 => 14-50+24*(1)+12(1)^2=>-36+36=>0 = RHS

Yeah, absolutely. That should have read sum(4*w^2) which is just equal to 4*w^2*n as you point out, since it does not depend on the summation index.

iordache_

That’s what i did, had problems with the output for large numbers tho, but it’s O(n), not O(1), instead of O(nlogn)

i_ujjwal

For anyone using JAVA , never ever use Arrays.sort even after shuffling the array, I got unnecessary TLE and rectified using Collections.sort. The tests were designed carefully.

rainbowtable

thanks

SpongeCodes

What is a failed test case for this solution for D?

214942704

Baraa-Ahmed

I make the same code and i do not know where is the wrong

Kacchi

Editorial published during open hacking phase?!

aayush_chhabra

G Problem is kind of impossible with python

vgtcross

Even if we forget the fact that there are workarounds to the hash hack in python, we can still solve the problem using python quite easily.

Instead of using maps/dictionaries, we can just store all values of $$$x$$$, $$$y$$$, $$$x + y$$$ and $$$x - y$$$ in four separate arrays, sort each of them and check the number of equal elements that way. And as far as I know, there is no hack for sorting in python (unlike in java).

Code (pls forgive me for horrible python): 214952260

thanks got it now sorting also a good option

AbdulRahmanLuai

i got hacked on G (tle) because for some reason i thought i had to sort the points in order to get the intersection with y = x+c and y = -x + c lines.

It turns out this is unnecessary and you can solve the question with linear time O(N).

HACKED submission O(Nlog(N))

O(N) submission

evmenoff

Bro, it's TL unfortunately

pgiaminh8368

+12

https://mirror.codeforces.com/contest/1850/submission/214868771 This code look sus. Is it allowed?

That is (quite obivously) code obfuscation, which is not allowed. Hopefully they'll get skipped for breaking rules.

bubu_lukar

what does code obfuscation mean?

If only there was some magical place where you could just type the words "what does obfuscation mean" and you'd get an answer instantly...

sh1erkeh

But how many defines is code obfuscation then? Some c++ solutions are absolutely unreadable even though their authors had no intention to muddle their code.

I don't think there are any specific numbers I can give; I think the more important part is intention:

If the author didn't intend to make the code unreadable (and they can read it themselves), I wouldn't call it obfuscation.

If the author deliberately made the code unreadable (possibly using automated help), I would definitely call it obfuscation.

I think it should be clear that the aforementioned code falls under the second case.

Sacharlemagne

Unfortunately I saw a lot of solutions with defines like this that make the code unreadable. But I don't really know what to do with that as I haven't found any flag/signal. button yet.

transfermarket

Please ban him MikeMirzayanov

MikeMirzayanov

+16

Of course, this is an obvious violation of the rules, and the user will be punished.

SofTarg8

Hello! This is my first contest and I submitted the problem A. I was registered but I do not see an increase in my rating, can someone tell me when will I get them?

check again tommorrow afternoon (indian time)

can someone try to hack my solutions?

halfway_there1

I used binary search for problem-E but it has some error which I am unable to figure out. Can anyone please help me find error in my binary search logic for my submission 214950555. ? edit : when i set r = 1e10 the sample test-cases passed but on submission it fails again on some test case.

it looks like the res function might overflow, I had that problem and dealt with it as explained in the editorial. you can also use __int128 instead of long long to avoid overflow.

Bouttouwa

try r=sqrt(c) , it's the smallest value of r that can be valid

true, an alternative is also to use r=1e9+1.

FlyingElephant

Why this solution TLE in problem F because It does unnecessary work when we have more occurrences of one elment. I think the TC Is exactly the same as the one proposed by the editorial in the end. Also if we have the test case 1,2,3....,2e5. The solution posted does the same number of operations as the one of the editorial. Am I wrong thinking that this has the same TC as editorial?

Petertromso

If all n values of ai are equal to 2, each one will need n/2 iterations, in total n*n/2 operations.

Therefore it is necessary to treat together the array values that are equal.

awakeljw

maybe f can be hacked, consider case {1,1,1...} * 10^5

StrangePenguin

+10

We keep in cnt_i how many frogs we have for each hop distance.

this prevents it.

dsquare

I liked problem H . Before reading editorial, i didn't though it will turn that easy.

tenick

can someone explain why my E solution is accepted here:
https://mirror.codeforces.com/contest/1850/submission/214991383

but it is failing here:
https://mirror.codeforces.com/contest/1850/submission/214991353

the only difference is in my accepted version, i did (sizes[i] + w * 2) * (sizes[i] + w * 2)
but in the failing version, i did pow((sizes[i] + w * 2), 2)

leneza_41

Check this blog: https://mirror.codeforces.com/blog/entry/21844

stdfloat

In this contest can my E be WA, G be TL?

My submission in E in contest: 214829184. I don't know how it's passed pretests. In code wrongly I did: x = s[i] + 2 * md + 1 and printed l but x should be s[i] + 2 * md and printed l — 1. Like this code: 214997775 which I submitted after contest. Please let me know if it's hackable.

My submission in G in contest: 214869824. Can it be TL or ML? It passed pretests with 1668 ms 76900 KB(Time limit is 2s). After contest I optimized it (removed set) and passed pretests with 904 ms 39300 KB(214997753). Please let me know it's hackable.

shufentainanle

During the contest,I misunderstand Problem F,I think each second we can place a trap,so in this case,can we also calculate the maximum number of the frogs we can catch?I need help,thanks.

the_coder_8297

Can anyone help me my code has resulted in TLE in system testing?, it is having similar complexity as of author O(nlogn)

Code

#include <bits/stdc++.h>
using namespace std;

#define ull unsigned long long
#define int long long
#define vi vector<int>
#define vb vector<bool>
#define vvi vector<vector<int>>
#define vvvi vector<vector<vector<int>>>
#define pi pair<int,int>

const int mod = 1e9+7;

void helper(int n,int &maxi, unordered_map<int,int> &mp){
    int cnt = 0;
    for (int i=1; i*i<=n; i++)
    {
        if (n%i == 0)
        {
            // If divisors are equal, print only one
            if (n/i == i)
                cnt += mp[i];
  
            else {
                cnt += mp[i];
                cnt += mp[n/i];
            }
        }
    }
    maxi = max(maxi,cnt);
}

void solve(){
    int n,x;
    cin>>n;
    int maxi = 0;
    unordered_map<int,int> mp;

    for(int i = 0; i < n ; i++){
        cin>>x;
        mp[x]++;
    }

    for(int i = n ; i >= 1 ; i--){
        helper(i,maxi,mp);
    }
    cout<<maxi<<"\n";
}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t = 1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

people_plus_plus

Your code is $$$O(n^2)$$$ because of unordered_map

zatch07

The solution of F was already available on geeks for geeks and other various websites , seems to be a quite popular problem

UzuHa_NaruSuke

I used an unordered map on F. I will never use an unordered map again.

Vishwesh_8451

Why does that give TLE if unordered_map is used instead of the normal map in C++? Can anyone tell me when to use unordered_map and normal map?

https://mirror.codeforces.com/blog/entry/62393

thuonguyenvan

← Rev. 3 →

Can anyone explaine how Wrapper function works? This is my hacked submission: https://mirror.codeforces.com/contest/1850/submission/214906792 And then i fixed it by Wrapper function which make my submisson accept https://mirror.codeforces.com/contest/1850/submission/214984466 *sorry for bad english

mr_kamran

can someone tell why Question 'G' Fails for an Unordered map, but runs absolutely fine for ordered map

void mr_kamran(){

ll n; cin>>n; ll ans = 0; unordered_map<ll,ll>m1,m2,m3,m4; for(int i = 0;i<n;++i) { ll x,y; cin>>x>>y; m1[x]++; m2[y]++; m3[y-x]++; m4[y+x]++; } for(auto it : m1) { ans+=(it.second*(it.second-1)); } for(auto it : m2) { ans+=(it.second*(it.second-1)); } for(auto it : m3) { ans+=(it.second*(it.second-1));
} for(auto it : m4) { ans+=(it.second*(it.second-1)); } cout<<ans<<an;

}

dhruv1807

Check the editorial, this question has been answered a million times here.

rishigodre14

there might be some internal collisions due to the internal implimentation of unordered maps

yashesh_07

Solved problem H using Union Find.

215052919

xtronix_90

Your code here...

#include <bits/stdc++.h>
using namespace std;

#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#endif

#define pb push_back
#define mp make_pair
#define FAST                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define ll long long
#define ld long double
ll s(ll md, vector<ll> &v)
{
    ll ans = 0;
    for (ll i = 0; i < v.size(); i++)
    {
        ans += ((v[i] + 2 * md) * (v[i] + 2 * md));
    }
    return ans;
}

void solve()
{
    ll n, c;
    cin >> n >> c;
    vector<ll> v(n, 0);
    for (ll i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    ll i = 1, j = (ll)1e9;
    while (i <= j)
    {
        ll md = i + (j - i) / 2;
        ll tmp = s(md, v);
        if (tmp == c)
        {
            cout << md << endl;
            return;
        }
        else if (tmp > c)
        {
            j = md - 1;
        }
        else
        {
            i = md + 1;
        }
    }
    cout << 1 << endl;
}

int main()
{
    FAST
        ll t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Can someone Explain Why my code gives WA? For Some Test Cases it the While Loop Breaks and prints 1 which I used for Checking.

in your predicate function (s) 'ans' variable is overflowing.

to combat this return ans as soon as it becomes larger than c

ll s(ll md, vector &v) { ll ans = 0; for (ll i = 0; i < v.size(); i++) { ans += ((v[i] + 2 * md) * (v[i] + 2 * md)); if(ans>c) return ans; } return ans; }

Thanks, It worked!!

How did you spot it?

like md is 1e9 now you square it becomes 1e18

now you are adding it a maximum of 1e5 times

so 1e18 X 1e5 will give you 1e23 — overflow

ChenDX

why F is nlog(n)? if there are 2e5 1 than is n*n

hash the count of each number

so even is there are 1e5 1s the answer will run in n

I don't think they say that in this problem .Is there a hint here? It is guaranteed that the sum of n over all test cases does not exceed 2⋅105

i did not get your point sorry lol

the problem f isn't say hash the count of each number.

you just have(can ig) to do it in order to solve it lol

sorry ig our views differ due to our solutions

0mar

It looks like n*n but it's not. the time complexity is n+n/2+n/3+n/4+n/5 +... We can factor out n and it becomes n(1+1/2+1/3+1/4 + .... + 1/n) which you should be familiar with if you have taken calculus. It's called the harmonic series. If you aren't familiar with calculus, all you need to know is that 1+1/2+1/3+1/4 + ... + 1/n is approximately equal to log(n) where n is the number of terms

piyushjain1603

why in problem G it gives TLE error if we use unordered_map<int,int> instead of map<int,int>. The time complexity of unordered_map is O(1) whereas operations on map take O(log n) time.

Hamloo

https://mirror.codeforces.com/blog/entry/50626?#comment-345515

xiuyuan-cao

Thank you for the link! Got the same problem today.

ALexAnDm

Hey guys! Can somebody help me please why in task E — Cardboard for Pictures we should use mid = l + (r — l) / 2? I am new at this and would appreciate any answer)

vitosevski

It's same as mid=(l+r)/2 but it's recommended to use mid=l+(r—l)/2 to avoid overflow.

Roronoa__Zoro

SlavicG Can you explain why u also pushed negative edges in the last problem

Arnur2937

Can we solve H using different approach?: For all loops found in graph, I check if "cnt" of the loop is equal to 0. "cnt" of the loop is sum of all (-d)s for all adjacent vertexes in the loop. For example, if we have loop

(a, b, d)

1 2 1

2 3 2

3 1 -3

cnt of this loop is 0. (-1-2-(-3) = 0). If cnt of the loop is not zero, it means that every soldier in the loop belongs to 2 different camps. My code gives WA3: 216588864

tanujvats

can we do F by checking for cycle ?

nonrice

Comment on G implementation

If you want to calculate $$$n(n-1)$$$, you can instead calculate $$$2(1+2+...+(n-1))$$$.

By using this, you can avoid the second calculation pass and have a cleaner solution (https://mirror.codeforces.com/contest/1850/submission/221488328)

213976

can anybody please tell me a counter test case for F problem according to my code? please

map < ll, ll > mp;
 
void solve()
{
    mp.clear();
    ll n; cin >> n; 
 
    vector < ll > a;
 
    for(ll i = 1; i <= n; i++)
    {
        ll x; cin >> x;
        if(x <= n)
        {
            a.push_back(x); mp[x]++;
        }
    }
    ll mx = 0;
    for(auto i : mp)
    {
        ll ache = i.F;
 
        ll pos = 0;
 
 
        for(ll i = 2; i * i <= ache; i++)
        {
            if(ache % i == 0)
            {
                ll x1 = i, x2 = (ache / i);
 
                if(x1 == x2)
                {
                    if(mp.count(x1))
                    {
                        pos += mp[x1];
                    }
 
                
                }
                else if(x1 != x2)
                {
                    if(mp.count(x1))
                    {
                        pos += mp[x1];
                    }
 
                    if(mp.count(x2))
                    {
                        pos += mp[x2];
                    }
                }
            }
        }
        pos += mp[ache];
        
 
        if(ache != 1 and mp.count(1)) pos += mp[1];
 
       // cout << " val = " << ache << " pos = " << pos << nn;
 
        
        mx = max(mx, pos);
 
 
    }
    cout << mx << nn; return;
 
 
   
 
 
 
    return;
}

heWhoCooks

19 months ago, hide # ^ |

Your code is overcounting, say for 4 you have contributions from 1,2,4 as multiples but 2 has contributions from 2 as well as from 1. So, eventually your answer for 4 counts the contributions from 1 twice. To avoid this you can start from n and go till 1 and do the same process, it would pass then

cgy2022

2 years ago, hide # |

I wonder why the G question times out with unordered_map

mahir1

2 years ago, hide # ^ |

Here you go

Thank you! I get it.

Maryan_Shyika

14 months ago, hide # |

Why when I didn't add the edge b[i] to a[i] with weight −di, it gave the wrong answer, but when I did, it was Accepted? My solution https://mirror.codeforces.com/contest/1850/submission/304616401

Muhammed.Elgenead.Hago

4 months ago, hide # |

This is come text. In G I write this code: This is some text. ~~~~~ // this is code from collections import defaultdict for _ in range(int(input())): n = int(input()) coor = [[] for i in range(n)] for i in range(n): coor[i]=(list(map(int,input().split()))) counter = [dict() for i in range(4)] ans = 0 for x,y in coor: t=counter[0][x]= counter[0].get(x,0)+ 1 ans += (t-1)*2 t=counter[1][y]=counter[1].get(y,0) + 1 ans += (t-1)*2 t=counter[2][x+y]=counter[2].get(x+y,0)+1 ans += (t-1)*2 t = counter[3][x-y]=counter[3].get(x-y,0)+ 1 ans += (t-1)*2 print(ans) ~~~~~ It gives me time limit exceeded how can I improve it?

Could someone give me a python solution for G,please?

mesanu's blog