Would like to propose a contest:
Let's see who can find the largest number of websites/channels etc which have the same type of icons as CF. I am volunteering two:

• https://really.sg/
• https://www.youtube.com/c/UsefulCharts

Have fun guys! Let the contest begin :)

Guys no cheating, cannot be CF-adjacent websites ;)

Just a heads up if someone else gets this bug:

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

I usually add these two lines of pragmas in my code. But on submitting it to the POI judge, it gives runtime error 4, and when excluded, it doesn't.

Would also be nice if someone could elaborate on why Runtime error 4 is returned on passing the pragmas.

Hi everyone, Quarantine, though necessary, is honestly a tad boring, especially the months between school and college. So........ I recently started a Youtube channel (coz why not), and intend to post some solutions to OI Problems I have solved in the past year. I will discuss solutions from POI/BOI/CEOI/JOI etc, and expect the problems to be from 1900-2600 difficulty level (?!). Obviously, these will be just the problems I have managed to solve, with/without help, so they won't be super tough. Also, some of these problems might not have proper editorials or at least English translated ones, so hopefully, it will be useful.

Polish Olympiad in Informatics:
2014:
POI — 2014 — Round2 — Day2 — LittleBird
POI — 2014 — Round2 — Day2 — Rally

2018:
POI — 2018 — Round2 — Day1 — BikePath
POI — 2018 — Round2 — Day1 — Conductor
POI — 2018 — Round2 — Day2 — Transceivers
POI — 2018 — Round2 — Day2 — Book Of Poetry
POI — 2018 — Round2 — Day1 — Complete Numbers NEW
POI — 2018 — Round3 — Day2 — Polynomials NEW
POI — 2018 — Round3 — Day2 — Taxis NEW
POI — 2018 — Round3 — Day2 — Two Long Candy Sticks NEW

Japanese Olympiad in Informatics : Final Round
2020:
JOI — Final Round — 2020 — P5 — Fire

Simple Topic Series
Dynamic Programming Broken Down NEW

The problem statement and AC codes are linked in the description.

These are pretty easy, maybe around 2000 level (?!). I'll maybe do a few easier problems and once I gain a bit more experience, I'll post solutions of the harder ones.

Feedback is appreciated.

UPD: POI 2018 Round 3 videos coming soon!!

For this problem (2017 Round 3 day 2), when I submit a wrong code, it gives a score and everything properly. When I try submitting my correct (i mean, atleast what I think should be correct :P ) it just gives "Initial Tests:OK" in a green color as would usually appear for a 100 pnt solution, but it doesnt give the detailed list of in which testcases what happened, and most importantly, nor does it give a Score.

My Code and solution: click

Can we access the testcases for this problem somehow, or test it otherwise?

UPDATE: It now somehow works fine, (and I got AC, but had to change the code a bit, anyhow.) I am not sure behind the magic of this mystery but oh well.

I have been searching for examples of usage of online Minimum Spanning Trees, but everything seems to be using the static minimum spanning tree and then some processing. Is there any actual use case of online MST finding, apart from just the purely theoretical aspect of it? (and except CP probs obvio).

Update: Clustering algorithms seems to be one such use case.

(Ill add to this if I find anything more, others please comment too if you know of any)

I was learning DSU tree (also sometimes known as Reachability Tree) recently (see link below) but the most useful application that I could think was for finding maximum/minimum edge in path from some node A to B. However, this can also be done in O(log N) time using Link Cut Trees.

I was wondering if there was anything that can be done by this DSU-tree/Reachability Tree data structure that can't already be done by LCT.

(I am not that well versed with applications of LCT)

Brief idea about Reachability tree for those too bored to read the editorial linked:

Basically, when we iterate over the edges in a tree in order of weight, we also maintain which edge is connecting which component. So suppose an edge e connects components A and B, we create a new node signifying e and attach to its children A and B. Thus it forms a binary tree, with the leaves as the original nodes, and the n-1 internal edges are basically edges in the normal tree.

(https://discuss.codechef.com/t/tulips-editorial/12281)

Can the timing of the edu round today be shifted by 30 mins? Then it would not be clashing with the round 2 of JOI OC, 2019.

I recently came across something called fractured Searching.

Example prob : Kth MST. Outline : We basically find a MST, now fix a prefix of the edges used and say the rest can be changed, and depending on length of the prefix, we divide the rest of our search space into different regions, and search in them again.

Another prob : Third Prob of this link

Editorial Solution : click

There is also a video on this on youtube by Algorithms Live.

Can someone provide more problems that can be solved by this technique, since its hard to find tags that describe such approach.

UPDATE : THE CODE IS AC NOW, THERE WAS SOME MISTAKES IN IMPLEMENTATION. AC code

Hi, I have been trying this problem, and I have an alternate solution to the editorial as follows:

Form a new graph, with nodes as (prevNode, currNode), to keep track of which node we are coming from. There will be an edge from (A,B) to (B,C) in the new graph if A-B-C is not a 3-cycle in the original graph. Now, after forming this graph, find a cycle in it. This will correspond to a cycle in my orginal graph too. Now i claim that in this cycle of my original graph, there will be no 3 consecutive nodes that form a 3-cycle, due to the constraint of edge on my new graph. So the cross edges that we will have will divide my cycle into sectors with more than 3 nodes. Hence outputting any such sector should be fine. However, I am getting WA on most of my cases. The code is printing "no", which i found was that it was indeed getting a cycle in the new graph but couldnt find such sector in my original cycle for some reason.

Can someone confirm if the solution is correct? (my implementation is not good so there is a high chance i am coding it wrong). And if its incorrect, can someone give a counterexample to either of the claims, 1) if there is a valid graph which does not give a cycle in my new graph, or 2) any cycle in my new graph will correspond to cycle in my original graph that will have sectors that are not 3-cycles

