Corruption in Freedonia CodeChef Solution

Problem -Corruption in Freedonia 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.
<<Previous CodeChef Problem Next Codechef Problem>>

Corruption in Freedonia CodeChef Solution in C++14

#include<bits/stdc++.h>
#define pb push_back
#define ll long long int

using namespace std;

const int mxSize = 1e6 +5;
vector<int>g[mxSize];
int vis[mxSize];
int a[mxSize],b[mxSize];

void dfs(int node){
    vis[node] = 1;
    bool check = false, check2 = false;
    int c = 0;
    for (auto it : g[node]){
        if (!vis[it] ) {
            check = true;
            dfs(it);
            c++;
            
            a[node] += a[it];
            b[node] += b[it];
            if(b[node] < 0)check2 = true;

        }
    }
    if(!check){
        a[node] = 1;
    }
    if((!check2) && (c > 1)){
        b[node] = -1;
    }
    
}
void solve(){
    int n ;
     cin >> n;

    for (int i = 1; i < n; i++) {
        int u,v; cin >> u >> v;
        g[u].pb(v); g[v].pb(u);
        vis[i] = 0; 
        a[i] = 0;
        b[i] = 0;
    }
    vis[0]=0;
    vis[n] = 0;
    a[n] = 0;
    b[n] = 0;
    dfs(1);
    int ans = a[1] + b[1];
    cout<<ans<<endl;

   
    

}

int main()
{
        solve();
        return 0;
}

Corruption in Freedonia CodeChef Solution in PYTH 3

