Hello, can any one please tell how to solve This problem
→ Pay attention
Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
11:47:28
Register now »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
11:47:28
Register now »
*has extra registration
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/23/2024 05:47:33 (f1).
Desktop version, switch to mobile version.
Supported by
Well, if n was
<= 20we could've simply ran through every subset of the the array, butn <= 40. Observe that 40 is still pretty close to 20.So what should we do?
We are going to use the Meet in the Middle algorithm (also the name of the task
:)) to solve this problem. That means that we generate all sums for all subsets of the first half and the second half of the array separately. That way time complexity isO (2^(n/2)*n)Now that we have the sums for both halves we want to find in how many ways we can pair two from different halves so that we get x.
We can do that easily by sorting the sum arrays of both halves and use the two pointers method.