Editorial of MindCoding 2016 Round 4 (Div. 2)

Editorial by Sergiu Pușcaș.

50 - Virtual Pharmacy

Sergiu Pușcaș - Python 3

    1 #!/usr/bin/python3
    2 
    3 v = []
    4 for t in range(int(input())):
    5     line = input().split()
    6 
    7     if line[0] == '1':
    8         v.append(line[1])
    9     if line[0] == '2' and len(v) > 0:
   10         v.pop()
   11     if line[0] == '3':
   12         filtered = [x for x in v if int(x) <= int(line[1])]
   13         print("Empty" if filtered == [] else ' '.join(filtered))

Cosmin Rusu - C++11

    1 #include <iostream>
    2 #include <vector>
    3 
    4 using namespace std;
    5 
    6 int main() {
    7     vector <int> v;
    8     int n;
    9 
   10     cin >> n;
   11     while(n--) {
   12         int op, x;
   13         cin >> op;
   14         if(op == 1) {
   15             cin >> x;
   16             v.push_back(x);
   17         }
   18         else if(op == 2) {
   19             if(v.size())
   20                 v.pop_back();
   21         }
   22         else {
   23             cin >> x;
   24             vector <int> aux;
   25             for(auto it : v)
   26                 if(it <= x)
   27                     aux.push_back(it);
   28             if(aux.size() == 0) {
   29                 cout << "Empty";
   30             }
   31             else
   32                 for(auto it : aux)
   33                     cout << it << ' ';
   34             cout << '\n';
   35         }
   36     }
   37 
   38     return 0;
   39 }

100 - Registration Plates

This problem admits some very short solutions, based on regular expressions:

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:

  1. Generate future states and solve each of them recursively. This is too slow, since each state can be reached multiple times.
  2. 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).
  3. 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)
Questions?

Sponsors Gold