Last active
May 20, 2020 08:30
-
-
Save cypher-nullbyte/73d60c923531130fe4b4c59f007127c3 to your computer and use it in GitHub Desktop.
Vpropel VIT | POD | 19/05/2020 | Chalk sticks | 14
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream> | |
#include<algorithm> | |
#include<numeric> | |
#include<sstream> | |
#include<string> | |
#include<vector> | |
using namespace std; | |
bool sqmaker(std::vector<int> &v) | |
{ | |
int side[4]={0}; | |
int eachS=std::accumulate(v.begin(),v.end(),0); | |
if(eachS%4!=0) return false; | |
else eachS=eachS/4; | |
bool checker[v.size()]={false}; | |
for(int i:v) if(i>eachS) return false; | |
for(int i=0;i<4;i++) | |
{ | |
for(int j=0;j<v.size();j++) | |
if(side[i]+v[j]<=eachS && checker[j]==false) | |
{ | |
side[i]+=v[j]; | |
checker[j]=true; | |
} | |
if(side[i]!=eachS) return false; | |
} | |
return true; | |
} | |
int main() | |
{ | |
int n; | |
std::cin>>n; | |
std::vector<int> v; | |
std::string str; | |
std::cin>>str; | |
std::stringstream s(str); | |
while(s.good()) | |
{ | |
std::string temp; | |
std::getline(s,temp,','); | |
std::stringstream s_temp(temp); | |
int k; | |
s_temp>>k; | |
v.push_back(k); | |
} | |
std::sort(v.begin(),v.end()); | |
std::reverse(v.begin(),v.end()); | |
if(sqmaker(v)) | |
std::cout<<"Yes"; | |
else | |
std::cout<<"No"; | |
} | |
// ### Thank YOu :) | |
// @cs_jawanda | |
// .Chiranjeet Singh Jawanda. | |
// VIT VELLORE |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Scanner; | |
import java.util.Arrays; | |
class solve | |
{ | |
boolean makesquare(int v[]) | |
{ | |
Arrays.sort(v); | |
reverse(v); | |
int side[]=new int[4]; | |
int eachS=0; | |
for(int i:v) eachS+=i; | |
if(eachS%4!=0) return false; | |
else eachS=eachS/4; | |
boolean checker[]=new boolean[v.length]; | |
for(int i:v) if(i>eachS) return false; | |
for(int i=0;i<4;i++) | |
{ | |
for(int j=0;j<v.length;j++) | |
if(side[i]+v[j]<=eachS && checker[j]==false) | |
{ | |
side[i]+=v[j]; | |
checker[j]=true; | |
} | |
if(side[i]!=eachS) return false; | |
} | |
return true; | |
} | |
private void reverse(int[] nums) | |
{ | |
int i = 0, j = nums.length - 1; | |
while (i < j) | |
{ | |
int temp = nums[i]; | |
nums[i] = nums[j]; | |
nums[j] = temp; | |
i++; j--; | |
} | |
} | |
} | |
public class Main | |
{ | |
public static void main(String []args) throws Exception | |
{ | |
Scanner s=new Scanner(System.in); | |
int n=s.nextInt(); | |
String str=s.next(); | |
String []nums=str.split(","); | |
int number[]=new int[n]; | |
for(int i=0;i<n;i++) | |
number[i]=Integer.parseInt(nums[i]); | |
solve obj=new solve(); | |
if(obj.makesquare(number)) | |
System.out.print("Yes"); | |
else | |
System.out.print("No"); | |
} | |
} | |
// ### Thank YOu :) | |
// @cs_jawanda | |
// .Chiranjeet Singh Jawanda. | |
// VIT VELLORE |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def sqMaker(v): | |
eachS=sum(v) | |
if eachS%4!=0: | |
return False; | |
else: | |
eachS=eachS//4 | |
sides=[0,0,0,0] | |
checker=[False]*len(v) | |
for i in range(4): | |
for j in range(len(v)): | |
if (sides[i]+v[j]<=eachS and checker[j]==False): | |
sides[i]+=v[j] | |
checker[j]=True | |
if sides[i]!=eachS: | |
return False | |
return True | |
n=int(input()) | |
v=input().split(',') | |
v=[int(x) for x in v] | |
v.sort(reverse=True) | |
if sqMaker(v): | |
print("Yes") | |
''' | |
// ### Thank YOu :) | |
// @cs_jawanda | |
// .Chiranjeet Singh Jawanda. | |
// VIT VELLORE | |
''' |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//Using DFS | |
import java.util.Scanner; | |
import java.util.Arrays; | |
class solve | |
{ | |
public boolean makesquare(int[] nums) | |
{ | |
if (nums == null || nums.length < 4) return false; | |
int sum = 0; | |
for (int num : nums) sum += num; | |
if (sum % 4 != 0) return false; | |
Arrays.sort(nums); | |
reverse(nums); | |
return dfs(nums, new int[4], 0, sum / 4); | |
} | |
private boolean dfs(int[] nums, int[] sums, int index, int target) | |
{ | |
if (index == nums.length) | |
{ | |
if (sums[0] == target && sums[1] == target && sums[2] == target) | |
{ | |
return true; | |
} | |
return false; | |
} | |
for (int i = 0; i < 4; i++) | |
{ | |
if (sums[i] + nums[index] > target) continue; | |
sums[i] += nums[index]; | |
if (dfs(nums, sums, index + 1, target)) return true; | |
sums[i] -= nums[index]; | |
} | |
return false; | |
} | |
private void reverse(int[] nums) | |
{ | |
int i = 0, j = nums.length - 1; | |
while (i < j) | |
{ | |
int temp = nums[i]; | |
nums[i] = nums[j]; | |
nums[j] = temp; | |
i++; j--; | |
} | |
} | |
} | |
public class Main | |
{ | |
public static void main(String []args) throws Exception | |
{ | |
Scanner s=new Scanner(System.in); | |
int n=s.nextInt(); | |
String str=s.next(); | |
String []nums=str.split(","); | |
int number[]=new int[n]; | |
for(int i=0;i<n;i++) | |
number[i]=Integer.parseInt(nums[i]); | |
solve obj=new solve(); | |
if(obj.makesquare(number)) | |
System.out.print("Yes"); | |
else | |
System.out.print("No"); | |
} | |
} | |
// External source :) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// DP | |
import java.util.Scanner; | |
import javafx.util.Pair; | |
import java.util.HashMap; | |
class solve { | |
HashMap<Pair<Integer, Integer>, Boolean> memo; | |
int[] nums; | |
int possibleSquareSide; | |
solve() { | |
memo = new HashMap<Pair<Integer, Integer>, Boolean>(); | |
} | |
boolean recurse(Integer mask, Integer sidesDone) { | |
int total = 0; | |
int L = this.nums.length; | |
Pair<Integer, Integer> memoKey = new Pair(mask, sidesDone); | |
for(int i = L - 1; i >= 0; i--) { | |
if ((mask&(1 << i)) == 0) { | |
total += this.nums[L - 1 - i]; | |
} | |
} | |
if (total > 0 && total % this.possibleSquareSide == 0) { | |
sidesDone++; | |
} | |
if (sidesDone == 3) { | |
return true; | |
} | |
if (this.memo.containsKey(memoKey)) { | |
return this.memo.get(memoKey); | |
} | |
boolean ans = false; | |
int c = total / this.possibleSquareSide; | |
int rem = this.possibleSquareSide * (c + 1) - total; | |
for(int i = L - 1; i >= 0; i--) { | |
if (this.nums[L - 1 - i] <= rem && (mask&(1 << i)) > 0) { | |
if (this.recurse(mask ^ (1 << i), sidesDone)) { | |
ans = true; | |
break; | |
} | |
} | |
} | |
this.memo.put(memoKey, ans); | |
return ans; | |
} | |
boolean makesquare(int[] nums) { | |
if (nums == null || nums.length == 0) { | |
return false; | |
} | |
int L = nums.length; | |
int perimeter = 0; | |
for(int i = 0; i < L; i++) { | |
perimeter += nums[i]; | |
} | |
int possibleSquareSide = perimeter / 4; | |
if (possibleSquareSide * 4 != perimeter) { | |
return false; | |
} | |
this.nums = nums; | |
this.possibleSquareSide = possibleSquareSide; | |
return this.recurse((1 << L) - 1, 0); | |
} | |
} | |
public class Main | |
{ | |
public static void main(String []args) | |
{ | |
Scanner s=new Scanner(System.in); | |
int n=s.nextInt(); | |
String str=s.next(); | |
String []nums=str.split(","); | |
int number[]=new int[n]; | |
for(int i=0;i<n;i++) | |
number[i]=Integer.parseInt(nums[i]); | |
solve obj=new solve(); | |
if(obj.makesquare(number)) | |
System.out.print("Yes"); | |
else | |
System.out.print("No"); | |
} | |
} | |
// External source :) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//Using DFS(2nd method) | |
import java.util.Scanner; | |
import java.util.Arrays; | |
class solve | |
{ | |
public boolean makesquare(int[] nums) | |
{ | |
int sum=0; | |
for(int num: nums) sum+=num; | |
if(sum%4!=0) return false; | |
Arrays.sort(nums); | |
return dfs(nums,0,sum/4,0,1,new boolean[nums.length]); | |
} | |
private boolean dfs(int []nums,int tempSum, int target,int pos,int groupId,boolean[] visited) | |
{ | |
if(groupId==4) return true; | |
if(target==tempSum) return dfs(nums,0,target,0,groupId+1,visited); | |
if(target<tempSum) return false; | |
for(int i=pos;i<nums.length;i++) | |
{ | |
if(visited[i]) continue; | |
if(i>0 && nums[i]==nums[i-1] && !visited[i-1]) continue; | |
visited[i]=true; | |
if(dfs(nums,tempSum+nums[i],target,i+1,groupId,visited)) return true; | |
visited[i]=false; | |
} | |
return false; | |
} | |
} | |
public class Main | |
{ | |
public static void main(String []args) throws Exception | |
{ | |
Scanner s=new Scanner(System.in); | |
int n=s.nextInt(); | |
String str=s.next(); | |
String []nums=str.split(","); | |
int number[]=new int[n]; | |
for(int i=0;i<n;i++) | |
number[i]=Integer.parseInt(nums[i]); | |
solve obj=new solve(); | |
if(obj.makesquare(number)) | |
System.out.print("Yes"); | |
else | |
System.out.print("No"); | |
} | |
} | |
// External source :) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Chalk sticks | |
Ganesh has n chalk sticks of various lengths. He tries to build a square out of the chalk sticks he have. Given the length of n chalk sticks check whether he can build a square or not. Every chalk stick must be used | |
Example:- | |
Input:- [1,1,2,2,2] | |
Output:-Yes | |
Explanation:-As square of side length 2 can be formed from the given lengths | |
Example:- | |
Input: [3,3,3,3,4] | |
Output: No | |
Explanation: You cannot find a way to form a square with all the matchsticks. | |
Input format:- | |
n-number of chalk sticks | |
Length of n chalk sticks separated by comma | |
Output format:- | |
Yes/No |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
https://leetcode.com/articles/matchsticks-to-square/