Hey there.

I have the following problem, not from any ongoing or past contest. Can you help me, by suggesting what optimal methods you have to solve it.

Node has three properties: left, right, height

N Insert node queries. Each query is (l, r, h).

Now M queries ask following: L, R, H
For all nodes(l, r, h), that satisfy L <= l && r <= R,
return min( abs( H — h) )

Can you guys suggest some approaches that you have in mind?

I recently started learning basics of Java and got stuck on this doubt. How to write Java code for the below given C++ code. Note that making a class and passing an object or returning some object looks like a hack to me. So looking for other possible answers.

// c++ code
void f(int & x, int & y) {
    x++;y++;
}
f(x, y); // function call somewhere

Thanks

Editorial will be completed soon!!

Problem A

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

int main() {
	int n;
	cin >> n;
	bool flag;
	if(n == 1)
	{
		int a, b;
		cin >> a >> b;
		if(a == b)
			flag = 1;
		else
			flag = 0;
	}
	else if(n == 2)
	{
		int a, b, c, d;
		cin >> a >> b;
		cin >> c >> d;
		if(a > b) swap(a, b);
		if(c > d) swap(c, d);
		if(b == d && a + c == b)
			flag = 1;
		else
			flag = 0;
	}
	else if(n == 3)
	{
		int a, b, c, d, e, f;
		cin >> a >> b;
		cin >> c >> d;
		cin >> e >> f;
		if(a > b) swap(a, b);
		if(c > d) swap(c, d);
		if(e > f) swap(e, f);
		if(b > f) {
			swap(a, e);
			swap(b, f);
		}
		if(d > f) {
			swap(c, e);
			swap(d, f);
		}
		flag = 0;
		if(b == d && b == f && b == a + c + e)
			flag = 1;

		if(a == c && b + d == f && a + e == f)
			flag = 1;
		if(b == d && a + c == f && b + e == f)
			flag = 1;
		if(a == d && a + e == f && b + c == f)
			flag = 1;
		if(b == c && b + e == f && a + d == f)
			flag = 1;
	}
	if(flag)
		cout << "yes\n";
	else
		cout << "no\n";
	return 0;
}

This is an adhoc problem. We just need to consider all the possible cases of joining. Note that we can join 2 rectangles only along their common side lengths, if any.

For n = 1, it is trivial, check if it is a square.

For n = 2, only possible way is to join the 2 rectangles.

For n = 3, we have two cases. Either join them all linearly, all 3 in a row kind of fashion. Another way is to join the 2 rectangles to form a greater rectangle and then join third one, perpendicularly.

For all of the above cases, if it is possible to form a square, the side length of square is the largest length / breadth from rectangles.

Problem B

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int main() {
	int l, r;
	cin >> l >> r;
	if(l != -r || r % 2)
		cout << "0";
	else {
		long long ans = 1;
		for(int i = 1; i < r; i += 2)
			ans = ans * 2 * i % mod;
		cout << ans;
	}
}

First of all, g(0) = 0.

Since g(g(x)) = -x then using this condition, g(g(g(0))) = -g(0) if we expand 2 outer g's and g(g(g(0))) = g(0) if we expand 2 inner g's. Thus, if g(0) = -g(0) then g(0) = 0.

Now, let g(a) = b then g(b) = g(g(a)) = -a, similarly g(-a) = g(g(b)) = -b and g(-b) = g(g(-a)) = a. Thus we get {a, b, -a, -b}, that is we need to divide the given integers into such groups.

Therefore, if r != -l, then answer is zero, as we need both positive and negative of a number.

Also, if r is odd, then answer is zero, as we need to divide into groups with exactly 2 positive and their negative integers. By using combinatorics, we can get the answer as follows: ** yet to write further**

Problem C

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

	const int MAXN = 300000;
	const int MO = 1e9;
	typedef long long ll;
	ll n;
	pair<ll, ll> p[MAXN + 10];

	bool cmp (pair<ll, ll> a, pair<ll, ll> b) {
		return a.first * b.second < a.second * b.first;
	}
    
	int main() {
        
		scanf("%d", &n);
		assert(n >= 1 && n <= 300000);
		for(int i = 0; i < n; i++) {
			int a, b, c; 
			scanf("%d%d%d", &a, &b, &c);
			assert(a >= -MO && a <= MO);
			assert(b >= -MO && b <= MO);
			assert(c >= -MO && c <= MO);
			p[i] = make_pair(a, b);
		}

		sort(p, p + n, cmp);

		ll l = 0, r = 0;
		ll ans = 0;

		for(int i = 0; i < n; ++i) {
			while(cmp(p[l], p[i]))
				++l;  									
			while(r < n && !cmp(p[i], p[r])) 
				++r;
			ans += l * (n - r);
		}

		printf("%lld\n", ans);

		return 0;

	}

To find all triangles, we need to find number of ways to select 3 lines such that no 2 of them have same slope.

