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.

Find on CodeChef

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!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *