Array TransformProblem code: ARRAYTRM |
Given n numbers, you can perform the following operation any number of times : Choose any subset of the numbers, none of which are 0. Decrement the numbers in the subset by 1, and increment the numbers not in the subset by K.
Is it possible to perform operations such that all numbers except one of them become 0 ?
Input :
The first line contains the number of test cases T. 2*T lines follow, 2 for each case. The first line of a test case contains the numbers n and K. The next line contains n numbers, a_1...a_n.
Output :
Output T lines, one corresponding to each test case. For a test case, output "YES" if there is a sequence of operations as described, and "NO" otherwise.
Sample Input : 3 2 1 10 10 3 2 1 2 2 3 2 1 2 3
Sample Output : YES YES NO
Constraints : 1 <= T <= 1000 2 <= n <= 100 1 <= K <= 10 0 <= a_i <= 1000
| Date: | 2010-04-09 |
| Time limit: | 2s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
HELP
Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:
- Accepted
Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark. - Time Limit Exceeded
Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach. - Wrong Answer
Your program compiled and ran succesfully but the output did not match the expected output. - Runtime Error
Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section. - Compilation Error
Your code was unable to compile. When you see this icon, click on it for more information.
If you are still having problems, see a sample solution here.
can anyone put some more
can anyone put some more sample input and output cases of this problem
what should be the out output
what should be the out output for following test case?
3 2
0 0 1
It is "YES" initially. But if we do a single operation, it will become "NO". So is "YES" possible with initial set without doing operation?
Thanks,
Saurabh
"Any number of times"
"Any number of times" includes 0 times.
@admin, can you please give
@admin, can you please give me a test case where solution is failing. I think my logic is correct.
An extra test case would make
An extra test case would make things too easy. Your logic is not correct; check it thoroughly and you should be able to come up with a test case yourself.
@Stephen, got it. Just one
@Stephen, got it. Just one silly mistake. Thanks.
@admin can you tell me a test
@admin
can you tell me a test case where my solution is falling i think my logic is correct
12 32 1 That should be 'YES';
12 32 1That should be 'YES'; choose everything as the subset and you immediately are done.
i didnt considered this case
i didnt considered this case ...
when k can be greater than n...
thanks Stephen...
wasn't reading the problem
wasn't reading the problem statement correctly...
but still stuck at same point.....
can anyone look at it....
http://www.codechef.com/viewsolution/365982
I'm afraid you're still
I'm afraid you're still giving the wrong answer most of the time. For example:
13 1
2 3 4
Correct answer is YES. There are other types of input which you are also getting wrong, but since coming up with these test cases is half the work of solving the problem, I won't be giving you any more ;)
thans Stephen I think I am
thans Stephen
I think I am unable to come up with test cases that is why I am unable to solve many problems of the coechef despite kowing on algorithm....
i will try it...
@stephen all the test cases
@stephen all the test cases you have told above , My code works for all of them ? but I am still getting wrong answer :( Can you please throw some light :-/
@admin how could this case 13
@admin
how could this case
13 1
2 3 4
be yes...?
Choose the second and third
Choose the second and third numbers:
3 2 3
Choose the first and third numbers three times:
0 5 0
Somebody Plz look at this
Somebody Plz look at this solution also. ...
http://www.codechef.com/viewsolution/402392
Sorry, plz look this soln.
Sorry, plz look this soln. and ignore the previous post ...
http://www.codechef.com/viewsolution/402406
@Stephen: My solution works
@Stephen:
My solution works for all test cases including those in the comments but while submitting I get a run time error.
Faqs says that it may be due to memory overhead.
But I have only used dynamic memory allocations as required by the values of n in the problem statement.
The code works completely fine on my machine
So what should be the problem ?!
Should I try long static arrays instead of small Dynamic arrays ?!
That's only one possibility
That's only one possibility for runtime error.. another one it mentions is that a main function must always return 0.
OK I got my error it was
guys it will really kind of
guys it will really kind of you if you could take a look at http://discuss.codechef.com/showthread.php?p=3667#post3667 , why am i getting wrong answer even though I have a mathematical proof of my logic , it works for all above test cases including those mentioned in comments
can some one please check my
can some one please check my submission ....?http://www.codechef.com/viewsolution/427187.... i did the same thing which abhinav atul mentioned in the post http://discuss.codechef.com/showthread.php?p=3667#post3667....please help me.. :)
can some one please check my
can some one please check my submission ....? http://www.codechef.com/viewsolution/427187 .... i did the same thing which abhinav atul mentioned in the post http://discuss.codechef.com/showthread.php?p=3667#post3667....please help me.. :)
@admin: Can you give me a
@admin:
Can you give me a test case where my solution is giving the wrong answer?
is this logic correct that if
is this logic correct that if i can find any subset of n-1 numbers such that all get converted into a number x after some operations then the ans is yes
pls respond as soon as possible
thank you
alas got AC
alas got AC
@admin I've tried all the
@admin
I've tried all the test cases u said above and the answer is right. Still its saying 'wrong answer'... can u tell me a test case where my solution fails?
my id is 428976
my id is 428976
@parigha i guess u hav
@parigha
i guess u hav followed the approach given by abhinav which is wrong
if u hav then respond so that i can tell the mistake in that approach
@garima i haven't fully used
@garima
i haven't fully used abhinav's algorithm... just till d mathematical part (i.e. till finding the remainders)... is something wrong till there?
@parigha there is a mistake
@parigha
there is a mistake in it
as given in the forum m%(k+1)=a_i%(k+1)
from here we conclude that n-1 numbers must hav same remainder and the left one can hav same or different rem
so we conclude there should be 1 or 2 distinct remainders
if there are 1 or 2 distinct rem we say yes but it has a mistake, consider only n-2 numbres out of n can be made 0 at at time and all of them giv same rem say x the rest of the two numbers can giv x or something else as rem if they also giv x
we get 1 distinct rem and we output yes which is wrong
@Parigha I'm not sure what
@Parigha
I'm not sure what garima is talking about, but your issue occurs when the first three elements of c are all the same.
are a_i s always
are a_i s always positive
initiallly as well as during the transformation
The initial constraints are
The initial constraints are mentioned in the problem. It doesn't say anywhere they can't become negative at any point.
I am facing some trouble
I am facing some trouble understanding the problem.. Can someone explain why the answer is NO for the following sample case:
3 2
1 2 3
Sorry.. I did not read the
Sorry.. I did not read the problem statement carefully.. Ignore my above comment!
could anyone help me
could anyone help me pleasehttp://www.codechef.com/viewsolution/437720
@admin what will be answer
@admin
what will be answer for these sequences:
1. 3 4 6 9 11 12 15
2. 4 6 9 11 14 17
3. 4 6 9 11 12 15
4. 3 6 9 11 12 15
5. 3 6 9 10 11 15
Pls. give me the answers..
In which language I should
In which language I should submit the program:
C(gcc-4,3,2), C99 strict(gcc 4.3.2), C++(gcc-4.0.0-8) or C++(gcc-4.3.2)
I dont know why it is giving answer to both of my solutions:
1. http://www.codechef.com/viewsolution/438058
2. http://www.codechef.com/viewsolution/438041
To admin @above comment.. it
To admin
@above comment..
it is giving wrong answer after submitting the solution
@Mayank : At codechef you
@Mayank : At codechef you dont have to print messages to ask for input in your soln . You should assume that Judge knows when to input what values and in what format.
to admin, could you please
to admin,
could you please tell me at what case my solution is giving a wrong answer, as it is running fine on m machine
http://www.codechef.com/viewsolution/438389
also should an input all zeroes generate yes or no?
@Admin Getting a wrong answer
@Admin
Getting a wrong answer for this solution http://www.codechef.com/viewsolution/438432
All the test cases are working fine.
to admin, could you please
to admin,
could you please tell me at what case my solution is giving a wrong answer, as it is running fine on my machine
http://www.codechef.com/viewsolution/438478
@Manmohar: Thanks for the
@Manmohar: Thanks for the suggestion. So after removing that line will my code work correctly??
@admin Please tell why my
@admin
Please tell why my code is showing wrong output? even when all test cases are working.
http://www.codechef.com/viewsolution/438495
@admin please tell why my
@admin
please tell why my solution failing? I have consider all test cases including in comments section.
@admin what's wrong in my
@admin
what's wrong in my code?
why am I getting Wrong Answer Error?
http://www.codechef.com/viewsolution/443565
@admin what is the answer of
@admin
what is the answer of this?
2 0
0 0
@admin- could you tell me for
@admin- could you tell me for what input my code fails?
@Rahul: K>=1
@Rahul: K>=1
@Sami: For the example you
@Sami: For the example you provided, the algorithm gives correct answer..
Please can you provide some test case..
Where's my code failing,
Where's my code failing, please somebody help...
@Admin: I have two doubts:
@Admin: I have two doubts: Very important I think should be added to problem statement to make it clearer.
1. exactly one should be left not equal to zero or all may become zero. (i guess exactly one)
2. A subset as per definition can have all elements and also no element of set, is this the same for this problem also?
@admin : please reply admin.
@admin : please reply admin.
please reply...
please reply...
@Stephen Merriman :Please
@Stephen Merriman :Please reply......
I have two doubts: Very important I think should be added to problem statement to make it clearer.
1. exactly one should be left not equal to zero or all may become zero. (i guess exactly one)
2. A subset as per definition can have all elements and also no element of set, is this the same for this problem also?
@Stephen Merriman :Please
@Stephen Merriman :Please reply......
I have two doubts: Very important I think should be added to problem statement to make it clearer.
1. exactly one should be left not equal to zero or all may become zero. (i guess exactly one)
2. A subset as per definition can have all elements and also no element of set, is this the same for this problem also?
Ohh it was so easy i cant
Ohh it was so easy i cant believe... :P
and answers that i got to my above comment..
1. all can be zero also
2. it can have all elements and also no need of no element case in subset...
can som1 please mail me the
I am getting wrong answer in
hi
i am getting wrong answer
admin plz check my soln
wrong testcases!!!!!
please expalin how to get
can we choose a single number
I am still not getting why
Can you add some more test
Everyone is using the
Can anyone please answer my