Skip to content

Instantly share code, notes, and snippets.

@cypher-nullbyte
Last active May 20, 2020 08:30
Show Gist options
  • Save cypher-nullbyte/73d60c923531130fe4b4c59f007127c3 to your computer and use it in GitHub Desktop.
Save cypher-nullbyte/73d60c923531130fe4b4c59f007127c3 to your computer and use it in GitHub Desktop.
Vpropel VIT | POD | 19/05/2020 | Chalk sticks | 14
#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
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
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
'''
//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 :)
// 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 :)
//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 :)
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
@cypher-nullbyte
Copy link
Author

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment