Array Construction


Problem Statement :


Professor GukiZ has hobby — constructing different arrays. His best student, Nenad, gave him the following task that he just can't manage to solve:

Construct an n-element array, A, where the sum of all elements is equal to s and the sum of absolute differences between each pair of elements is equal to k. All elements in A must be non-negative integers.
  A0+A1+...+An-1 = s
  ΣΣ |Ai-Aj| = k
If there is more then one such array, you need to find the lexicographically smallest one. In the case no such array A exists, print -1.

Note: An array, A, is considered to be lexicographically smaller than another array, B, if there is an index i such that Ai<Bi and, for any index j<i, Aj=Bj.

Input Format

The first line contains an integer, q, denoting the number of queries.
Each of the q subsequent lines contains three space-separated integers describing the respective values of n (the number of elements in array A), s (the sum of elements in A), and k (the sum of absolute differences between each pair of elements).

Constraints
1 <= q <= 100
1 <= n <= 50
0 <= s <= 200
0 <= k <=2000


Solution :



title-img 


                            Solution in C :

In C++ :





#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

int main(){
	int q;
	cin >> q;
	for(int Q = 0; Q < q; Q++){
		int n, s, k;
		cin >> n >> s >> k;
		int dp[s+1][k+1];
		for(int i = 0; i <= s; i++){
			for(int j = 0; j <= k; j++){
				dp[i][j] = 0;
			}
		}
		dp[0][0] = 1;
		int done = 0;
		for(int c = 1; c <= n; c++){
			int d = c*(n-c);
			for(int i = 0; i + c <= s; i++){
				for(int j = 0; j + d <= k; j++){
					if(dp[i][j] != 0 && dp[i+c][j+d] == 0){
						dp[i+c][j+d] = c;
					}
				}
			}
			if(dp[s][k]){
				int diff[n];
				for(int i = 0; i < n; i++) diff[i] = 0;
				int cs = s;
				int ck = k;
				while(cs > 0 || ck > 0){
					int a = dp[cs][ck];
					int b = a*(n-a);
					diff[n-a]++;
					cs -= a;
					ck -= b;
				}
				int r = 0;
				for(int i = 0; i < n; i++){
					r += diff[i];
					cout << r << " ";
				}
				cout << endl;
				done = 1;
				break;
			}
		}
		if(!done){
			cout << -1 << endl;
		}
	}
}








In Java :





import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        while (q-- > 0){
            List<Integer> solution = solve(in.nextInt(), in.nextInt(), in.nextInt());
            if (solution == null)
                System.out.println(-1);
            else{
                String s = "";
                for (int i : solution)
                    s = i + " " + s;
                System.out.println(s);
            }
        }
    }
    
    private static List<Integer> solve(int n, int s, int k){
        if (k < 0)
            return null;
        else if (n == 1){
            if (k > 0)
                return null;
            else{
                List<Integer> l = new ArrayList<Integer>();
                l.add(s);
                return l;
            }
        }
        else if (k > s * (n - 1) || (s * (n - 1)) % 2 != k % 2)
            return null;
        else{
            for (int x = 0; x <= s / n; x++){
                List<Integer> solution = solve(n - 1, s - n * x, k + n * x - s);
                if (solution != null){
                    for (int i = 0; i < n - 1; i++)
                        solution.set(i, solution.get(i) + x);
                    solution.add(x);
                    return solution;
                }
            }
            return null;
        }
    }
}









In C :






#include <stdio.h>
#include <stdlib.h>

#define maxS 200
#define maxN 50
#define maxK 2000
#define maxNodes (200 + 1) * (2000 + 1)


void printArray(short array[], int size) {
    for (int i = 1; i < size; i++) {
        printf("%hd ", array[i]);
    }
    printf("%hd\n", array[size]);
}


struct Node {
    short init;
    short s, k, val;
    struct Node* prevNode;
};


struct Node** _initDP() {
    struct Node** output = malloc(sizeof(struct Node*) * maxN);
    struct Node* firstDP = malloc(sizeof(struct Node) * maxNodes);
    for (int i = 0; i <= maxS; i++) {
        firstDP[i].init = 1;
        firstDP[i].s = i;
        firstDP[i].k = 0;
        firstDP[i].val = i;
        firstDP[i].prevNode = &firstDP[i];
    }   
    output[0] = firstDP;
    return output;
}