We can do this counting, by sorting all the lines by their slope. Now let the slope of 3 lines that we select be m1, m2 and m3, such that m1 < m2 < m3.

So we iterate on the 2nd line, that has slope m2 and for each such line, add the possible ways for selecting m1(<m2) and m3(>m2) ways.

Problem D

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

#define pb push_back

typedef long long ll ;

const int mod = 1e9 + 7 ;
ll powmod(ll a,ll b) {ll res=1;if(a>=mod)a%=mod;for(;b;b>>=1){if(b&1)res=res*a;if(res>=mod)res%=mod;a=a*a;if(a>=mod)a%=mod;}return res;}

const int maxn = 100010;
const int inf = INT_MAX;

bool p[1000000 + 5];
vector<ll> prime;

ll f(ll a, ll b, ll n)
{
	ll ret = 1;
	while(1) {
		ret = ret * n;
		if( (a - 1) / ret * ret + ret > b)
			break;
	}
	ret = ret / n;
	return ret;
}
int main() {
	ll n, k;
	cin >> n >> k;
	for(int i = 2; i <= 1000; i++) {
		if(p[i])
			continue;
		for(int j = i * i; j <= 1000000; j += i)
			p[j] = 1;
	}
	for(int i = 2; i <= 1000000; i++)
		if(p[i] == 0)
			prime.pb(i);
	ll ans = powmod(n + 1, mod - 2);
	for(int i = 0; i < prime.size(); i++) {
		ans = ans * f(n + 1 - k, n + 1, prime[i]);
		if(ans >= mod)
			ans %= mod;
	}
	cout << ans << endl;
    return 0;
}

Since C(n, i + 1) = C(n, i) * (n — i) / (i + 1).
We can iterate on i from 1 to k, and keep some table to store the prime factorisation of each C(n, i).

Then we can know the maximum power of each prime that occured and thus their product will give us the required LCM.
Another solution for this problem can be to use a mathematical identity
Let X be the required answer, X = lcm { C(n, 0), C(n, 1), ...C(n, k)} % mod
then (n + 1) * X = lcm(n+1, n, n — 1, ..., n + 1 — k),
for proof of above identity see this
So now all we need is to find the lcm of (n + 1 — k, n + 1 — k + 1, ...n-1, n, n + 1)
We can do this by iterating over all the primes and then iterating on powers from 1 till the smallest power that is not divisible is found in this range.

Problem E

#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 2e5+10;
struct Union_Find{
    int d[SIZE],num[SIZE];
    void init(int n){
        REP(i,n)d[i]=i,num[i]=1;
    }
    int find(int x){
        return (x!=d[x])?(d[x]=find(d[x])):x;
    }
    bool uu(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y)return 0;
        if(num[x]>num[y])swap(x,y);
        num[y]+=num[x];
        d[x]=y;
        return 1;
    }
}U;
int n,m;
struct EDGE{
    int u,v,a,b;
    EDGE(int _u=0,int _v=0,int _a=0,int _b=0):u(_u),v(_v),a(_a),b(_b){}
    bool operator<(const EDGE& e2){return a<e2.a;}
}e[SIZE];
struct data{
    int x,y;
    LL v;
    data(int _x=0,int _y=0,LL _v=0):x(_x),y(_y),v(_v){}
    bool operator<(const data& b)const{
        return v<b.v;
    }
}e2[SIZE];
LL mst(LL x){
    REP(i,m){
        e2[i]=data(e[i].u,e[i].v,e[i].a*x+e[i].b);
    }
    sort(e2,e2+m);
    int r=n-1;
    U.init(n);
    LL res=0;
    REP(i,m){
        if(U.uu(e2[i].x,e2[i].y)){
            r--;
            res+=e2[i].v;
            if(!r)break;
        }
    }
    return res;
}
int main(){
    RII(n,m);
    REP(i,m){
        RII(e[i].u,e[i].v);
        e[i].u--;e[i].v--;
        RII(e[i].a,e[i].b);
    }
    int ll=-100000000,rr=100000000;
    LL ma;
    while(ll<rr){
        int mm1=ll+(rr-ll)/2;
        int mm2=mm1+1;
        LL v1=mst(mm1);
        LL v2=mst(mm2);
        ma=max(v1,v2);
        if(v1<v2)ll=mm2;
        else rr=mm1;
    }
    int med=ll;
    DRI(Q);
    while(Q--){
        DRII(t1,t2);
        if(t1<=med&&med<=t2)printf("%I64d\n",ma);
        else if(med<=t1)printf("%I64d\n",mst(t1));
        else printf("%I64d\n",mst(t2));
    }
    return 0;
}

A suboptimal solution first.

Let us first look at the algorithm for finding Minimum Spanning tree.

We may observe that if the ordering of edges, when sorted by weights, does not change, then the minimum spanning tree remains to be unchanged i.e. the edges in MST remain to be same, even if we increase/decrease the edge weights.