Thanks for any help.

my code

this is the pdf link, see p2 (mobiles).

SOLUTION : binsrch on answer and check. however my code is giving error (WA). its quite small, so hopefully it will be readable.

Any help is appreciated.

PS: main function only has the binary search part. Check function checks if the dist chosen will cover the entire line. i have removed the redundant segments using deque using the fact that the points are already sorted by x coordinate

#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <complex>
#include <stack>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>

const ld INF = 1e9+10;
using namespace std;
const int MAXN = 1000*1000+10;

vector<pld> allP;

bool check(ld dist,ld l){
	deque<pld> dq;
	for(auto e : allP){
		ld dd = dist*dist - e.ss*e.ss;
		if(dd < 0)continue;
		dd = sqrt(dd);
		pld r = {e.ff-dd,e.ff+dd};
		while(dq.size() > 0 and dq.back().ff >= r.ff)
			dq.pop_back();
		dq.pb(r);
	}
	if(dq.empty())return 0;
	if(dq.front().ff > 0)return 0;
	ld right = dq[0].ss;
	FORE(i,1,(int)dq.size()-1){
		if(dq[i].ff > dq[i-1].ss)return 0;
		right = max(right,dq[i].ss);
	}
	return right >= l;
}


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n,l;
	cin >> n >> l;
	FOR(i,n){
		int a,b;
		cin >> a >> b;
		allP.pb({a,abs(b)});
	}
	ld lo = 0;
	ld hi = 3e9;
	ld best = 1e12;
	while(lo <= hi){
		if(hi-lo < 1e-5){
			break;
		}
		ld mid = (lo+hi)/2;
		if(check(mid,l)){
			best = min(best,mid);
			hi = mid;
		}else{
			lo = mid;
		}
	}
	printf("%.5f\n",(double)best);
	return 0;
}

I was trying to implement Aliens-IOI 16.

For subtassk 5, the a CHT should suffice. However, my code gets TLE on it. Is it that we have to do the O(n) variant only? The LiChao part is in a class, so hopefully the code will not seem to be too cluttered.

code.

I was trying out implementing a incremental version of CHT with sqrt decomposition. I noticed a very wierd thing though. When I made my block size = 350, the code TLEd with >2000ms. However when i made it 351, it passed in 390ms

Here are two sets of submissions that differ in only 1 aspect, the block size.

blocksize = 350 : TLE

blocksize = 350 : TLE

blocksize = 351 : AC(389ms)

This seems very wierd to me, since blocksizes of <350 also give AC(although with more time. blocksize = 200 with AC in 1669 ms). However, its the specific value of 350 that times out.

What could be a possible for reason for this? I am just curious. (As far as i can see, my code does not have any undefined behaviour.)

I was looking at this NOI problem from another CF post.

Apparently there is a network flow solution to it, but i don't get how it works. Can someone explain in a bit more details? I am not too experienced in flows. Would be a great help.

(PS: I got the LP constraints. If that is important.)

I have been writing some tutorials, of some beginner/intermediate topics. These are mostly intended at beginners. Hopefully will be helpful to the newer folks in the community.

Beginners:
Graph — 1
Graph — 2
Graph — 3
Trees
Intro to DP

Medium:
Euler Tour
Centroid Decomposition
Spanning trees
Small To Large Merging
2-D structures — 1
Converting From 1D to 2D
Persistance : A Problem Perspective

Advanced:
Segment Tree Beats — Intro
SegTreeBeats- Complexity -1
SegTreeBeats — Complexity -2

UPD: Persistance usecases blog.

Hey,

I recently read this blog, about segment tree beats, but it took me a lot of time to understand this. Thus I have written some blogs on my own stating my own understanding of the topic, so that it is closely linked to the original blog, yet so that its a bit easier to understand. I have explained some of the key concepts that I feel were only touched upon in the original blog but was actually important. However, whatever I have written is based on the original article.

This only includes the explanations for the general concept and the proofs of task 1 and task 2 only. However I hope this explains the proof method itself in a better fashion.

I have also tried to prove the first task using the method in task 2. However I dont yet know whether it is actually correct, and if someone points out the flaw then I would remove it from my post.

Also, any improvements can be suggested in the comments and I would try to update them as soon as possible.

concept task 1 task 2

I have a dynamic connecticity problem, but with a additional constraint. The edges that can be added cannot be removed, and the edges that are being removed, cannot be added back. We initially have a graph too, so basically, the edges that are present in the initial graph can be removed, and new edges can be added, but the edges that are added later cannot be removed. they are permanant. Is there a simpler solution to this problem, than the normal fully connected dynamic connectivity problem?

P.S: can someone give me a link to any problem based on online fully dynamic connectivity.

I have a undirected graph, with 0/1 edge cost. The graph is a complete graph. I have two operations: -- update: flip the edge cost of a particular edge. that is, if it's cost was 0, make it 1, or vice versa. -- query: shortest path between the source and target vertex.

We are given the graph as a adjacency matrix, as well as the source and the target node in the input. The source and the target node remain fixed. Expected memory is o(n^2) (obviously) and time complexity is o(logn) for both update and query.

Thanks for any help in advance.