struct Node** createDP() {
    struct Node** output = _initDP();
    struct Node* oldNode;
    int newVal, newS, newK;
    for (int i = 1; i < maxN; i++) {
        struct Node* oldDP = output[i - 1];
        struct Node* newDP = malloc(sizeof(struct Node) * maxNodes);
        short* hasFound =  (short*) calloc(maxNodes, sizeof(short));
        int nodeIdx = 0;
        for (int j = 0; j < maxNodes; j++) {
            oldNode = &(oldDP[j]);
            if (oldNode->init == 0) { break; }
            newVal = oldNode->val;
        
            while (1) {
                newS = oldNode->s + newVal;
                if (newS > maxS) { break; }
                newK = oldNode->k - oldNode->s + (newVal * i);
                if (newK > maxK) { break; }
                int newIdx = newK * (maxS + 1) + newS;
                if (hasFound[newIdx] == 0 || hasFound[newIdx] > newVal + 1) {
                    newDP[nodeIdx].init = 1;
                    newDP[nodeIdx].s = newS;
                    newDP[nodeIdx].k = newK;
                    newDP[nodeIdx].val = newVal;
                    newDP[nodeIdx].prevNode = oldNode;
                    hasFound[newIdx] = newVal + 1;
                    nodeIdx += 1;
                }
                newVal += 1;
            }          
        }
        output[i] = newDP;
        free(hasFound);       
    }
    return output; 
}

void printSolution(int n, int s, int k, struct Node* dp) {
    for (int i = 0; i < maxNodes; i++) {
        if (dp[i].init == 0) { break; }
        //printf("  s = %hd and k = %hd val = %hd\n", dp[i].s, dp[i].k, dp[i].val);
        if (dp[i].s == s && dp[i].k == k) {
            struct Node thisNode = dp[i];
            short* solution = malloc(sizeof(short) * (n + 1));
            int count = n;
            while (count > 0) {
                solution[count] = thisNode.val;
                count -= 1;
                thisNode = *(thisNode.prevNode);
            }
            printArray(solution, n);
            return;
        }
    }
    printf("-1\n");
}


int main() {
    int numQueries, n, s, k;
    struct Node** dp = createDP();
    scanf("%d", &numQueries);
    for (int i = 0; i < numQueries; i++) {
        scanf("%d %d %d", &n, &s, &k);
        printSolution(n, s, k, dp[n - 1]);
    }
    return 0;
}










In Python3 :





cumsum = []
res = []

def mn(ceil, beans):
    return (beans // ceil) * cumsum[ceil] + cumsum[beans % ceil]
def mx(ceil, beans):
    return cumsum[1] * beans

fmemo = set()
def f(ceil, sm, beans):
    if not (mn(ceil, beans) <= sm <= mx(ceil, beans)):
        return False
    if beans == 0 and sm == 0:
        return True
    if (ceil, sm, beans) in fmemo:
        return False
    
    for k in range(1, min(beans, ceil) + 1):
        if f(k, sm - cumsum[k], beans - k):
            res.append(k)
            return True
    fmemo.add((ceil, sm, beans))
    return False
    
        

for _ in range(int(input())):
    n, s, k = map(int, input().split())
    if n == 1:
        if k == 0:
            print(s)
        else:
            print(-1)
        continue
    if s == 0:
        if k == 0:
            print(' '.join(map(str,[0 for _ in range(n)])))
        else:
            print(-1)
        continue
    
    cumsum = [0, 2*n - 2]
    for i in range(1, n):
        cumsum.append(cumsum[-1] + 2*n - 2 - 2*i)
    res = []
    f(n, k + (n - 1) * s, s)
    if res:
        r = [0 for _ in range(n)]
        for num in res:
            for i in range(num):
                r[-1-i] += 1
        print(' '.join(map(str,r)))
    else:
        print(-1)








View More Similar Problems

Minimum Average Waiting Time

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h

View Solution →

Merging Communities

People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w

View Solution →

Components in a graph

There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu

View Solution →

Kundu and Tree

Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that

View Solution →

Super Maximum Cost Queries

Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and

View Solution →

Contacts

We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co

View Solution →