from sys import stdin,stdout
input=stdin.readline
n=int(input())
a=[[] for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    a[u-1].append(v-1)
    a[v-1].append(u-1)
b=[0]*n
vis=[0]*n
st=[(0,0)]
vis[0]=1
pa=[0]*n
while st:
    x,y=st.pop()
    b[x]=y
    for i in a[x]:
        if vis[i]==0:
            pa[i]=x
            vis[i]=1
            if x==0:
                st.append((i,y+len(a[x])-1))
            else:
                st.append((i,y+len(a[x])-2))
c=[]
for i in range(1,n):
    if len(a[i])==1:
        c.append((b[i],i))
c.sort()
ans=0
while c:
    x,y=c.pop()
    m=y
    p=0
    while y!=0 and pa[y]!=-1:
        y=pa[y]
        if pa[y]==-1:
            break
        if y!=0:
            p+=(len(a[y])-2)
        else:
            p+=(len(a[y])-1)
    if p>=1:
        p=0
        while m!=0 and pa[m]!=-1:
            x=m
            if pa[m]==-1:
                break
            m=pa[m]
            pa[x]=-1
            if m!=0:
                p+=(len(a[m])-2)
            else:
                p+=(len(a[m])-1)
        if y==0:
            pa[0]=-1
for i in range(n):
    if pa[i]!=-1:
        st=[i]
        pa[i]=-1
        while st:
            x=st.pop()
            for j in a[x]:
                if pa[j]!=-1:
                    pa[j]=-1
                    st.append(j)
        ans+=1
print(ans)

Corruption in Freedonia CodeChef Solution in C

//tree DP
//ABC036-D
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
#define inf 1072114514
#define llinf 4154118101919364364
#define mod 1000000007
#define pi 3.1415926535897932384

int max(int a,int b){if(a>b){return a;}return b;}
int min(int a,int b){if(a<b){return a;}return b;}
int zt(int a,int b){return max(a,b)-min(a,b);}
long long llmax(long long a,long long b){if(a>b){return a;}return b;}
long long llmin(long long a,long long b){if(a<b){return a;}return b;}
long long llzt(long long a,long long b){return llmax(a,b)-llmin(a,b);}
long long llround(long long a,long long b){if((a%b)*2 >= b){return (a/b)+1;}return a/b;}
long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;}
long long llgcd(long long a,long long b){long long c;while(b!=0){c=a%b;a=b;b=c;}return a;}
long long lllcm(long long a,long long b){long long c=llgcd(a,b);a/=c;return a*b;}
long long llnCr(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
long long llnHr(long long a,long long b){return llnCr(a+b-1,b);}
long long llfact(long long a){long long i,r=1;for(i=1;i<=a;i++){r*=i;}return r;}
long long llpow(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}
long long lldsum(long long x){long long r=0;while(x){r+=(x%10);x/=10;}return r;}
long long lldsumb(long long x,long long b){long long r=0;while(x){r+=(x%b);x/=b;}return r;}
long long llsankaku(long long x){return ((1+x)*x)/2;}

typedef struct{
int val;
int node;
}sd;

int sdsortfnc(const void *a,const void *b){
if(((sd*)a)->val > ((sd*)b)->val){return -1;}
if(((sd*)a)->val < ((sd*)b)->val){return 1;}
return 0;
}

typedef struct{
    long long st;
    long long fi;
    long long kr;
}rs;

typedef struct{
    long long st;
    long long kz;
}mkj;

int sortfnc(const void *a,const void *b){
if(((rs*)a)->st == ((rs*)b)->st){return 0;}
if(((rs*)a)->st < ((rs*)b)->st){return -1;}
return 1;
}

void makemkj(rs g[],mkj x[],long long n){
    long long i,ms=0,nst=g[0].st;
    for(i=1;i<n;i++){
        if(g[i].st!=g[i-1].st){
            x[nst].kz=i-ms;
            x[nst].st=ms;
            nst=g[i].st;ms=i;
        }
    }
    x[nst].kz=n-ms;
    x[nst].st=ms;
}

long long dist[2097152],par[2097152];
void dfs(long long t,long long l,long long bp,rs g[],mkj x[]){
  long long i;
  if(dist[t]<=l){return;}
  dist[t]=l;
  par[t]=bp;
  for(i=x[t].st;i<x[t].st+x[t].kz;i++){
    dfs(g[i].fi,l+1,t,g,x);
  }
}

int main(void){
    long long i,j,n,m,k,a,b,c,h,w,r=0,l,t;
    long long res=0;
    long long dp[2097152][2]={0};
    long long wa,wb;
    rs g[2097152];
    mkj x[2097152];
    sd dat[2097152];
    scanf("%lld",&n);
    for(i=0;i<(n-1);i++){
      scanf("%lld%lld",&a,&b);
      g[2*i].st=a;
      g[2*i].fi=b;
      g[2*i].kr=1;
      g[2*i+1].st=b;
      g[2*i+1].fi=a;
      g[2*i+1].kr=1;
    }
    qsort(g,2*(n-1),sizeof(g[0]),sortfnc);
    makemkj(g,x,2*(n-1));
    for(i=0;i<=n;i++){
      dist[i]=inf;
    }
    dfs(1,0,-1,g,x);
    for(i=0;i<n;i++){
      dat[i].node=i+1;
      dat[i].val=dist[i+1];
    }
    qsort(dat,n,sizeof(dat[0]),sdsortfnc);
    for(i=0;i<n;i++){
      w=dat[i].node;
      wa=1;
      for(j=x[w].st;j<x[w].st+x[w].kz;j++){
        if(par[w]==g[j].fi){continue;}
        wa=wa+dp[g[j].fi][0]-1;
      }
      dp[w][0]=wa;
      if(x[w].kz==1 && g[x[w].st].fi==par[w]){dp[w][1]=0;}
      else{
        wa=0;h=-llinf;
        wb=0;t=0;
        for(j=x[w].st;j<x[w].st+x[w].kz;j++){
          if(par[w]==g[j].fi){continue;}
          wa+=dp[g[j].fi][0];
          h=llmax(dp[g[j].fi][1]-dp[g[j].fi][0],h);
          if(dp[g[j].fi][0]<=dp[g[j].fi][1]){t=1;}
          wb+=llmax(dp[g[j].fi][0],dp[g[j].fi][1]);
        }
        if(t==1){dp[w][1]=wb;}
        else{dp[w][1]=wa+h;}
      }
      //printf("%lld %lld %lld\n",w,dp[w][0],dp[w][1]);
    }
    printf("%lld\n",llmax(dp[1][0],dp[1][1]));
    return 0;
}

Corruption in Freedonia CodeChef Solution in JAVA

import java.util.*;

class Test
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        ArrayList<Integer>[] array = (ArrayList<Integer>[])new ArrayList[n+1];
        for(int i=1; i<=n; i++)
            array[i] = new ArrayList<Integer>();
        for(int i=0; i<n-1; i++)
        {
            int a = scan.nextInt();
            int b = scan.nextInt();
            array[a].add(b);
            array[b].add(a);
        }
        int dp[] = new int[n+1];

        dfs(array, new boolean[n+1], 1, dp);
        System.out.println(Math.max(dp[1], 1));
    }

    public static void dfs(ArrayList<Integer>[] array, boolean[] visited, int curr, int[] dp)
    {
        if(visited[curr] == false)
        {
            visited[curr] = true;
            for(int u : array[curr])
            {
                dfs(array, visited, u, dp);
            }
            visited[curr] = false;
        }
        int s1 = 0;
        int count = 0;
        if(visited[curr] == false)
        {
            for(int u : array[curr])
            {
                if(visited[u] == false)
                    s1 = s1 + Math.max(dp[u], 1);
            }
        }

        if(visited[curr] == false)
        {
            for(int u : array[curr])
            {
                int s2 = 0;
                if(visited[u] == false)
                    s2 = s1 - Math.max(dp[u], 1) + dp[u];
                count = Math.max(count, s2);
            }
        }
        dp[curr] = count;
        return;
    }
}

