100 - Peculiar Times
The regular solution (Sergiu Puscas)
This is a straightforward implementation problem and does not require any algorithmic knowledge. For any given time, each of the criteria can be easily verified. Also, no integer manipulation is required, especially for the last two conditions, considering the small set of times that validate them:
- The only valid times that have consecutive digits are 01:23, 12:34 and 23:45;
- The only valid times that make up a number which is a power of two are 10:24 and 20:48 (the next one, 40:96, is already too large).
C++ solution
1 #include <iostream> 2 using namespace std; 3 4 int t; 5 bool peculiar, valid; 6 char X, Y, Z, T, separator; 7 string fullTime, hour, minutes; 8 9 int main() { 10 cin>>t; 11 while(t--) { 12 cin>>X>>Y>>separator>>Z>>T; 13 fullTime.clear(); 14 fullTime.push_back(X); 15 fullTime.push_back(Y); 16 fullTime.push_back(Z); 17 fullTime.push_back(T); 18 19 hour.clear(); 20 hour.push_back(X); 21 hour.push_back(Y); 22 23 minutes.clear(); 24 minutes.push_back(Z); 25 minutes.push_back(T); 26 27 peculiar = false; 28 if(Z == '0' && T == '0') peculiar = true; 29 if(X == Z && Y == T) peculiar = true; 30 if(X == T && Y == Z) peculiar = true; 31 if(fullTime == "0123" || fullTime == "1234" || fullTime == "2345") peculiar = true; 32 if(fullTime == "1024" || fullTime == "2048") peculiar = true; 33 34 valid = true; 35 if(hour < "00" || hour >= "24") valid = false; 36 if(minutes < "00" || minutes >= "60") valid = false; 37 38 cout<<(valid && peculiar? "YES\n":"NO\n"); 39 } 40 41 return 0; 42 }
Python solution
1 for _ in range(0, input()): 2 a, b = raw_input().split(':') 3 print ['NO', 'YES'][(b=='00' or a==b or a==b[::-1] or a+b in '0123 1234 2345 1024 2048'.split()) and a < '24' and b <= '60']
A regex solution (Marius Gavrilescu)
This problem can also be solved using regular expressions, as seen in the following solution.1 #!/usr/bin/perl 2 use v5.14; 3 use warnings; 4 5 <>; 6 my $hour = qr/(?:[01]\d|2[0-3])/; # Matches a valid hour (00 - 23) 7 my $min = qr/[0-5]\d/; # Matches valid minutes (00 - 59) 8 my $time = qr/$hour:$min/; # Matches a valid time 9 my $exact = qr/\d\d:00/; # Matches exact hours (XY:00) 10 my $same = qr/(\d)(\d):(?:\1\2|\2\1)/; # Matches XY:XY and XY:YX 11 my $cons = qr/01:23|12:34|23:45/; # Matches consecutive digits 12 my $pow2 = qr/10:24|20:48/; # Matches a power of 2 13 14 my $peculiar = qr/(?:$exact|$same|$cons|$pow2)/; # Matches peculiar times 15 16 my $re = qr/(?=$time)$peculiar/; # Matches valid peculiar times 17 say m/$re/ ? 'YES' : 'NO' while <>;A typical way of writing the above:
1 #!/usr/bin/perl 2 use v5.14; 3 use warnings; 4 5 <>; 6 say /(?:[01]\d|2[0-3]):[0-5]\d/ && /:00|(\d)(\d):(?:\1\2|\2\1)|01:23|12:34|23:45|10:24|20:48/ ? 'YES' : 'NO' while <>;This solution can be golfed further if necessary.
1 <>;CORE::say/(?:[01]\d|2[0-3]):[0-5]\d/&&/:00|(\d)(\d):(?:\1\2|\2\1)|01:23|12:34|23:45|10:24|20:48/?YES:NO while<>;
250 - Tournament
The main problem we're dealing with is finding a suitable data structure. First of all, it should allow updating teams' scores and total goals, with every passing match. Secondly, it should facilitate custom sorting, based on the given criteria (number of points > number of goals > team name). Most modern programming languages provide such a data structure: map + vector from C++'s Standard Template Library, or a dictionary in Python.
C++11 solution (Sergiu Puscas)
1 #include <iostream> 2 #include <map> 3 #include <vector> 4 #include <string> 5 #include <algorithm> 6 #define totalPoints first 7 #define totalGoals second 8 #define name first 9 #define stats second 10 using namespace std; 11 12 map <string, pair <int, int>> M; 13 vector <pair <string, pair <int, int>>> v; 14 int goalsA, goalsB, bonusA, bonusB; 15 string teamA, teamB; 16 17 bool cmp(pair <string, pair <int, int>> A, pair <string, pair <int, int>> B) { 18 if(A.stats.totalPoints != B.stats.totalPoints) 19 return A.stats.totalPoints > B.stats.totalPoints; 20 21 if(A.stats.totalGoals != B.stats.totalGoals) 22 return A.stats.totalGoals > B.stats.totalGoals; 23 24 return A.name < B.name; 25 } 26 27 int main() { 28 for(int i=1; i<=6; i++) { 29 cin>>teamA>>teamB>>goalsA>>goalsB; 30 31 if(goalsA > goalsB) bonusA = 3, bonusB = 0; 32 else if(goalsA == goalsB) bonusA = 1, bonusB = 1; 33 else bonusA = 0, bonusB = 3; 34 35 if(M.find(teamA) == M.end()) M[teamA] = make_pair(0, 0); 36 if(M.find(teamB) == M.end()) M[teamB] = make_pair(0, 0); 37 38 M[teamA] = make_pair(M[teamA].totalPoints + bonusA, M[teamA].totalGoals + goalsA); 39 M[teamB] = make_pair(M[teamB].totalPoints + bonusB, M[teamB].totalGoals + goalsB); 40 } 41 42 for(auto team:M) v.push_back(team); 43 sort(v.begin(), v.end(), cmp); 44 for(auto team:v) cout<<team.name<<"\n"; 45 46 return 0; 47 }
Python solution
1 scoreboard, goalboard = {}, {} 2 3 for _ in range(0, 6): 4 teamA, teamB, goalsA, goalsB = raw_input().split() 5 goalsA, goalsB = map(int, [goalsA, goalsB]) 6 7 if goalsA > goalsB: scoreA, scoreB = 3, 0 8 elif goalsA == goalsB: scoreA, scoreB = 1, 1 9 else: scoreA, scoreB = 0, 3 10 11 if not teamA in scoreboard: scoreboard[teamA], goalboard[teamA] = 0, 0 12 if not teamB in scoreboard: scoreboard[teamB], goalboard[teamB] = 0, 0 13 14 scoreboard[teamA] += scoreA 15 scoreboard[teamB] += scoreB 16 17 goalboard[teamA] += goalsA 18 goalboard[teamB] += goalsB 19 20 print '\n'.join(["%s" % x[2] for x in sorted([(scoreboard[x], goalboard[x], x) for x in scoreboard], key=lambda x: (-x[0], -x[1], x[2]))])
500 - Staff
Although it looks like a tractor kind of problem, Staff allows for some quite elegant solutions.
Observation
The ASCII staff provided in the statement can be hard-coded and used in the solution. More concisely, it can be split horizontally into a series of sections. The treble cleff and final bar each make up one section. Each note occupies a 5-character section, with the @ situated exactly in the middle. This assures the right distance between consecutive notes.
All that's left is the printing. If the series described above is constructed appropriately, then it's a simple matter of executing multiple passes across the series, with each pass printing one row of the solution staff (much like an actual computer printer stamps sentences on a piece of paper, one row at a time).
C solution (Marius Gavrilescu)
1 #include<stdio.h> 2 #include<string.h> 3 4 const char *notes = "C C#D D#E F F#G G#A A#B C2C2#"; // Notes in order. Note #i is at position i * 2 in the string 5 const char *ex[] = { // ! instead of \\ since escaped backslashes are ugly 6 "----|-!-----------------------------------------------------------------------------+", 7 " | } |", 8 "----|-/-----------------------------------------------------|----|------------------|", 9 " |/ 4 | | | | (@) #(@) |", 10 "---/|-----------------------------------|----|----|----|----|----|--(@)--|----|-----|", 11 " / | 4 | | | | | (@) #(@) | | | |", 12 "-{--|-!------------------|----|----|----|----|--(@)-#(@)------------|----|----|-----|", 13 " !_|_/ | | | | | (@) #(@) | |", 14 "----|!---------|----|----|----|--(@)------------------------------------------------+", 15 " |_} | | (@) #(@) ", 16 " (@) #(@) "}; 17 18 int v[255]; 19 20 void print(int l, int a, int b) { 21 for(int i = a ; i < b ; i++) 22 putchar(ex[l][i] == '!' ? '\\' : ex[l][i]); // Replace '!' with '\\' 23 } 24 25 int main() { 26 int n; 27 char note[10]; 28 scanf("%d ", &n); 29 for(int i = 0 ; i < n ; i++){ 30 scanf("%s ", note); 31 v[i] = (strstr(notes, note) - notes) / 2; // Index of the note 32 v[i] = 12 + v[i] * 5; // Start position of the note 33 } 34 35 for (int l = 0; l < 11; l++) { // For each line of ex... 36 print(l, 0, 12); // ... print the clef and measure 37 for(int i = 0; i < n; i++) 38 print(l, v[i], v[i] + 5); // ... print the note 39 print(l, 82, 85); // ... print the final bar 40 puts(""); // ... print a newline 41 } 42 43 return 0; 44 }
Python solution (Sergiu Puscas)
1 base = ['----|-\-----------------------------------------------------------------------------+', 2 ' | } |', 3 '----|-/-----------------------------------------------------|----|------------------|', 4 ' |/ 4 | | | | (@) #(@) |', 5 '---/|-----------------------------------|----|----|----|----|----|--(@)--|----|-----|', 6 ' / | 4 | | | | | (@) #(@) | | | |', 7 '-{--|-\------------------|----|----|----|----|--(@)-#(@)------------|----|----|-----|', 8 ' \_|_/ | | | | | (@) #(@) | |', 9 '----|\---------|----|----|----|--(@)------------------------------------------------+', 10 ' |_} | | (@) #(@) ', 11 ' (@) #(@) '] 12 13 link = {'clef': (0, 12), 14 'C': (12, 17), 15 'C#': (17, 22), 16 'D': (22, 27), 17 'D#': (27, 32), 18 'E': (32, 37), 19 'F': (37, 42), 20 'F#': (42, 47), 21 'G': (47, 52), 22 'G#': (52, 57), 23 'A': (57, 62), 24 'A#': (62, 67), 25 'B': (67, 72), 26 'C2': (72, 77), 27 'C2#': (77, 82), 28 'bar': (82, 85)} 29 30 v = ['clef'] + [raw_input() for _ in range(0, input())] + ['bar'] 31 print '\n'.join([''.join([base[line][link[element][0]:link[element][1]] for element in v]) for line in range(0, len(base))])
The entire functionality only takes up two lines of code. All else is preparation.
Perl solution (Marius Gavrilescu)
1 #!/usr/bin/perl 2 use v5.14; 3 use warnings; 4 5 my @notes = qw/C C# D D# E F F# G G# A A# B C2 C2#/; # List of notes 6 my %notes = map {; $notes[$_] => 12 + $_ * 5 } 0 .. $#notes; # Hash from note name to start index 7 8 my @ex = split "\n", <<'EOF'; 9 ----|-\-----------------------------------------------------------------------------+ 10 | } | 11 ----|-/-----------------------------------------------------|----|------------------| 12 |/ 4 | | | | (@) #(@) | 13 ---/|-----------------------------------|----|----|----|----|----|--(@)--|----|-----| 14 / | 4 | | | | | (@) #(@) | | | | 15 -{--|-\------------------|----|----|----|----|--(@)-#(@)------------|----|----|-----| 16 \_|_/ | | | | | (@) #(@) | | 17 ----|\---------|----|----|----|--(@)------------------------------------------------+ 18 |_} | | (@) #(@) 19 (@) #(@) 20 EOF 21 $_ .= ' ' x 80 for @ex; # Append 80 spaces to each line of @ex 22 23 <>; # Read the first line and ignore it 24 my @song = map { chomp; $notes{$_} } <>; # Song is an array of start indices 25 26 for my $l (@ex) { # For each line of @ex... 27 print substr $l, 0, 12; # ...print the clef and measure 28 print substr $l, $_, 5 for @song; # ...print each note 29 print substr $l, 82, 3; # ...print the final bar 30 say ''; # ...print a newline 31 }
Alternative solutions
Examples from the contest: 6930 (5.62 KB), 7208 (5.60 KB), 7390 (4.25 KB), 6655 (3.94 KB), 6924 (3.38 KB).
1000 - Bosses
Bosses can be summarised as follows:
Given a root-adjustable tree, find the Lowest Common Ancestor between pairs of given nodes.
At a closer look, we notice that any LCA can be obtained solely by using the original tree. Regardless of current root, only 4 LCAs are needed:
- lca1 = LCA(x, y)
- lca2 = LCA(x, currentRoot)
- lca3 = LCA(y, currentRoot)
- lca4 = root
For each query, the solution is the lca that grants the minimum value for the expression:
dist(lcai, x) + dist(lcai, y), 1 ≤ i ≤ 4
C++ solution Cosmin Rusu
1 #include <vector> 2 #include <iostream> 3 4 using namespace std; 5 6 const int maxn = 100005; 7 const int maxlg = 20; 8 9 vector <int> g[maxn]; 10 int n, m, root = 1, rmq[maxlg][maxn << 1], euler[maxn << 1], level[maxn << 1], k, first[maxn], lg[maxn << 1]; 11 12 inline void dfs(int node, int father, int actlevel) { 13 euler[++ k] = node; 14 level[ k ] = actlevel; 15 first[node] = k; 16 for(vector <int> :: iterator it = g[node].begin() ; it != g[node].end() ; ++ it) { 17 if(*it == father) 18 continue; 19 dfs(*it, node, actlevel + 1); 20 euler[++ k] = node; 21 level[ k ] = actlevel; 22 } 23 } 24 25 inline void preprocess() { 26 for(int i = 2 ; i <= k ; ++ i) 27 lg[i] = lg[i >> 1] + 1; 28 for(int i = 1 ; i <= k ; ++ i) 29 rmq[0][i] = i; 30 for(int l = 1 ; (1 << l) <= k ; ++ l) { 31 int aux = (1 << (l - 1)); 32 for(int i = 1 ; i + (1 << l) - 1 <= k ; ++ i) { 33 rmq[l][i] = rmq[l - 1][i]; 34 if(level[rmq[l][i]] > level[rmq[l - 1][i + aux]]) 35 rmq[l][i] = rmq[l - 1][i + aux]; 36 } 37 } 38 } 39 40 inline int LCA(int x, int y) { 41 x = first[x]; 42 y = first[y]; 43 if(x > y) 44 swap(x, y); 45 int logaritm = lg[y - x + 1]; 46 int ret = rmq[logaritm][x]; 47 if(level[ret] > level[rmq[logaritm][y - (1 << logaritm) + 1]]) 48 ret = rmq[logaritm][y - (1 << logaritm) + 1]; 49 return euler[ret]; 50 } 51 52 inline int dist(int x, int y) { 53 int lca = LCA(x, y); 54 return level[first[x]] + level[first[y]] - 2 * level[first[lca]]; 55 } 56 57 inline int check(int x, int y, int lca) { 58 return dist(x, lca) + dist(y, lca) + 2 * dist(lca, root); 59 } 60 61 inline int query(int x, int y) { 62 int lca = LCA(x, y); 63 int auxlca = LCA(x, root); 64 if(check(x, y, lca) > check(x, y, auxlca)) 65 lca = auxlca; 66 auxlca = LCA(y, root); 67 if(check(x, y, lca) > check(x, y, auxlca)) 68 lca = auxlca; 69 auxlca = root; 70 if(check(x, y, lca) > check(x, y, auxlca)) 71 lca = auxlca; 72 return lca; 73 } 74 75 int main() { 76 cin >> n >> m; 77 for(int i = 1 ; i < n ; ++ i) { 78 int x, y; 79 cin >> x >> y; 80 g[x].push_back(y); 81 g[y].push_back(x); 82 } 83 dfs(1, 0, 1); 84 preprocess(); 85 for(int i = 1 ; i <= m ; ++ i) { 86 int type, x, y; 87 cin >> type; 88 if(type == 1) { 89 cin >> x; 90 root = x; 91 } 92 else { 93 cin >> x >> y; 94 int lca = query(x, y); 95 if(lca == x || lca == y) 96 cout << "-1\n"; 97 else 98 cout << lca << '\n'; 99 } 100 } 101 }
