Crease Painting CodeChef Solution

Problem -Crease Painting 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.

Crease Painting CodeChef Solution in C++14


#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <map>
#include <cassert>
#define mod  1000000007
#define PHI 1000000006
#define ull unsigned long long
#define ll long long int
#define pii pair<int,int>
#define pb(x) push_back(x)
#define F(i,a,n) for(i=(a);i<(n);++i)
#define FD(i,a,n) for(i=(a);i>=(n);--i)
#define FE(it,x) for(it=x.begin();it!=x.end();++it)
#define V(x) vector<x>
#define S(x) scanf("%d",&x)
#define S1(x) scanf("%llu",&x)
#define MAX 50009
#define NIL 0
#define INF (1<<28)

#define MAXNODES 50009
using namespace std;

int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
ll startx[1002];
ll endx[1002];
ll starty[1002];
ll endy[1002];
void intersect(ll sx1,ll sy1,ll ex1,ll ey1,ll sx2,ll sy2,ll ex2,ll ey2, vector<pair<ll,ll> >* segments)
{
    if(sx2==ex2)
    {
        if(sx1!=sx2)
            return;
        ll sy3=max(min(sy1,ey1),min(sy2,ey2));
        ll ey3=min(max(sy1,ey1),max(sy2,ey2));
        if(sy3>ey3)
            return;
        segments->push_back(make_pair(sy3,ey3));
        return;
    }
    if(sy2==ey2)
    {
        if(sy2>=min(sy1,ey1) && sy2<=max(sy1,ey1) && min(sx2,ex2)<=sx1 && max(sx2,ex2)>=sx1)
            segments->push_back(make_pair(sy2,sy2));
        return;
    }
}
map<pair<int,int>,bool> hashed;
int main()
{
    int N;
    scanf("%d",&N);
    ll cx=0;
    ll cy=0;
    ll answer=0;
    startx[0]=endx[0]=starty[0]=endy[0]=0;
    for(int i=1;i<=N;i++)
    {
        char dir[3];
        ll steps;
        int id;
       scanf("%s",&dir);
       scanf("%lld",&steps);
        if(dir[0]=='R')
            id=0;
        if(dir[0]=='L')
            id=1;
        if(dir[0]=='U')
            id=2;
        if(dir[0]=='D')
            id=3;
        startx[i]=cx+dx[id];
        starty[i]=cy+dy[id];
        endx[i]=cx+dx[id]*steps;
        endy[i]=cy+dy[id]*steps;

        cx=endx[i];
        cy=endy[i];
        vector<pair<ll,ll> > segments;
        for(int j=0;j<i;j++)
        {
            if(startx[i]==endx[i])
                intersect(startx[i],starty[i],endx[i],endy[i],startx[j],starty[j],endx[j],endy[j],&segments);
            else
                intersect(starty[i],startx[i],endy[i],endx[i],starty[j],startx[j],endy[j],endx[j],&segments);
        }
        sort(segments.begin(),segments.end());
        ll st=(startx[i]==endx[i]?min(starty[i],endy[i]):min(startx[i],endx[i]));
        ll en=(startx[i]==endx[i]?max(starty[i],endy[i]):max(startx[i],endx[i]));
        ll currocc=en-st+1;
        for(int j=0;j<segments.size();j++)
        {
            currocc-=max(0ll,(segments[j].second-max(st,segments[j].first))+1);
            st=max(st,segments[j].second+1);
        }
        answer+=currocc;
        printf("%lld\n",currocc);
    }
}

Crease Painting CodeChef Solution in JAVA

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";
	
	static void solve()
	{
		int n = ni();
		int[][] pa = new int[n][];
		for(int i = 0;i < n;i++){
			int c = nc();
			int d = ni();
			pa[i] = new int[]{c, d};
		}
		long x = 0, y = 0;
		long[][] co = new long[n][];
		for(int i = 0;i < n;i++){
			int c = pa[i][0], d = pa[i][1];
			if(c == 'U'){
				co[i] = new long[]{x, y, x+1, y+1+d};
				y += d;
			}else if(c == 'D'){
				co[i] = new long[]{x, y-d, x+1, y+1};
				y -= d;
			}else if(c == 'R'){
				co[i] = new long[]{x, y, x+1+d, y+1};
				x += d;
			}else{
				co[i] = new long[]{x-d, y, x+1, y+1};
				x -= d;
			}
		}
		
		long[] shx = new long[2*n];
		for(int i = 0;i < n;i++){
			shx[2*i] = co[i][0];
			shx[2*i+1] = co[i][2];
		}
		Object[] resx = shrink(shx);
		int[] shedx = (int[])resx[0];
		long[] ix = (long[])resx[1];
		
		long[] shy = new long[2*n];
		for(int i = 0;i < n;i++){
			shy[2*i] = co[i][1];
			shy[2*i+1] = co[i][3];
		}
		Object[] resy = shrink(shy);
		int[] shedy = (int[])resy[0];
		long[] iy = (long[])resy[1];
		
		boolean[][] F = new boolean[ix.length][iy.length];
		for(int i = 0;i < n;i++){
			long S = 0;
			for(int j = shedx[2*i];j < shedx[2*i+1];j++){
				for(int k = shedy[2*i];k < shedy[2*i+1];k++){
					if(!F[j][k]){
						F[j][k] = true;
						S += ix[j] * iy[k];
					}
				}
			}
			if(i == 0)S--;
			out.println(S);
		}
	}
	
	public static Object[] shrink(final long[] a)
	{
		int n = a.length;
		Integer[] b = new Integer[n];
		for(int i = 0;i < n;i++)b[i] = i;
		Arrays.sort(b, new Comparator<Integer>(){
			public int compare(Integer x, Integer y){
				return Long.signum(a[x] - a[y]);
			}
		});
		int[] ret = new int[n];
		long[] interval = new long[n];
		int p = 0;
		for(int i = 0;i < n;i++){
			if(i > 0 && a[b[i]] > a[b[i-1]]){
				interval[p] = a[b[i]]-a[b[i-1]];
				p++;
			}
			ret[b[i]] = p;
		}
		
		return new Object[]{ret, Arrays.copyOf(interval, p)};
	}
	
	static char nc()
	{
		try {
			int b;
			while((b = is.read()) != -1 && (b == ' ' || b == '\r' || b == '\n'));
			if(b == -1)return 0;
			return (char)b;
		} catch (IOException e) {
		}
		return 0;
	}
	
	public static void main(String[] args) throws Exception
	{
		long S = System.currentTimeMillis();
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
		long G = System.currentTimeMillis();
		tr(G-S+"ms");
	}
	
	static boolean eof()
	{
		try {
			is.mark(1000);
			int b;
			while((b = is.read()) != -1 && !(b >= 33 && b <= 126));
			is.reset();
			return b == -1;
		} catch (IOException e) {
			return true;
		}
	}
		
	static int ni()
	{
		try {
			int num = 0;
			boolean minus = false;
			while((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));
			if(num == '-'){
				num = 0;
				minus = true;
			}else{
				num -= '0';
			}
			
			while(true){
				int b = is.read();
				if(b >= '0' && b <= '9'){
					num = num * 10 + (b - '0');
				}else{
					return minus ? -num : num;
				}
			}
		} catch (IOException e) {
		}
		return -1;
	}
	
	static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}

