SPOJ.com - Problem ARRTWIST

ARRTWIST - TWISTED ARRAY

There are two integer arrays A and B. The length of array A is n and length of array B is k. Array A = [ a₁, a₂ ... a_i ... a_n ] and B = [ b₁, b₂ ... b_j ... b_k ] where 1 ≤ a_i ≤ k and 1 ≤ b_j ≤ n and 1 ≤ i ≤ n and 1 ≤ j ≤ k and 1 ≤ k ≤ n ≤ 10⁷. If there exists a subarray of A which has the same sum as some subarray of B then B and A are said to be twisted arrays.

More mathematically, if there exists p, q, r and s such that sum(A, p, q) = sum(B, r, s), where 1 ≤ p ≤ q ≤ n and 1 ≤ r ≤ s ≤ k and sum(A, p, q) = a_p + a_p+1 + a_p+2... + a_q-1 + a_q and sum(B, r, s) = b_r + b_r+1 + b_r+2... + b_s-1 + b_s then the two arrays A and B are said to be twisted arrays.

Input

Input contains n + k + 1 lines. The first line has values for n and k separated by space.

Then next n lines specify the elements of array A. The next k lines specify the elements of array B.

Output

One line containing Yes if the arrays are twisted or No otherwise (Note: Yes and No are case sensitive.)

Example

Input:

4 3
1
2
3
1
2
1
1 Output: Yes

Explanation:

Here A = [1, 2, 3, 1] and B = [2, 1, 1]. Clearly a₁ + a₂ = b₁ + b₂, and so A and B are twisted

Submit solution!

Added by:	Amitayush Thakur
Date:	2018-07-13
Time limit:	0.5s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All
Resource:	Own

hide comments



2021-07-02 10:50:02 where can i get help for solution to this problem? Please help me with proof. [Amitayush] Replied to your query for proof in the discussion forum: http://discuss.spoj.com/t/problem-arrtwist/42733 Last edit: 2021-07-03 06:50:08
2020-01-30 19:15:48 Amitayush Thakur Anyone posting answers here, I will make sure their submissions and all submissions after their comment are disqualified. Their comments will be edited or removed completely. So don't post answer or any hints here. You solved the problem keep it to yourself (it is no rocket science) and let others solve it too. Solving a problem is not a big deal, knowing/ learning something new is important. If you feel you learnt something new solving this problem then enjoy or else move on don't spoil it for curious and enthusiasts who enjoy learning. I check solutions and comments regularly. So take this comment seriously. I have already disqualified many solvers who posted answers here. Don't do the same mistake. Last edit: 2020-01-30 19:48:24
2018-12-27 21:40:36 My personal opinion is that problems like this are OK, but this one is pretty blatantly given away by ([amit9oct] Reduced the limits :P) combined with the oh so subtle ([amit9oct] Removed the not so subtle hint :P). [amit9oct]: Thanks for your feedback. I have relaxed the constraint and removed the NOT so subtle hint :) RE: Wait, but you can't just remove the constraints from the problem statement >.< RE(amit9oct): Yes I can, because any file with 10^8 numbers is too big, and judge doesn't accept. In a way, the problem constraint was always this :P , it never had a test case with 10^8 numbers. RE: Oh, I missed the n<=10^7 added to a different part of the statement. But I have to say I don't like how you 'mislead' solvers - sure, when n<=10^7, it is also true that n<=10^8, but then everyone could say 'n<=10^8 in my input files' and we would have no idea whether in reality n<10 or n<1000 or n<100000. If input files have some constraints, tell us those constraints. RE(amit9oct): I agree, it might have been little misleading but the ideal solution would have even worked for 10^8, I actually wanted to subtly give some hints by making the constraint as 10^8. But now I am considering to relax the time limit too. Last edit: 2018-12-31 17:35:22
2018-11-17 09:51:44 1 <= ai <= k and 1 <= bj <= n this is important
2018-10-01 15:36:19 Made a guess based on AC runtimes and passed. (@amit9oct Reply: removed the spoiler). This means eg. arrays A = [1] and B = [2] are not twisted, but either no such testcase exists or the statement is wrong. (@amit9oct Reply: Please read the question carefully A = [1] and B = [2] doesn't even qualify as a valid input because len(A) = 1 so B cannot have any number greater than 1 hence B cannot contain 2) Please move to Basics as this doesn't even qualify as Riddle. (@amit9oct Reply: try proving mathematically what you just said, even though your guess might be right. I am sure you can't. It needs a good amount of combinatorial mathematics with mathematical induction. It is not some basic maths that you can do it. So NOT moving) (amit9oct Reply: I had to disqualify all the answer which were submitted after your comment because you literally posted the answer here, there have been people who gave multiple attempts and then understood that what is mathematically possible and solved this. It is not good giving away answers just because you got it. There are people who did multiple submissions for this question and some of them had really enjoyed this problem (including some of the highly rated users). You can't give away the answer just because you don't like mathematical problems or this specific problem.) [NG]: This is a place for programming contests, not mathematical proofs; it is psetters job to design the problem and testcases so that automated judge accepts only the correct solutions. Obviously, testcases here are worthless in that respect, and worse still, you appear to indicate that the gibberish of a statement doesn't even allow for designing ones that would reject my "solution". ([amit9oct Reply:] This is really hilarious how can your correct solution get rejected even if you guessed it, or for that matter some oracle told you the solution. I can only agree that I cannot stop people from guessing, but I don't think competitive coders code for guessing and solving problems. I believe they love solving problems and are curious about learning something new.) Bottomline, a problem that allows highly probable AC by taking a guess ([amit9oct Reply:] Removed spoiler) does not belong in Classical. ([amit9oct Reply:]Also I don't think it is highly probable because people don't think in a linear way, they try to generate examples and counter examples. Most of the solutions I have seen people tried multiple approaches and then landed on the correct answer) [amit9oct Reply:] I don't agree with you. Even though this is platform to host programming contests but I think a good programmer should be aware of what can be solved and what can't. We classify problems as NP, NPC, NP hard and some of them even unsolvable. It is completely pragmatic to have some mathematical / theoretical knowledge. This question doesn't simply tests your programming skills but also sees if you can think and reason why your intuition can be correct. In my opinion most of the people who do competitive coding don't do it for guessing and solving question, they do it because they love doing it. They love to learn something new and are curious. If this question makes you think and curious then bang!! You enjoyed it!!. Otherwise just solve it and move on. Don't spoil the experience for others. Bottomline is I will NOT move this problem, because people have already solved this problem. I have seen their solutions, many of them got WA after trying multiple approaches. That means they are also understanding what this problem is about. I am happy even if someone ultimately gets to the solution without knowing the proof it is totally worth after multiple tries. Last edit: 2018-10-26 20:38:37
2018-07-14 15:14:23 why NZEC for python? help!