So, if we considered all the pairs of edges, found the time when their edge weights become equal, then one of the edge weight becomes larger than the other one, forever, as they are linear functions of time.

Of course, in some cases, if they are identical, then always same.

Now, sort these O(m^2) times of intersections, we can say that minimum spanning tree between any of the two adjacent times, remains unchanged.
Thus we can find the MSTs for each of these times and answer the queries.
This will certainly TLE, O(m^3 log n).
The optimal solution uses binary search and attains following complexity.
precalculation:(O(log 10^8 * m log(m)))
each query:O(m log(m))
** optimal solution updated **
The sum of edge cost of every possible spaning tree is a linear function for t. So the MST function is a concave function. For solving this problem, we precalculate the highest position of the MST function by ternary search in range [-10⁸, 10⁸]. The time complexity is O(log(10⁸) × m × log(m)). After finishing this step, we get the maximum MST value V_{max} where t is in range [$-10^8$, 10⁸] and let such t as t_max.

Let the MST value of t = x is mst(x).

For each query, if T_i1 ≤ t_max ≤ T_i2, the answer is V_max. If T_i2 ≤ t_max, the answer if mst(T_{i2}). Otherwise, the answer is mst(T_{i1}).

Hi everyone!

I would like to invite you to the Weekly Training Farm 25 !! The problemsetter is me (dreamplay) and the tester and quality controller is dreamoon_love_AA. Big thanks to drazil for his help in preparation.

It will be a 2 hour — 5 problems contest, with ACM-ICPC style scoring, will be held on codeforces, 1.5 hours after CF round #402.

Contest time: 17:00 UTC + 5.5
Contest link: Join the group (as participant) first and find Weekly Training Farm 25.

Editorial will be provided right after the contest.
Here are the standings from a recent Weekly Training Farm contest.

Good luck and hope you enjoy the problem solving!

UPD: 30 min to the start !!

UPD: contest is over. Hopefully, each of you liked atleast one problem.

Sadly, last problem went unsolved. Happy upsolving.
Editorial will be posted soon.
Congratulations to Winners.
1. zscoder
2. eddy1021
3. cchao
UPD: Here's the Editorial.

Given a polygon of n points in counter-clockwise order and then some queries, result of each query being either INSIDE(point is inside or on the boundary) or outside (point outside the boundary)
This is the code I refer to.
Input:
3
0 0
2 0
2 2

1 1

Output:
Outside

Expected Output:
Inside ( point is on boundary )
Am I missing something, or is there an error while handling the boundary case? Similar error is also commented in russian on the link.

Given n points (x,y) on a euclidean plane. A radius R.
Input: Q queries of form (a,b)
Output: For each query, points within radius R

Suggest a solution to this?

Expected complexity: Better than brute force, asymptotically.

This is a reminder to the ACM ICPC Practise contest for the Amritapuri,India Site Preliminary Round.

The preliminary round will be held on 11th of October whereas Practise Contest will be held Tonight i.e. 6th October from 9pm to 2am, 7th October (IST/GMT+5:30)

Although the timings clash with Codeforces Round #324, here`s the Practise contest Link

Greetings.Thank you.

A very warm Happy Birthday to our Greatest Gennady Korotkevich aka tourist.

I'd like to call upon all of you especially Petr on this special day, to say just 2-3 lines about him apart from wishing him.

Here's Mine: Tourist, is an inspiration to me and motivates me to work hard, not because of his unreachable ratings, but because of the humility that he has even after being the best and the fact that he still works hard to get better.

It would be great if someone could explain how to exactly solve this problem .

I know about BIT , had even tried of using it during the contest but I don`t know how , even after reading the editorial. Please explain in a better way . Thanks .

Also it`d be great if you could suggest similar problems .

I need to perform following queries What data structure can i use or modify to.

1) Insert/delete an element(comparable) , say integer , in some order such that i.e. iteration from smallest to largest element at any time , takes O(number of elements) .

2) number of elements greater than ei is given in O(logn) .

...I thought of adding an attribute at each node of r-b tree which stores number of elemts in subtree rooted at that element but this seems incorrect too .

I have often encountered problems(in gym) which reduce to finding C(n,r) % p , where p is not necessarily prime . Also n and r are both large . Essentialy they demand for the use of Lucas and Chinese Remainder Theorem.

For constraints let`s take this problem .

This link does help a lot but I am still confused , especially in the part which asks to use C.R.Theorem . How to apply CRT?

Also what if p is not a square free number ?

Along with explaination , a link to code would be extremely helpful.

http://www.spoj.com/SPOJ/problems/ABCPATH/

Consider the above problem which can possibly have a maximum of 2500 letters.

It is a dp on graphs problem,solvable by dfs.

But I had this doubt

Let us consider using say ** dfs only** and not using any sort of DP. What is then the worst case time complexity of the dfs-solution. Expressed in terms of number of steps/letters traversed on the graph.