PROBLEM LINK:
Author: Jeevan Jyot Singh
Tester: Aryan Choudhary
DIFFICULTY:
EASY
PREREQUISITES:
Trees
PROBLEM:
Chef’s friend JJ challenged him to construct a tree which has exactly R red coloured nodes, G green coloured nodes and B blue coloured nodes.
To make the task interesting he added an extra condition: the simple path between any two blue nodes should contain at least one red node and at least one green node.
Can you help Chef to complete JJ’s challenge by constructing any valid tree that satisfies these conditions?
(It is given that R, G, B \ge 1)
QUICK EXPLANATION:
If B \gt R + G, then the answer does not exist. Otherwise it is always possible to make the graph in the following way:
- Make a bipartite graph using the R red nodes and G green nodes. Attach each of the B blue nodes to a distinct non-blue node.
EXPLANATION:
Let’s first determine the condition when a tree will not exist given the constraints we have imposed.
Claim: If B > R + G, then no tree will fulfil the requirements.
Proof: By pigeonhole principle, if B > R + G, we would have atleast one non-blue node having \ge 2 blue nodes attached to it. In this case, the condition is not satisfied because the path between these 2 blue nodes will not contain atleast 1 red node and atleast 1 green node.
Now, there are many ways to construct a tree satisfying the properties, but let’s discuss an easy construction:
- Make a bipartite graph using the R red nodes and G green nodes. Attach each of the B blue nodes to a distinct non-blue node.
Since every blue node is connected to a non-blue node, the only path between two blue nodes must pass through at least 2 non-blue nodes. Since the tree of non-blue nodes we constructed was bipartite in reds and greens, it is guaranteed that the path between any two blue nodes will pass through at least 1 red and atleast 1 green node.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int r, g, b; cin >> r >> g >> b;
if(r + g < b)
{
cout << -1 << '\n'; return;
}
string colors = "RG";
vector<pair<int, int>> edges{{1, 2}};
r--, g--;
int cur = 3;
while(r--)
{
colors += 'R';
edges.push_back({2, cur++});
}
while(g--)
{
colors += 'G';
edges.push_back({1, cur++});
}
for(int i = 1; i <= b; i++)
{
colors += 'B';
edges.push_back({i, cur++});
}
cout << colors << '\n';
for(auto [x, y]: edges)
cout << x << " " << y << '\n';
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T;
while(T--)
{
solve();
}
return 0;
}
Tester's Solution
/* in the name of Anton */
/*
Compete against Yourself.
Author - Aryan (@aryanc403)
Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/
#ifdef ARYANC403
#include <header.h>
#else
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize ("-ffloat-store")
#include<bits/stdc++.h>
#define dbg(args...) 42;
#endif
// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
Fun fun_;
public:
template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
using namespace std;
#define fo(i,n) for(i=0;i<(n);++i)
#define repA(i,j,n) for(i=(j);i<=(n);++i)
#define repD(i,j,n) for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
vi readVectorInt(int n,lli l,lli r){
vi a(n);
for(int i=0;i<n-1;++i)
a[i]=readIntSp(l,r);
a[n-1]=readIntLn(l,r);
return a;
}
// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
// vector<vi> e(n);
// atcoder::dsu d(n);
// for(lli i=1;i<n;++i){
// const lli u=readIntSp(1,n)-1;
// const lli v=readIntLn(1,n)-1;
// e[u].pb(v);
// e[v].pb(u);
// d.merge(u,v);
// }
// assert(d.size(0)==n);
// return e;
// }
const lli INF = 0xFFFFFFFFFFFFFFFL;
lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}
class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{ return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }};
void add( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt==m.end()) m.insert({x,cnt});
else jt->Y+=cnt;
}
void del( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt->Y<=cnt) m.erase(jt);
else jt->Y-=cnt;
}
bool cmp(const ii &a,const ii &b)
{
return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
const lli mod = 1000000007L;
// const lli maxN = 1000000007L;
lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
lli m;
string s;
vi a;
//priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .
int main(void) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
// freopen("txt.in", "r", stdin);
// freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
T=readIntLn(1,1e2);
while(T--)
{
const lli sumRGB = 1000;
lli r=readIntSp(1,sumRGB),g=readIntSp(1,sumRGB-r),b=readIntLn(1,sumRGB-r-g);
if(r+g<b){
cout<<-1<<endl;
continue;
}
vii edges;
string col="RG";
lli cur=2;
edges.pb({0,1});
r--;g--;
while(r--){
col+="R";
edges.pb({1,cur});
cur++;
}
while(g--){
col+="G";
edges.pb({0,cur});
cur++;
}
lli idx=0;
while(b--){
col+="B";
edges.pb({idx,cur});
cur++;
idx++;
}
cout<<col<<endl;
for(auto x:edges)
cout<<x.X+1<<" "<<x.Y+1<<endl;
} aryanc403();
readEOF();
return 0;
}