Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Tidying Posters CodeChef Solution
Problem -Tidying Posters CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Tidying Posters CodeChef Solution in C++17
#include <bits/stdc++.h>
#ifdef BrehamPie
#include "debug.h"
#else
#define debug(args...)
#endif
using namespace std;
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define mem(x, i) memset(x, i, sizeof x)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld; //%Lf
const int mod = 1e9+7;
const int mx = 2e5+5;
struct Point {
int x, y;
};
// Returns true if two rectangles (l1, r1) and (l2, r2)
// overlap
bool doOverlap(Point l1, Point r1, Point l2, Point r2)
{
if(l1.x<l2.x && r2.x<r1.x && l2.y<l1.y && r1.y<r2.y) return true;
return false;
}
struct HK {
static const int inf = 1e9;
int n;
vector<int>matchL, matchR, dist;
//matchL contains value of matched node for L part.
vector<vector<int>>adj;
HK(int n) :n(n), matchL(n + 1),
matchR(n + 1), dist(n + 1), adj(n + 1) {
}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
bool bfs() {
queue<int>q;
for (int u = 1;u <= n;u++) {
if (!matchL[u]) {
dist[u] = 0;
q.push(u);
}
else dist[u] = inf;
}
dist[0] = inf;///unmatched node matches with 0.
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v : adj[u]) {
if (dist[matchR[v]] == inf) {
dist[matchR[v]] = dist[u] + 1;
q.push(matchR[v]);
}
}
}
return dist[0] != inf;
}
bool dfs(int u) {
if (!u) return true;
for (auto v : adj[u]) {
if (dist[matchR[v]] == dist[u] + 1
&& dfs(matchR[v])) {
matchL[u] = v;
matchR[v] = u;
return true;
}
}
dist[u] = inf;
return false;
}
int max_match() {
int matching = 0;
while (bfs()) {
for (int u = 1;u <= n;u++) {
if (!matchL[u])
if (dfs(u))
matching++;
}
}
return matching;
}
};
void solve() {
int n;
cin>>n;
vector<pair<Point,Point>>posters;
for(int i=0;i<n;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
posters.push_back({{a,c},{b,d}});
}
HK hk(n*2);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(doOverlap(posters[i].first,posters[i].second,posters[j].first,posters[j].second)){
hk.addEdge(i+1,j+1+n);
}
}
}
cout<<n-hk.max_match()<<endl;
}
void preprocess() {
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
preprocess();
int t = 1;
cin >> t;
for (int i = 1; i <= t; i++) {
solve();
}
}Tidying Posters CodeChef Solution in C++14
#include <bits/stdc++.h>
#ifdef BrehamPie
#include "debug.h"
#else
#define debug(args...)
#endif
using namespace std;
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define mem(x, i) memset(x, i, sizeof x)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld; //%Lf
const int mod = 1e9+7;
const int mx = 2e5+5;
struct Point {
int x, y;
};
// Returns true if two rectangles (l1, r1) and (l2, r2)
// overlap
bool doOverlap(Point l1, Point r1, Point l2, Point r2)
{
if(l1.x<l2.x && r2.x<r1.x && l2.y<l1.y && r1.y<r2.y) return true;
return false;
}
struct HK {
static const int inf = 1e9;
int n;
vector<int>matchL, matchR, dist;
//matchL contains value of matched node for L part.
vector<vector<int>>adj;
HK(int n) :n(n), matchL(n + 1),
matchR(n + 1), dist(n + 1), adj(n + 1) {
}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
bool bfs() {
queue<int>q;
for (int u = 1;u <= n;u++) {
if (!matchL[u]) {
dist[u] = 0;
q.push(u);
}
else dist[u] = inf;
}
dist[0] = inf;///unmatched node matches with 0.
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v : adj[u]) {
if (dist[matchR[v]] == inf) {
dist[matchR[v]] = dist[u] + 1;
q.push(matchR[v]);
}
}
}
return dist[0] != inf;
}
bool dfs(int u) {
if (!u) return true;
for (auto v : adj[u]) {
if (dist[matchR[v]] == dist[u] + 1
&& dfs(matchR[v])) {
matchL[u] = v;
matchR[v] = u;
return true;
}
}
dist[u] = inf;
return false;
}
int max_match() {
int matching = 0;
while (bfs()) {
for (int u = 1;u <= n;u++) {
if (!matchL[u])
if (dfs(u))
matching++;
}
}
return matching;
}
};
void solve() {
int n;
cin>>n;
vector<pair<Point,Point>>posters;
for(int i=0;i<n;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
posters.push_back({{a,c},{b,d}});
}
HK hk(n*2);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(doOverlap(posters[i].first,posters[i].second,posters[j].first,posters[j].second)){
hk.addEdge(i+1,j+1+n);
}
}
}
cout<<n-hk.max_match()<<endl;
}
void preprocess() {
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
preprocess();
int t = 1;
cin >> t;
for (int i = 1; i <= t; i++) {
solve();
}
}Tidying Posters CodeChef Solution in C
#include <stdio.h>
int n, next, x0[110], y0[110], x1[110], y1[110], m[110], b[110], e[110][110];
inline int attr(int a, int b, int c, int d)
{return a<c&&d<b;}
int proc(int x)
{
int y=0;
for(b[x]=next; y<n; y++)
if(e[x][y]&&(m[y]==-1||(b[m[y]]!=next&&proc(m[y]))))
{m[y]=x;return 1;}
return 0;
}
main()
{
int fall, i, j, r;
for(scanf("%d",&fall); fall--; printf("%d\n",r))
{
for(i=-scanf("%d",&n); ++i<n; scanf("%d %d %d %d",&x0[i],&x1[i],&y0[i],&y1[i]));
for(i=0,r=n; i<n; i++)
for(j=-1; ++j<n; e[i][j]=attr(x0[i],x1[i],x0[j],x1[j])&&attr(y0[j],y1[j],y0[i],y1[i]));
for(i=next=0; i<n; m[i++]=-1);
for(i=0; i<n; next++,r-=proc(i++));
}
return 0;
}Tidying Posters CodeChef Solution in JAVA
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for(int t=1; t<=T; t++) {
int n = in.nextInt();
Rectangle[] v = new Rectangle[n];
for(int i=0; i<n; i++)
v[i] = new Rectangle(in.nextInt(),in.nextInt(),in.nextInt(),in.nextInt());
Matching match = new Matching(2*n);
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(v[i].contains(v[j]))
match.add(i,n+j);
System.out.println(n - match.run());
}
}
static class Rectangle {
int x1, x2, y1, y2;
Rectangle(int a, int b, int c, int d) {
x1 = a;
x2 = b;
y1 = c;
y2 = d;
}
boolean contains(Rectangle rhs) {
return x1 < rhs.x1 && x2 > rhs.x2 && y1 > rhs.y1 && y2 < rhs.y2;
}
}
static class Matching {
Set<Integer>[] g;
int n, m = 0;
int[] match, parent;
Matching(int N) {
g = new Set[n=N];
for(int i=0; i<n; i++) g[i] = new HashSet<Integer>();
Arrays.fill(parent = new int[n], -1);
Arrays.fill(match = new int[n], -1);
}
void add(int x, int y) {
g[x].add(y); g[y].add(x);
}
int run() {
while(augment(getPath(g))) m++;
return m;
}
ArrayDeque<Integer> getPath(Set<Integer>[] g) {
int[] d = new int[n], root = new int[n];
ArrayDeque<Integer> q = new ArrayDeque<Integer>();
for(int i=0; i<n; i++)
if(match[i] == -1) q.add(root[i] = i);
else root[i]=d[i]=n+1;
while(!q.isEmpty()) {
int cur = q.poll();
for(int x : d[cur]%2 == 0 ? g[cur] : Arrays.asList(match[cur])) {
if(x == cur) continue;
if(d[x] > d[cur]+1) {
d[x] = d[cur]+1;
root[x] = root[parent[x] = cur];
q.add(x);
}
else if(d[cur] == d[x] && ((d[cur]%2 == 0) ^ (match[cur]==x))) {
if(root[cur] == root[x]) {
List<Integer> b = new ArrayList<Integer>(getPath(x, cur));
Set<Integer> bset = new HashSet<Integer>(b); // blossom
cur = parent[b.get(0)];
Set<Integer>[] g2 = new Set[n];
for(int i=0; i<n; i++) g2[i] = new HashSet<Integer>();
for(int i=0; i<n; i++) for(int j : g[i])
g2[bset.contains(i)?cur:i].add(bset.contains(j)?cur:j);
ArrayDeque<Integer> path = getPath(g2);
if(path.isEmpty()) return path;
ArrayDeque<Integer> ret = new ArrayDeque<Integer>();
ArrayDeque<Integer> tmp = new ArrayDeque<Integer>();
int z = path.pop(), ind=0;
ret.add(z);
for(int prev = z; !path.isEmpty(); ret.add(prev=z))
if(!g[prev].contains(z = path.pop())) {
for(int i=0; i<b.size(); i++)
if(g[prev==cur?z:prev].contains(b.get(i)))
ind = i;
if(ind%2==0) while(ind < b.size()) tmp.add(b.get(ind++));
else while(ind >= 0) tmp.add(b.get(ind--));
while(!tmp.isEmpty())
ret.add(prev==cur ? tmp.pollLast() : tmp.pollFirst());
}
return ret;
}
else return getPath(cur, x);
}
}
}
return new ArrayDeque<Integer>();
}
ArrayDeque<Integer> getPath(int s, int t) {
ArrayDeque<Integer> ret = new ArrayDeque<Integer>();
for(int x = s, y = t; x != y; x = parent[x], y = parent[y]) {
ret.push(x); ret.add(y);
}
return ret;
}
boolean augment(ArrayDeque<Integer> path) {
if(path.isEmpty()) return false;
while(!path.isEmpty()) {
int x = path.pop(), y = path.pop();
match[match[x] = y] = x;
}
return true;
}
}
}Tidying Posters CodeChef Solution in GO
package main
import (
"bufio"
"bytes"
"fmt"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
var buf bytes.Buffer
tc := readNum(reader)
for tc > 0 {
tc--
reader.ReadBytes('\n')
n := readNum(reader)
posters := make([][]int, n)
for i := 0; i < n; i++ {
posters[i] = readNNums(reader, 4)
}
res := solve(n, posters)
buf.WriteString(fmt.Sprintf("%d\n", res))
}
fmt.Print(buf.String())
}
func readUint64(bytes []byte, from int, val *uint64) int {
i := from
var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readString(reader *bufio.Reader) string {
s, _ := reader.ReadString('\n')
for i := 0; i < len(s); i++ {
if s[i] == '\n' {
return s[:i]
}
}
return s
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
return res
}
func solve(n int, rects [][]int) int {
g := make([][]bool, n)
overlap := func(i, j int) bool {
a, b := rects[i], rects[j]
return a[0] < b[0] && b[1] < a[1] && b[2] < a[2] && a[3] < b[3]
}
for i := 0; i < n; i++ {
g[i] = make([]bool, n)
for j := 0; j < n; j++ {
g[i][j] = overlap(i, j)
}
}
var ans int
v := make([]bool, n)
pair := make([]int, n)
for i := 0; i < n; i++ {
pair[i] = -1
}
var aug func(x int) bool
aug = func(x int) bool {
if v[x] {
return false
}
v[x] = true
for y := 0; y < n; y++ {
if g[x][y] && (pair[y] < 0 || aug(pair[y])) {
pair[y] = x
return true
}
}
return false
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
v[j] = false
}
if aug(i) {
ans++
}
}
return n - ans
}Tidying Posters CodeChef Solution Review:
In our experience, we suggest you solve this Tidying Posters CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Tidying Posters CodeChef Solution.
Conclusion:
I hope this Tidying Posters CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
