In this problem. I'm trying to prove that **at the end of the array, you can only achieve xor of any subarray of the original array** . I'm unable to do so and the proof given in the editorial is also unclear. Can someone prove it? Thanks

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

1 | ecnerwala | 3648 |

2 | Benq | 3580 |

3 | orzdevinwang | 3570 |

4 | cnnfls_csy | 3569 |

5 | Geothermal | 3568 |

6 | tourist | 3565 |

7 | maroonrk | 3530 |

8 | Radewoosh | 3520 |

9 | Um_nik | 3481 |

10 | jiangly | 3467 |

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

1 | maomao90 | 174 |

2 | adamant | 164 |

2 | awoo | 164 |

4 | TheScrasse | 160 |

5 | nor | 159 |

6 | maroonrk | 156 |

7 | SecondThread | 150 |

8 | -is-this-fft- | 149 |

9 | pajenegod | 146 |

10 | BledDest | 144 |

**at the end of the array, you can only achieve xor of any subarray of the original array** . I'm unable to do so and the proof given in the editorial is also unclear. Can someone prove it? Thanks

This was my initial submission for the problem: https://mirror.codeforces.com/contest/1815/submission/237704790

However just changing the value of arr[0] to something a lot lesser, the code becomes accepted: https://mirror.codeforces.com/contest/1815/submission/237704230

The algorithm is pretty straightforward (as seen from my code) but why should the value of arr[0] be so less? isn't -(1e9 + 1) small enough for it? If you can help, perhaps by giving a test case which fails for the initial submission I will be grateful

I was trying to solve E.Collapsing Strings from the recent educational round. I used polynomial hashing to count the occurrences of each suffix of each string in the given list and store it in a map, then iterate over the prefixes of all the strings and then subtract 2*length_of_the_prefix*(the_count_of_this_prefix_in_the_map) from the initial count(assuming total length of every pairwise combination is added to the final count) to get the final answer.

For the purpose of keeping count of the frequencies of the hash I was using a map, which gave TLE. However after replacing map with unordered_map it was accepted.

This caused me think about which situations I should use an unordered_map instead of a regular map (ordered map). Is an unordered_map always inherently faster than a map? in which cases should I use it? I'm asking here because I couldn't get a satisfactory answer after searching the web. Please help.

P.S also if you could, please suggest how I could better implement my algorithm for the above problem if possible.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/16/2024 06:55:23 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|