Corruption in Freedonia CodeChef Solution in GO

package main

import (
	"bufio"
	"fmt"
	"os"
)

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] != ' ' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readNum(scanner *bufio.Scanner) (a int) {
	scanner.Scan()
	readInt(scanner.Bytes(), 0, &a)
	return
}

func readTwoNums(scanner *bufio.Scanner) (a int, b int) {
	res := readNNums(scanner, 2)
	a, b = res[0], res[1]
	return
}

func readNNums(scanner *bufio.Scanner, n int) []int {
	res := make([]int, n)
	x := 0
	scanner.Scan()
	for i := 0; i < n; i++ {
		for x < len(scanner.Bytes()) && scanner.Bytes()[x] == ' ' {
			x++
		}
		x = readInt(scanner.Bytes(), x, &res[i])
	}
	return res
}

func fillNNums(scanner *bufio.Scanner, n int, res []int) {
	x := 0
	scanner.Scan()
	for i := 0; i < n; i++ {
		for x < len(scanner.Bytes()) && scanner.Bytes()[x] == ' ' {
			x++
		}
		x = readInt(scanner.Bytes(), x, &res[i])
	}
}

func readUint64(bytes []byte, from int, val *uint64) int {
	i := from

	var tmp uint64
	for i < len(bytes) && bytes[i] != ' ' {
		tmp = tmp*10 + uint64(bytes[i]-'0')
		i++
	}
	*val = tmp

	return i
}

func readInt64(bytes []byte, from int, val *int64) int {
	i := from
	var tmp int64
	for i < len(bytes) && bytes[i] != ' ' {
		tmp = tmp*10 + int64(bytes[i]-'0')
		i++
	}
	*val = tmp
	return i
}

func readNInt64Nums(scanner *bufio.Scanner, n int) []int64 {
	res := make([]int64, n)
	x := -1
	scanner.Scan()
	for i := 0; i < n; i++ {
		x = readInt64(scanner.Bytes(), x+1, &res[i])
	}
	return res
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)

	N := readNum(scanner)

	edges := make([][]int, N-1)

	for i := 0; i < N-1; i++ {
		edges[i] = readNNums(scanner, 2)
	}

	fmt.Println(solve(N, edges))
}

func solve(N int, edges [][]int) int {
	dp := make([]int, N)

	outs := make([][]int, N)

	for i := 0; i < N; i++ {
		outs[i] = make([]int, 0, 10)
	}

	for _, edge := range edges {
		u, v := edge[0]-1, edge[1]-1
		outs[u] = append(outs[u], v)
		outs[v] = append(outs[v], u)
	}

	var dfs func(p, u int)

	dfs = func(p, u int) {

		for _, v := range outs[u] {
			if p == v {
				continue
			}
			dfs(u, v)
		}
		x := -1

		for _, v := range outs[u] {
			if p == v {
				continue
			}
			if x == -1 || dp[v] > dp[x] {
				x = v
			}
		}

		for _, v := range outs[u] {
			if p == v {
				continue
			}
			if x != v {
				dp[u] += max(dp[v], 1)
			} else {
				dp[u] += dp[v]
			}
		}
	}
	dfs(-1, 0)

	return max(dp[0], 1)
}

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

func solve1(N int, edges [][]int) int {

	if N <= 2 {
		return 1
	}

	degree := make([]int, N)

	for _, edge := range edges {
		u, v := edge[0]-1, edge[1]-1
		degree[u]++
		degree[v]++
	}

	outs := make([][]int, N)

	for i := 0; i < N; i++ {
		outs[i] = make([]int, 0, degree[i])
	}

	for _, edge := range edges {
		u, v := edge[0]-1, edge[1]-1
		outs[u] = append(outs[u], v)
		outs[v] = append(outs[v], u)
	}

	var dfs func(p, u int) int
	var total int
	var pp int
	dfs = func(p, u int) int {
		leaf := true
		r := 1
		for _, v := range outs[u] {
			if p == v {
				continue
			}
			leaf = false
			x := dfs(u, v)
			if x > 1 {
				r = 2
			}
		}

		if leaf {
			total++
		} else if r == 1 {
			if u == 0 && degree[u] > 1 {
				pp++
			} else if degree[u] > 2 {
				pp++
			}
		}

		if r > 1 {
			return r
		}

		return degree[u] - 1
	}

	dfs(-1, 0)

	return total - pp
}
Corruption in Freedonia CodeChef Solution Review:

In our experience, we suggest you solve this Corruption in Freedonia 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 Corruption in FreedoniaCodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Corruption in Freedonia 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 *