As promised, here are some (nested) hints for Codeforces Round #682 (Div. 2).

1438A - Специфичные вкусы Андре

**Hint 1**

**Hint 1**

**Hint 1**

**Hint 1**

I wasn't able to solve E and F. If you did, you may want to add your hints in the comments.

# | User | Rating |
---|---|---|

1 | tourist | 4009 |

2 | jiangly | 3839 |

3 | Radewoosh | 3646 |

4 | jqdai0815 | 3620 |

4 | Benq | 3620 |

6 | orzdevinwang | 3612 |

7 | Geothermal | 3569 |

8 | ecnerwala | 3494 |

9 | Um_nik | 3396 |

10 | gamegame | 3386 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 163 |

1 | maomao90 | 163 |

3 | -is-this-fft- | 162 |

4 | atcoder_official | 158 |

4 | cry | 158 |

6 | awoo | 157 |

7 | nor | 155 |

7 | adamant | 155 |

9 | TheScrasse | 153 |

10 | maroonrk | 152 |

Unofficial hints for Codeforces Round #682 (Div. 2) (A — D)

Revision en3, by TheScrasse, 2020-11-13 20:25:47

As promised, here are some (nested) hints for Codeforces Round #682 (Div. 2).

1438A - Специфичные вкусы Андре

Solve some small tests on paper.

Can you make the sum of each subarray equal to its length?

Suppose that the answer is `NO`

. Which property should hold for the array $$$a$$$?

What happens if $$$l_1 = r_1$$$?

The answer is `YES`

if there is a pair of equal elements in the array $$$b$$$. What happens if there are no equal elements?

Look at the binary representation of the sum of each subarray. Are there equal binary representations?

Solve on paper

```
3 3
1 1 1
1 1 1
1 1 1
```

Now solve

```
3 3
2 1 1
1 1 2
2 1 2
```

Do a chess coloring on the grid. Can you make all differences odd?

How does the xor of all the array change after every operation?

The xor remains constant. Let it be $$$x$$$. If you make all elements equal, what's the xor of the resulting array?

If $$$n$$$ is even, $$$x = 0$$$. So the answer is `NO`

if the starting xor is not $$$0$$$.

If $$$n$$$ is odd, you can set $$$a[i] = x$$$ for each $$$i$$$, and their xor is $$$x$$$. The answer is always `YES`

.

In both cases, if the answer is `YES`

, you can solve the problem by making each $$$a[i]$$$ equal to $$$x$$$. Can you make $$$a[1] = x$$$ first?

Now you want to "spread" $$$x$$$ in all the array. Are there three indices such that $$$a[i] \oplus a[j] \oplus a[k] = x$$$?

I wasn't able to solve E and F. If you did, you may want to add your hints in the comments.

Revisions

Rev. | Lang. | By | When | Δ | Comment | |
---|---|---|---|---|---|---|

en6 | TheScrasse | 2020-11-13 20:59:08 | 17 | Tiny change: '\nThe xor remains c' -> '\nThe xor of all the array remains c' | ||

en5 | TheScrasse | 2020-11-13 20:46:19 | 97 | |||

en4 | TheScrasse | 2020-11-13 20:32:22 | 34 | Tiny change: 'he array. Are ther' -> 'he array. You already have some $a[i] = x$. Are ther' | ||

en3 | TheScrasse | 2020-11-13 20:25:47 | 24 | Tiny change: 'th cases, you can ' -> 'th cases, if the answer is `YES`, you can ' | ||

en2 | TheScrasse | 2020-11-13 20:21:01 | 76 | |||

en1 | TheScrasse | 2020-11-13 20:18:34 | 2080 | Initial revision (published) |

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/07/2024 08:40:57 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|