Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

CooloTran's blog

By CooloTran, history, 3 days ago, In English

Sometimes, I read editorial for a problem but it seems unclear and hard to understand or it's from Division 3 and I feel kind of lazy to do it (Link to the problem). Does skipping problems bad? Sometimes I met a Division 3 problem and I really want to skip it but it remains some unsteady knowledge, and when I do it I feel like I've wasted a lot of time for a problem.

Read more »

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

By CooloTran, history, 4 weeks ago, In English

The link to the solution: https://cses.fi/paste/0826caf8d50b8d372b4cf8/

The link to the problem statement: https://cses.fi/problemset/task/2195/

I'm using cp-algorithm template for convex hull but somehow it's still giving a wrong answer.

Read more »

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

By CooloTran, history, 5 weeks ago, In English

Currently, I'm struggling on the trick called "Binary search on segment tree" or "Segment tree walk" but I don't know any documentaries or any sources to learn it.

Read more »

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

By CooloTran, history, 2 months ago, In English

I'm curious about how does your area choose students for the national olympiad of informatics. In my province (Lam Dong — Vietnam), around 20 students participated in the selection round and 8 of them will be able to participate in the national olympiad of informatics (in Viet Nam). There are 4 problems and all of them are very old problems which occured in Codeforces or VNOJ (our country's online judge) which help students who has done it has a huge advantage (Which seems not fair at all to me).

Read more »

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

By CooloTran, history, 2 months ago, In English

Problem: https://codeforces.com/problemset/problem/52/C

Here is the link to my solution for 52C: https://codeforces.com/contest/52/submission/129151622

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define ll long long
#define ull unsigned long long
#define ldb long double
#define db double
#define str string
#define pi pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pi>
#define vpll vector<pll>
#define gcd __gcd
#define lcm __lcm
#define __builtin_popcount __builtin_popcountll
#define __builtin_clz __builtin_clzll
#define __builtin_ctz __builtin_ctzll
#define DB1(x) cerr << "DB1 >>" << (#x) << ": " << (x) << '\n'
#define DB2(x, l, r) cerr << "DB2 >>" << (#x) << ": "; for (int (i) = (l); (i) <= (r); ++(i)) cerr << (x)[(i)] << ' '; cerr << '\n'
#define file "TEST"
mt19937_64 rd(time(0));
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
const ll oo = (ll)1e15;
const int N = (int)2e5 + 5;
const int T = 8e5 + 5;
int n, m;
int a[N];
ll t[T], lazy[T];
void build(int no, int l, int r) {
	int mid = l + (r - l) / 2;
	if (l == r) {
		t[no] = a[l];
		return;
	}
	build(no * 2, l, mid);
	build(no * 2 + 1, mid + 1, r);
	t[no] = min(t[no * 2], t[no * 2 + 1]);
}
void upd(int no, int l, int r, int ql, int qr, int v) {
	int mid = l + (r - l) / 2;
	if (lazy[no] != oo) {
		t[no] += lazy[no];
		if (l != r) {
			if (lazy[no * 2] == oo)
				lazy[no * 2] = 0;
			if (lazy[no * 2 + 1] == oo)
				lazy[no * 2 + 1] = 0;
			lazy[no * 2] += lazy[no], lazy[no * 2 + 1] += lazy[no]; 
		}
		lazy[no] = oo;
	}
	if (l > qr || r < ql)
		return;
	if (ql <= l && r <= qr) {
		// cerr << l << ' ' << r << " : " << t[no] << '\n';
		t[no] += v;
		// cerr << l << ' ' << r << " : " << t[no] << '\n';
		if (l != r) {
			if (lazy[no * 2] == oo)
				lazy[no * 2] = 0;
			if (lazy[no * 2 + 1] == oo)
				lazy[no * 2 + 1] = 0;
			lazy[no * 2] += v, lazy[no * 2 + 1] += v;
		}
		return;
	}
	upd(no * 2, l, mid, ql, qr, v);
	upd(no * 2 + 1, mid + 1, r, ql, qr, v);
	t[no] = min(t[no * 2], t[no * 2 + 1]);
}
ll get(int no, int l, int r, int ql, int qr) {
	int mid = l + (r - l) / 2;
	if (lazy[no] != oo) {
		t[no] += lazy[no];
		if (l != r) {
			if (lazy[no * 2] == oo)
				lazy[no * 2] = 0;
			if (lazy[no * 2 + 1] == oo)
				lazy[no * 2 + 1] = 0;
			lazy[no * 2] += lazy[no], lazy[no * 2 + 1] += lazy[no]; 
		}
		lazy[no] = oo;
	}
	if (r < ql || l > qr)
		return oo;
	if (ql <= l && r <= qr)
		return t[no];
	return min({get(no * 2, l, mid, ql, qr), get(no * 2 + 1, mid + 1, r, ql, qr)});
}
vi stringtoint(str TMP) {
	vi rs;
	rs.pb(0);
	bool ok = 1;
	for (int i = 0; i < TMP.size(); ++i)
		if (TMP[i] == ' ')
			rs.pb(0);
		else if (TMP[i] >= '0' && TMP[i] <= '9') rs.back() = rs.back() * 10 + ((int)TMP[i] - '0');
		else if (TMP[i] == '-')
			ok = 0;
	if (!ok)
		rs.back() *= -1;
	return rs;
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    cin >> n;
    for (int i = 0; i < n; ++i)
    	cin >> a[i];
    for (int i = 1; i < T - 5; ++i)
    	lazy[i] = oo;
    build(1, 0, n - 1);
    cin >> m;
    while (m--) {
    	str TMP;
    	fflush(stdin);
    	getline(cin, TMP);
    	vi VA = stringtoint(TMP);
    	// DB1(TMP);
    	// DB1(VA.size());
    	if (VA.size() == 2) {
    		int L = VA.front(), R = VA.back();
    		int L1 = L, R1 = R, L2 = L, R2 = R;
    		if (R < L)
    			R1 = n - 1, L2 = 0;
    		cout << min({get(1, 0, n - 1, L1, R1), get(1, 0, n - 1, L2, R2)}) << '\n';
    		continue;
    	}
    	// for (auto j : VA)
    	// 	DB1(j);
    	// cerr << '\n';
    	// DB1(VA.back());
		int L = VA[0], R = VA[1];
		int L1 = L, R1 = R, L2 = 0, R2 = n - 1, v1 = VA.back(), v2 = 0;
		if (R < L)
			R1 = n - 1, L2 = 0, R2 = R, v2 = VA.back();	
		upd(1, 0, n - 1, L1, R1, v1);
		upd(1, 0, n - 1, L2, R2, v2);
		// DB1(L1);
		// DB1(R1);
		// DB1(L2);
		// DB1(R2);
		// return 0;
    }
    // cerr << "Time: " << (ldb)clock() / (ldb)CLOCKS_PER_SEC << '\n';
    return 0;
}

