WGHTS - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Abhinav Sharma
Testers: Nishank Suresh, Tejas Pandey
Editorialist: Nishank Suresh

DIFFICULTY:

697

PREREQUISITES:

None

PROBLEM:

Chef has 3 weights, weighing x, y, and z. Can he measure a weight of exactly W using these?

EXPLANATION:

There are seven possible positive weights that Chef can measure, namely, \{x, y, z, x+y, x+z, y+z, x+y+z\}. The answer is “Yes” if W equals one of these seven, and “No” otherwise.

TIME COMPLEXITY

\mathcal{O}(1) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    w, a, b, c = map(int, input().split())
    s = {a, b, c, a+b, a+c, b+c, a+b+c}
    print('yes' if w in s else 'no')
2

Hi, I’m new here in code chef and it’s great to find this site to practice my coding skills. I’d like to ask about the WGHTS problem, I’m really curious about my solution because on my test cases it doesn’t have any errors but once I submit there are test cases that are failing, my approach is more on handling dynamic length of an array. Looking forward if anyone can pinpoint any sample test case that would make the code fail, thank you!

using System;

public class Test
{
public static void Main()
{
int t = int.Parse(Console.ReadLine());

	for (int ctr = 0; ctr < t; ctr++) {
	    string ret = "NO";
	    string[] input = Console.ReadLine().Split(' ');
	    bool breakLoop = false;
	    int totalWeight = int.Parse(input[0]);
	    
	    // loop first to check equal data
	    for (int i = 1; i < input.Length; i++) {
	        if (totalWeight == int.Parse(input[i])) {
	            ret = "YES";
	            breakLoop = true;
	            break;
	        }
	    }
	    
	    if (!breakLoop) {
	        for (int incLoop = 1; incLoop < input.Length; incLoop++) {
	            for (int decLoop = input.Length - 1; decLoop >= 1; decLoop--) {
	                if (incLoop != decLoop) {
	                    if (totalWeight == 
	                        int.Parse(input[decLoop]) + 
	                        int.Parse(input[incLoop])) {
	                            ret = "YES";
	                            breakLoop = true;
	                            break;
	                    }
	                }
	            
	            }
	        
	            if (breakLoop){
	                break;
	            }
	        }
	    }
	    
	    
	    Console.WriteLine(ret);
	}
}

}

3

I’m not really familiar with C# syntax, but it looks to me that your code checks for two possibilities:

  • Whether the target weight is one of the given ones
  • Whether the target weight is the sum of two of the given ones

You aren’t considering the case when the target can be the sum of all three, for example the case

1
6 1 2 3
4

Ahhh alright, you are correct. I’m just considering if total weight is equal to one of the given ones and adding just two of them. I didn’t consider adding more than 2 elements. Thank you for the clarification, I really overlooked this one. I appreciate it! :slightly_smiling_face: