Editorial by Sergiu Pușcaș.
100 - Registration Plates
Sergiu Pușcaș - Python 3
1 #!/usr/bin/python3 2 import re 3 4 for _ in range(int(input())): 5 s = input() 6 print("Correct!" if re.match("[A-Z]{2}\s[0-9]{2}\s[A-Z]{3}", s) or \ 7 re.match("B\s[0-9]{2,3}\s[A-Z]{3}", s) else "Incorrect!")
Petru Trîmbițaș - Perl
1 use v5.16; 2 use warnings; 3 4 my $n = <>; 5 chomp $n; 6 for (1..$n) { 7 my $line = <>; 8 chomp $line; 9 if($line =~ /^(([A-Z][A-Z]\ [0-9]{2})|(B\ [0-9]{2,3}))\ [A-Z]{3}$/) { 10 say "Correct!"; 11 } else { 12 say "Incorrect!"; 13 } 14 }
Marius Gavrilescu - Perl
1 #!/usr/bin/perl 2 use v5.14; 3 use warnings; 4 <>; 5 say /^([A-Z][A-Z] \d\d|B \d{2,3}) [A-Z]{3}$/ ? 'Correct!' : 'Incorrect!' while <>;
425 - Permudrome
First observation: we can work with only half of a palindrome, since there is a bijection between the total number of halves and the total number of palindromes. This reduces our N constraint from 30 to 15.
Second observation: count the frequency of each letter. If more than one letter occurs with an odd frequency, the answer is 0. If exactly one letter occurs with an odd frequency, it must be placed in the middle.
The straight-forward method for generating half of a palindrome is a backtracking algorithm. Since there are at most factorial(15) permutations, this approach times out.
The faster method is based on dynamic programming. Let dp[mask][last] be the number of configurations which:
- use the letters indicated by the positions of 1's in the bitmask
- end with the letter indicated by the position last
This table can be constructed in at least 3 ways:
- Generate future states and solve each of them recursively. This is too slow, since each state can be reached multiple times.
- Generate future states by only taking one step forward, and then solving the newly reached state sometime in the future. This is a bit tricky, because the states have to be solved in a specific order (first, all configurations with 1 positive bit, then all configurations with 2 positive bits, and so on).
- Consider the current state fixed and check what past states it could have been reached from. This approach propagates recursively down to the null configuration, but has the advantage of not having to compute the same state multiple times. Memoization can be used in this regard.
The only aspect we need to address is the fact that identical permutations should only be counted once. Consider, for instance, the permutation aaabbcccccc. Our solution counts the same permutation multiple times, because it rearranges all instances of the letter a (b and c respectively) between them. Thus, we get an answer that is actually factorial(frequency('a')) * factorial(frequency('b')) * factorial(frequency('c')) times larger.
This can be solved by either using a larger data type (such as long long, which is enough for factorial(15)), or by computing the modular multiplicative inverse of these factorials, modulo 666013.
The worst-case complexity is O(2N/2 * N/2).
1 #!/usr/bin/python3 2 from string import ascii_lowercase as alphabet 3 from collections import defaultdict 4 from sys import setrecursionlimit 5 6 setrecursionlimit(10**8) 7 8 mod = 666013 9 10 s = input() 11 m = int(input()) 12 13 bad = defaultdict(lambda: False) 14 solved = defaultdict(lambda: False) 15 dp = defaultdict(lambda: 0) 16 17 stock = "" 18 odd_freqs = 0 19 mid = None 20 21 def solve(conf, last): 22 if solved[(conf, last)]: 23 return dp[(conf, last)] 24 solved[(conf, last)] = True 25 26 for i, x in enumerate(stock): 27 if (conf & (1<<i)) and i != last and not bad[(stock[last], x)]: 28 dp[(conf, last)] += solve(conf - (1<<last), i) 29 30 return dp[(conf, last)] 31 32 def main(): 33 global stock, odd_freqs, mid 34 35 for i in range(m): 36 a, b = input().split() 37 bad[(a, b)] = bad[(b, a)] = True 38 39 odd_freqs = [x for x in alphabet if s.count(x) % 2 == 1] 40 stock = ''.join([x * (s.count(x) // 2) for x in alphabet]) 41 mid = odd_freqs[0] if len(odd_freqs) > 0 else None 42 43 if len(odd_freqs) > 1: 44 print("0") 45 exit(0) 46 47 for i in range(len(stock)): 48 solved[(2**i, i)] = True 49 dp[(2**i, i)] = 1 50 51 sol = 0 52 for i, x in enumerate(stock): 53 if (mid is None and not bad[(x, x)]) or \ 54 (mid is not None and not bad[(x, mid)]): 55 sol += solve(2**(len(stock))-1, i) 56 57 fact = [1] 58 for i in range(1, 20): 59 fact.append(fact[-1] * i) 60 61 for x in alphabet: 62 sol //= fact[stock.count(x)] 63 64 print(sol % mod) 65 66 if __name__ == '__main__': 67 main()
425 - U
Let:
- up[i][j] be the length of the longest sequence of 1's that starts at (i, j) and extends upwards.
- left_up[i][j] be the length of the longest sequence of 1's that starts at (i, j), goes to the left 0 or more columns, and then extends upwards 1 or more rows.
When computing left_up[][], make sure that the sequence actually extends upwards, not just to the left. The following testcase fails numerous solutions (answer is 4, not 7):
4 4 1101 1101 0001 1111
The solution is constructed by joining an "L" shape, described by left_up[i][j-1] with a "|", described by up[i][j]. Complexity: O(N * M).
1 #!/usr/bin/python3 2 from copy import deepcopy 3 4 n, m = map(int, input().split()) 5 a = [input() for i in range(n)] 6 up = [[0 for j in range(m)] for i in range(n)] 7 left_up = deepcopy(up) 8 9 for j in range(m): 10 up[0][j] = int(a[0][j]) 11 12 for i in range(1, n): 13 for j in range(m): 14 up[i][j] = up[i-1][j] + 1 if a[i][j] == '1' else 0 15 16 for i in range(n): 17 left_up[i][0] = up[i][0] 18 19 for i in range(n): 20 for j in range(1, m): 21 if a[i][j] == '1': 22 if up[i][j] > 1: 23 left_up[i][j] = up[i][j] 24 25 if left_up[i][j-1] > 1: 26 left_up[i][j] = max(left_up[i][j], 1+left_up[i][j-1]) 27 28 sol = 0 29 for i in range(n): 30 for j in range(1, m): 31 sol = max(sol, left_up[i][j-1] + up[i][j]) 32 33 if sol < 4: 34 sol = 0 35 36 print(sol)
900 - Kpath
Suppose we want to count how many ancestor-descendant paths have a cost of at most x (arbitrarily fixed). In order to do this, we can compute:
- ancestor[j][i] = the 2jth ancestor of vertex i (or 0 if i has less than 2j ancestors)
- cost[j][i] = the cost of the path from i to ancestor[j][i]
Having these two tables, we can climb logarithmically from any vertex to its highest ancestor such that the cost of the path between them does not exceed x. Therefore we can find the answer for a fixed x in O(N * log(N)).
Now, we need to find the lowest x such that there exist at least K paths with a cost of at most x. We can apply a binary search and solve the problem in O(N * log(N) * log(N * MAX_WEIGHT)).
Further reading: Stramosi (infoarena).
Sergiu Pușcaș - C++11
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long ll; 5 const int nmax = 100005; 6 const int logmax = 18; 7 8 ll k; 9 int n, a, b, x; 10 int cost[logmax][nmax], ancestor[logmax][nmax]; 11 bool seen[nmax]; 12 vector <pair <int, int>> v[nmax]; 13 14 void explore(int x) { 15 seen[x] = true; 16 17 for(auto t:v[x]) 18 if(!seen[t.first]) { 19 cost[0][t.first] = t.second; 20 ancestor[0][t.first] = x; 21 explore(t.first); 22 } 23 } 24 25 int climb(int i, ll energy) { 26 if(ancestor[0][i] == 0 || cost[0][i] > energy) 27 return 0; 28 29 int j=0; 30 while(ancestor[j+1][i] != 0 && cost[j+1][i] <= energy) 31 j++; 32 33 return (1<<j) + climb(ancestor[j][i], energy - cost[j][i]); 34 } 35 36 ll how_many_paths(ll energy) { 37 ll ret = 0; 38 for(int i=2; i<=n; i++) 39 ret += climb(i, energy); 40 41 return ret; 42 } 43 44 int main() { 45 cin>>n>>k; 46 47 for(int i=1; i<n; i++) { 48 cin>>a>>b>>x; 49 50 v[a].push_back(make_pair(b, x)); 51 v[b].push_back(make_pair(a, x)); 52 } 53 54 explore(1); 55 56 for(int j=1; (1<<j)<=n; j++) 57 for(int i=1; i<=n; i++) { 58 ancestor[j][i] = ancestor[j-1][ancestor[j-1][i]]; 59 cost[j][i] = cost[j-1][i] + cost[j-1][ancestor[j-1][i]]; 60 } 61 62 ll lo = 0, hi = 1000000007LL, mid; 63 while(hi - lo > 1) { 64 mid = lo + (hi - lo) / 2; 65 66 if(how_many_paths(mid) >= k) 67 hi = mid; 68 else 69 lo = mid; 70 } 71 72 if(how_many_paths(hi) < k) 73 hi = -1; 74 75 cout<<hi<<"\n"; 76 return 0; 77 }
