[Here](https://mirror.codeforces.com/contestInvitation/d123f3d2aab682a92870919be0dcacb34706b508) is the link to the contest. The problems are from Codeforces problemset.↵
↵
#### [A. Ascend](https://mirror.codeforces.com/gym/526229/problem/A)↵
↵
<spoiler summary="Solution">↵
<p>↵
Let's iterate through the given array and store the length of the current increasing subarray in the variable $curLen$. If the current element is more than the previous we need to increase $curLen$ by one. Otherwise, the current number is a start of a new increasing subarray, so we need to restart $curLen$ with $1$. We keep track of the maximum after considering every number.↵
</p>↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
n = int(input())↵
a = list(map(int, input().split()))↵
↵
max_len = 1↵
cur_len = 1↵
↵
for idx in range(1, n):↵
if a[idx - 1] >= a[idx]:↵
cur_len = 0↵
↵
cur_len += 1↵
max_len = max(max_len, cur_len)↵
↵
print(max_len)↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [B. String Fusion](https://mirror.codeforces.com/gym/526229/problem/B)↵
↵
<spoiler summary="Solution">↵
Let's suppose that when we calculate the collapse of two strings $a$ and $b$, we reverse the string a first, so that instead of checking and removing the last letters of $a$, we do this to the first letters of $a$. Then, $|C(a,b)|=|a|+|b|−2|LCP(a′,b)|$, where $LCP(a′,b)$ is the longest common prefix of $a′$ (the reversed version of $a$) and $b$.↵
↵
Then the answer to the problem becomes $ 2n \sum_{i=1}^{n} |s_i| - 2 \sum_{i=1}^{n} \sum_{j=1}^{n} \text{LCP}(s_i, s_j) $.↵
↵
We need some sort of data structure that allows us to store all strings $s_i$↵
and for every string $s_j$, calculate the total $LCP$ of it with all strings in the structure. There are many ways to implement it (hashing, suffix arrays, etc), but in our opinion, one of the most straightforward is using a trie.↵
↵
Build a trie on all strings $s_i$. Then, for every vertex of the trie, calculate the number of strings $s_i$ that end in the subtree of that vertex (you can maintain it while building the trie: when you add a new string into it, increase this value by 1 on every vertex you go through).↵
↵
If you want to find the LCP of two strings $s$ and $t$ using a trie, you can use the fact that it is equal to the number of vertices that are both on the path to $s$ and on the path to $t$ at the same time (except for the root vertex). This method can be expanded to querying the sum of LCP of a given string $s$ and all strings in the trie as follows: try to find $s$ in the trie. While searching for it, you will descend in the trie and go through vertices that represent prefixes of $s$. For every such prefix, you need the number of strings in the trie that have the same prefix — and it is equal to the number of strings ending in the subtree of the corresponding vertex (which we already calculated). Don't forget that you shouldn't consider the root, since the root represents the empty prefix.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
class Trienode:↵
def __init__(self):↵
self.child= {}↵
self.cnt = 0↵
↵
↵
class Trie:↵
def __init__(self):↵
self.root=Trienode()↵
↵
def insert(self, word: str) -> None:↵
cur = self.root↵
↵
for c in word:↵
ind=ord(c)-ord("a")↵
↵
if ind not in cur.child:↵
cur.child[ind]=Trienode()↵
↵
cur=cur.child[ind]↵
cur.cnt += 1↵
↵
↵
def search(self, word: str) -> int:↵
↵
cur=self.root↵
tot = 0↵
for c in word:↵
ind=ord(c)-ord("a")↵
if ind not in cur.child:↵
return tot↵
↵
cur=cur.child[ind]↵
tot += cur.cnt * 2↵
↵
return tot↵
↵
n = int(input())↵
s = [input() for i in range(n)]↵
trie = Trie()↵
for cur in s:↵
trie.insert(cur)↵
total = sum([len(cur)*2*n for cur in s])↵
for cur in s:↵
total -= trie.search(cur[::-1])↵
print(total)↵
↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
#### [C. Prefix-Free Words](https://mirror.codeforces.com/gym/526229/problem/C)↵
↵
↵
<spoiler summary="Solution">↵
To solve this problem efficiently, we can sort the given input array of word length in ascending order while keeping track of their original indices.It helps in generating the smallest possible lexicographical strings by starting with the shortest strings. Using a $Trie$ data structure, we efficiently generate unique binary strings for each length, which are not a prefix of other words. For each length, starting from the smallest, we can build a binary string by traversing the $Trie$. If a binary string of the required length cannot be uniquely formed (i.e., both possible extensions lead to existing valid prefixs), we will return $NO$. If successful, we can store the binary string and update the $Trie$ to reflect the newly added string. After forming a binary string, we have to backtrack to update the $is_end$ flags appropriately to ensure that we correctly mark nodes as end nodes when there are no further possible paths (all childrens are occupied).↵
↵
↵
Time Complexity: $O(NlogN + N * M)$ time. N is input array length and M denotes the maximum word length ↵
↵
Space Complexity: $O(N * M)$↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
class TrieNode:↵
def __init__(self):↵
self.ch = [None, None]↵
self.is_end = False ↵
↵
class Trie:↵
def __init__(self):↵
self.root = TrieNode()↵
↵
def insert(self, length):↵
stack, trie = [], self.root ↵
word = []↵
# finding a unique word representation with the given length↵
for i in range(length):↵
stack.append(trie) ↵
if trie.ch[0] is None or not trie.ch[0].is_end:↵
if trie.ch[0] is None:↵
trie.ch[0] = TrieNode()↵
trie = trie.ch[0]↵
word.append('0')↵
elif trie.ch[1] is None or not trie.ch[1].is_end:↵
if trie.ch[1] is None:↵
trie.ch[1] = TrieNode()↵
trie = trie.ch[1]↵
word.append('1')↵
else:↵
return False↵
trie.is_end = True↵
↵
# backtrcking to update the is_end of the nodes if they don't have unoccopied child for the word represetnation↵
while stack and stack[-1].ch[1] and stack[-1].ch[1].is_end:↵
prev = stack.pop()↵
prev.is_end = True↵
↵
return ''.join(word)↵
↵
def main():↵
n = int(input()) ↵
nums = sorted(zip(map(int, input().split()), range(n)))↵
trie = Trie()↵
words = [''] * n↵
for num, indx in nums:↵
word = trie.insert(num)↵
if not word:↵
print('NO')↵
return↵
words[indx] = word↵
↵
print('YES')↵
for word in words:↵
print(word)↵
↵
if __name__ == '__main__':↵
main()↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
#### [D. BitPleasure Maximization](https://mirror.codeforces.com/gym/526229/problem/D)↵
↵
<spoiler summary = "Hint1">↵
How can we find the best possible match for the XOR of some number from an array using a Trie?.↵
</spoiler>↵
↵
<spoiler summary = "Hint2">↵
Can We use the same concept for prefix and suffix?↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
For this problem, we will use the Trie data structure. Let's start by calculating the prefix of the array. For $\(0 \leq i \leq n\)$, let $pref[0] = 0$. After calculating $prefix[i]$, we should add $prefix[i]$ to the Trie. Then, we can easily calculate the best possible match for the XOR of the new suffix that starts from $n$ and ends at $i + 1$. In this case, we are guaranteed that the prefix and suffix do not intersect.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
class Node:↵
def __init__(self):↵
self.children = [None, None]↵
↵
class Trie:↵
def __init__(self, val):↵
self.root = Node()↵
self.bit_len = val↵
↵
def insert(self, num):↵
cur = self.root↵
↵
for i in range(self.bit_len, -1, -1):↵
bit = 1 if num & (1 << i)else 0↵
if cur.children[bit] is None:↵
cur.children[bit] = Node()↵
cur = cur.children[bit]↵
↵
def findMax(self, num):↵
cur = self.root↵
max_num = 0↵
for i in range(self.bit_len, -1, -1):↵
bit = 1 if num & (1 << i) else 0↵
if cur.children[1 - bit] is not None:↵
max_num = max_num | (1 << i)↵
cur = cur.children[1 - bit]↵
else:↵
cur = cur.children[bit]↵
return max_num↵
↵
n = int(sys.stdin.readline().strip())↵
↵
nums = list(map(int, sys.stdin.readline().strip().split()))↵
↵
trie = Trie(len(bin(max(nums))))↵
↵
tot_pref = 0↵
nums = [0] + nums↵
↵
for num in nums:↵
tot_pref ^= num↵
↵
cur_pref = 0↵
ans = 0↵
↵
for num in nums:↵
cur_pref ^= num↵
trie.insert(cur_pref)↵
ans = max(ans, trie.findMax(cur_pref ^ tot_pref))↵
↵
print(ans)↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
#### [A. Ascend](https://mirror.codeforces.com/gym/526229/problem/A)↵
↵
<spoiler summary="Solution">↵
<p>↵
Let's iterate through the given array and store the length of the current increasing subarray in the variable $curLen$. If the current element is more than the previous we need to increase $curLen$ by one. Otherwise, the current number is a start of a new increasing subarray, so we need to restart $curLen$ with $1$. We keep track of the maximum after considering every number.↵
</p>↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
n = int(input())↵
a = list(map(int, input().split()))↵
↵
max_len = 1↵
cur_len = 1↵
↵
for idx in range(1, n):↵
if a[idx - 1] >= a[idx]:↵
cur_len = 0↵
↵
cur_len += 1↵
max_len = max(max_len, cur_len)↵
↵
print(max_len)↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [B. String Fusion](https://mirror.codeforces.com/gym/526229/problem/B)↵
↵
<spoiler summary="Solution">↵
Let's suppose that when we calculate the collapse of two strings $a$ and $b$, we reverse the string a first, so that instead of checking and removing the last letters of $a$, we do this to the first letters of $a$. Then, $|C(a,b)|=|a|+|b|−2|LCP(a′,b)|$, where $LCP(a′,b)$ is the longest common prefix of $a′$ (the reversed version of $a$) and $b$.↵
↵
Then the answer to the problem becomes $ 2n \sum_{i=1}^{n} |s_i| - 2 \sum_{i=1}^{n} \sum_{j=1}^{n} \text{LCP}(s_i, s_j) $.↵
↵
We need some sort of data structure that allows us to store all strings $s_i$↵
and for every string $s_j$, calculate the total $LCP$ of it with all strings in the structure. There are many ways to implement it (hashing, suffix arrays, etc), but in our opinion, one of the most straightforward is using a trie.↵
↵
Build a trie on all strings $s_i$. Then, for every vertex of the trie, calculate the number of strings $s_i$ that end in the subtree of that vertex (you can maintain it while building the trie: when you add a new string into it, increase this value by 1 on every vertex you go through).↵
↵
If you want to find the LCP of two strings $s$ and $t$ using a trie, you can use the fact that it is equal to the number of vertices that are both on the path to $s$ and on the path to $t$ at the same time (except for the root vertex). This method can be expanded to querying the sum of LCP of a given string $s$ and all strings in the trie as follows: try to find $s$ in the trie. While searching for it, you will descend in the trie and go through vertices that represent prefixes of $s$. For every such prefix, you need the number of strings in the trie that have the same prefix — and it is equal to the number of strings ending in the subtree of the corresponding vertex (which we already calculated). Don't forget that you shouldn't consider the root, since the root represents the empty prefix.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
class Trienode:↵
def __init__(self):↵
self.child= {}↵
self.cnt = 0↵
↵
↵
class Trie:↵
def __init__(self):↵
self.root=Trienode()↵
↵
def insert(self, word: str) -> None:↵
cur = self.root↵
↵
for c in word:↵
ind=ord(c)-ord("a")↵
↵
if ind not in cur.child:↵
cur.child[ind]=Trienode()↵
↵
cur=cur.child[ind]↵
cur.cnt += 1↵
↵
↵
def search(self, word: str) -> int:↵
↵
cur=self.root↵
tot = 0↵
for c in word:↵
ind=ord(c)-ord("a")↵
if ind not in cur.child:↵
return tot↵
↵
cur=cur.child[ind]↵
tot += cur.cnt * 2↵
↵
return tot↵
↵
n = int(input())↵
s = [input() for i in range(n)]↵
trie = Trie()↵
for cur in s:↵
trie.insert(cur)↵
total = sum([len(cur)*2*n for cur in s])↵
for cur in s:↵
total -= trie.search(cur[::-1])↵
print(total)↵
↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
#### [C. Prefix-Free Words](https://mirror.codeforces.com/gym/526229/problem/C)↵
↵
↵
<spoiler summary="Solution">↵
To solve this problem efficiently, we can sort the given input array of word length in ascending order while keeping track of their original indices.It helps in generating the smallest possible lexicographical strings by starting with the shortest strings. Using a $Trie$ data structure, we efficiently generate unique binary strings for each length, which are not a prefix of other words. For each length, starting from the smallest, we can build a binary string by traversing the $Trie$. If a binary string of the required length cannot be uniquely formed (i.e., both possible extensions lead to existing valid prefixs), we will return $NO$. If successful, we can store the binary string and update the $Trie$ to reflect the newly added string. After forming a binary string, we have to backtrack to update the $is_end$ flags appropriately to ensure that we correctly mark nodes as end nodes when there are no further possible paths (all childrens are occupied).↵
↵
↵
Time Complexity: $O(NlogN + N * M)$ time. N is input array length and M denotes the maximum word length ↵
↵
Space Complexity: $O(N * M)$↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
class TrieNode:↵
def __init__(self):↵
self.ch = [None, None]↵
self.is_end = False ↵
↵
class Trie:↵
def __init__(self):↵
self.root = TrieNode()↵
↵
def insert(self, length):↵
stack, trie = [], self.root ↵
word = []↵
# finding a unique word representation with the given length↵
for i in range(length):↵
stack.append(trie) ↵
if trie.ch[0] is None or not trie.ch[0].is_end:↵
if trie.ch[0] is None:↵
trie.ch[0] = TrieNode()↵
trie = trie.ch[0]↵
word.append('0')↵
elif trie.ch[1] is None or not trie.ch[1].is_end:↵
if trie.ch[1] is None:↵
trie.ch[1] = TrieNode()↵
trie = trie.ch[1]↵
word.append('1')↵
else:↵
return False↵
trie.is_end = True↵
↵
# backtrcking to update the is_end of the nodes if they don't have unoccopied child for the word represetnation↵
while stack and stack[-1].ch[1] and stack[-1].ch[1].is_end:↵
prev = stack.pop()↵
prev.is_end = True↵
↵
return ''.join(word)↵
↵
def main():↵
n = int(input()) ↵
nums = sorted(zip(map(int, input().split()), range(n)))↵
trie = Trie()↵
words = [''] * n↵
for num, indx in nums:↵
word = trie.insert(num)↵
if not word:↵
print('NO')↵
return↵
words[indx] = word↵
↵
print('YES')↵
for word in words:↵
print(word)↵
↵
if __name__ == '__main__':↵
main()↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
#### [D. BitPleasure Maximization](https://mirror.codeforces.com/gym/526229/problem/D)↵
↵
<spoiler summary = "Hint1">↵
How can we find the best possible match for the XOR of some number from an array using a Trie?.↵
</spoiler>↵
↵
<spoiler summary = "Hint2">↵
Can We use the same concept for prefix and suffix?↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
For this problem, we will use the Trie data structure. Let's start by calculating the prefix of the array. For $\(0 \leq i \leq n\)$, let $pref[0] = 0$. After calculating $prefix[i]$, we should add $prefix[i]$ to the Trie. Then, we can easily calculate the best possible match for the XOR of the new suffix that starts from $n$ and ends at $i + 1$. In this case, we are guaranteed that the prefix and suffix do not intersect.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
class Node:↵
def __init__(self):↵
self.children = [None, None]↵
↵
class Trie:↵
def __init__(self, val):↵
self.root = Node()↵
self.bit_len = val↵
↵
def insert(self, num):↵
cur = self.root↵
↵
for i in range(self.bit_len, -1, -1):↵
bit = 1 if num & (1 << i)else 0↵
if cur.children[bit] is None:↵
cur.children[bit] = Node()↵
cur = cur.children[bit]↵
↵
def findMax(self, num):↵
cur = self.root↵
max_num = 0↵
for i in range(self.bit_len, -1, -1):↵
bit = 1 if num & (1 << i) else 0↵
if cur.children[1 - bit] is not None:↵
max_num = max_num | (1 << i)↵
cur = cur.children[1 - bit]↵
else:↵
cur = cur.children[bit]↵
return max_num↵
↵
n = int(sys.stdin.readline().strip())↵
↵
nums = list(map(int, sys.stdin.readline().strip().split()))↵
↵
trie = Trie(len(bin(max(nums))))↵
↵
tot_pref = 0↵
nums = [0] + nums↵
↵
for num in nums:↵
tot_pref ^= num↵
↵
cur_pref = 0↵
ans = 0↵
↵
for num in nums:↵
cur_pref ^= num↵
trie.insert(cur_pref)↵
ans = max(ans, trie.findMax(cur_pref ^ tot_pref))↵
↵
print(ans)↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