Crease Painting CodeChef Solution in GO

package main

import (
	"bufio"
	"bytes"
	"fmt"
	"os"
	"sort"
)

func main() {
	reader := bufio.NewReader(os.Stdin)

	n := readNum(reader)

	S := make([]string, n)

	for i := 0; i < n; i++ {
		S[i] = readString(reader)
	}

	res := solve(n, S)

	var buf bytes.Buffer

	for i := 0; i < n; i++ {
		buf.WriteString(fmt.Sprintf("%d\n", res[i]))
	}

	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, commands []string) []int {
	ans := make([]int, n)

	var x, y int64

	strips := make([]Stripe, n+1)
	strips[0] = Stripe{0, 0, 0, 0}

	for i := 0; i < n; i++ {
		cmd := parseCommand(commands[i])

		if cmd.dir == 'L' {
			strips[i+1] = NewStripe(x-1, y, x-cmd.dis, y)
			x -= cmd.dis
		} else if cmd.dir == 'R' {
			strips[i+1] = NewStripe(x+1, y, x+cmd.dis, y)
			x += cmd.dis
		} else if cmd.dir == 'U' {
			strips[i+1] = NewStripe(x, y+1, x, y+cmd.dis)
			y += cmd.dis
		} else {
			strips[i+1] = NewStripe(x, y-1, x, y-cmd.dis)
			y -= cmd.dis
		}

		var horizontal bool
		if cmd.dir == 'L' || cmd.dir == 'R' {
			horizontal = true
		}
		var ps []Point
		for j := 0; j <= i; j++ {
			ok, intersection := intersect(strips[i+1], strips[j])

			if ok {
				if horizontal {
					ps = append(ps, Point{intersection.x1 - strips[i].x1, false})
					ps = append(ps, Point{intersection.x2 - strips[i].x1 + 1, true})
				} else {
					ps = append(ps, Point{intersection.y1 - strips[i].y1, false})
					ps = append(ps, Point{intersection.y2 - strips[i].y1 + 1, true})
				}
			}
		}

		sort.Sort(Points(ps))

		var covered int
		var last int64
		var painted = cmd.dis

		for j := 0; j < len(ps); j++ {
			p := ps[j]
			if covered > 0 {
				painted -= p.coord - last
			}
			if p.begin {
				covered--
			} else {
				covered++
			}
			last = p.coord
		}
		ans[i] = int(painted)
	}

	return ans
}

type Stripe struct {
	x1, y1, x2, y2 int64
}

func NewStripe(x1, y1, x2, y2 int64) Stripe {
	return Stripe{min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2)}
}

func intersect(a, b Stripe) (bool, Stripe) {
	x1 := max(a.x1, b.x1)
	y1 := max(a.y1, b.y1)
	x2 := min(a.x2, b.x2)
	y2 := min(a.y2, b.y2)
	if x1 > x2 || y1 > y2 {
		return false, Stripe{}
	}
	return true, Stripe{x1, y1, x2, y2}
}

type Point struct {
	coord int64
	begin bool
}

func (this Point) Less(that Point) bool {
	if this.coord != that.coord {
		return this.coord < that.coord
	}
	if this.begin != that.begin {
		return !this.begin
	}
	return false
}

type Points []Point

func (this Points) Len() int {
	return len(this)
}

func (this Points) Less(i, j int) bool {
	return this[i].Less(this[j])
}

func (this Points) Swap(i, j int) {
	this[i], this[j] = this[j], this[i]
}

func min(a, b int64) int64 {
	if a <= b {
		return a
	}
	return b
}

func max(a, b int64) int64 {
	if a >= b {
		return a
	}
	return b
}

type Command struct {
	dir byte
	dis int64
}

func parseCommand(s string) *Command {
	dir := s[0]
	var dis int
	readInt([]byte(s), 2, &dis)
	return &Command{dir, int64(dis)}
}
Crease Painting CodeChef Solution Review:

In our experience, we suggest you solve this Crease Painting 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 Crease Painting CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Crease Painting 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 *