I don't know why does it give me out of bounds error because it runs normally on my computer. I think it's because of the getline function and the fflush(stdin). Can anyone help me :(.

Read more »

 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it

By CooloTran, history, 4 months ago, In English

This is my first blog so tell me if I'm wrong somewhere :) (my english is bad)

Problem

Given an undirected complete graph with $$$n$$$ vertex. There are $$$m$$$ edges that are getting deleted. Given the starting point $$$s$$$, find all the shortest path from note $$$v$$$( $$$v$$$ is not equal to $$$s$$$ ).

Naive solution

We build a complete graph first and after that erase all the edge that are getting deleted by the user. We just iterate through all the edges of every note using bfs and print all the shortest distance from other vertex.

So this solution has a time complexity of $$$O(n + n^2)$$$( Which is not possible for large number of edge $$$\approx$$$ $$$10^{10}$$$).

Big problem

Notice that the bfs technique only insert the note that haven't been colored yet( also the problem we are facing to reduce the time complexity ).

How to deal with it?

So what we can do is to maintain an array and the size of the uncolored vertex.

In a step of bfs we will iterate through all the vertex Adjacent with the current vertex that doesn't show up in the deleted edge and haven't been colored yet( using another markup array to check if the current note is the deleted edge ) and after that swap the current vertex to the end of the Haven't been colored index and increase the size of the colored index to 1 and continue process all the remains uncolored vertex.

Surprisingly, this solution run fast enough to pass with small value of $$$m$$$ $$$\approx$$$ $$$10^5$$$.

Time complexity?

So, all the vertex in the array that we are maintain only being used once if that vertex haven't been colored and is not deleted, and being use as the same number of edge that are include this vertex in the deleted edges $$$k$$$ times if that vertex haven't been colored but is deleted.

So the total time complexity will be $$$O(n + m)$$$ with $$$m$$$ is the number of deleted edge in the complete graph.

Relative problem

Given an undirected complete graph consist of $$$n$$$ vertex ( $$$n \leq 10^4$$$ ) and $$$m$$$( $$$m \leq n \times \sqrt{n}$$$ ) edges beging deleted (as usual). Given $$$q$$$ queries ( $$$q \leq 10^6$$$ ) of type $$$a => b$$$ (the shortest path from $$$a$$$ to $$$b$$$).

Solution

We will not discuss the naive solution here.

Let's look at a path from $$$u$$$ to $$$v$$$: Considere vertex $$$u$$$, if the number of edges that include $$$u$$$ that is deleted and the number of that type of edge is smaller than $$$\frac{n}{2}$$$, if it's also true for $$$v$$$ then according to Pigeonhole principle $$$u$$$ and $$$v$$$ must have at least one common vertex ( as it adjacent list are greater than $$$\frac{n}{2}$$$ ) or $$$u$$$ and $$$v$$$ have an edge that are not deleted to each other. So beside that, there's are no better distance from $$$u$$$ to $$$v$$$.

Consider the case where $$$u$$$ or $$$v$$$ have at least $$$\frac{n}{2}$$$ edge being deleted. As we know that the maximum number of vertex that have at least $$$\frac{n}{2}$$$ edges deleted in the adjacent list is at most $$$\sqrt{n}$$$ vertex ( As there're at most $$$n \times \sqrt{n}$$$ edges being deleted) so we are going to use the same technique as the previous section does to bfs on small amount of deleted edges for all the edge that have at least $$$\frac{n}{2}$$$ adjacent vertex being deleted.

Time comlexity

As there're only at most $$$\sqrt{n}$$$ vertex that have at least $$$\frac{n}{2}$$$ adjacent vertex in the deleted set and we are using the BFS on a complete graph but with a small amount of edge deletion that cost $$$O(m)$$$ per a vertex so the total complexity will be $$$O(\sqrt{n} \times m)$$$ $$$\approx$$$ $$$O(\sqrt{n} \times n \times \sqrt{n})$$$ $$$\approx$$$ $$$O(n ^ 2)$$$ which is enough to solve the problem.

Read more »

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