### k790alex's blog

By k790alex, 7 months ago, ,

Hi,

Tomorrow is going to be held The 2017 ACM-ICPC Mexico and Central America Finals (https://icpc.baylor.edu/regionals/finder/mexico-central-america-2017).

Let's discuss the problems after the contest.

Good luck to all the teams.

Update: Statements (thanks aajjbb).

Update 2: Live Ranking.

Update 3: The contest ended some hours ago, still no final ranking, if anyone gets it, share it please.

Update 4: Final Ranking, congratulations to the winners!!

Update 5: Solutions in Spanish

•
• +13
•

 » 7 months ago, # |   0 Can you re-post this blog when you HAVE problems to discuses ?
 » 7 months ago, # |   0 Will the contest be mirrored online? If yes, where? and if not, do you know when will the problems be available (to submit)?Thank you.
•  » » 7 months ago, # ^ |   +3 as far as I know, there is no mirror contest, the problems are usually posted after the contest starts (PDF), usually the problems are posted to COJ or URI judges some days after the contest.
 » 7 months ago, # | ← Rev. 2 →   +9 statements are Here. Please, do not discuss solutions until the end of the contest.
•  » » 7 months ago, # ^ |   0 The contest is held onsite, so contestants will not have access to the discussion here on codeforces.
•  » » » 7 months ago, # ^ |   0 Okay then.
 » 7 months ago, # |   0 Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).
 » 7 months ago, # |   0 Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).
 » 7 months ago, # | ← Rev. 2 →   +14 Livestream of the competition on youtube https://www.youtube.com/watch?v=SF_HvzWJnwEScoreboard of the caribbean subregion: http://live.uclv.edu.cu/
 » 7 months ago, # |   0 Final Scoreboard: http://bombonera.org/score2017f2/results-secret42/board.html#
 » 7 months ago, # |   0 Can anybody share the solution to problem L?? By the way, the intended solution to problem K was brute force + max-flow??
•  » » 7 months ago, # ^ | ← Rev. 10 →   +18 For problem L: If the number of blocks (not meters) you have to walk in one direction is much smaller than in the other direction, then you have to "kill time" somehow. There are three ways to do this: Keep zigzagging between two adjacent streets near the starting point (maybe in a 5-meter block), or find the nearest 1-meter block (in either side), zigzag there and then go to the end vertex. So for each direction there are only three possible plans, giving nine plans in total. It is possible to try them all.For K, the intended solution was indeed brute-force + maxflow, but there is an easier solution: Create two vertices for each empty cell, one vertex for each cell with a circle, and connect two vertices if the corresponding cells share (exactly) one edge. The solution is Y if and only if this bipartite graph has a perfect matching: If there is a matching, contracting the two vertices corresponding to each empty cell gets you a graph with maximum degree 2 and the correct vertices of degree 1. Conversely, if there is a solution, then there is a matching by just looking at the segments which cross cells on the board.
 » 7 months ago, # |   +3 Statements and inputs/outputs here.http://maratona.ime.usp.br/resultados17/
 » 7 months ago, # |   +8 The problems will be available to submit here: ACM/ICPC LATIN AMERICAN REGIONAL 2017 REPLAY CONTEST
•  » » 7 months ago, # ^ |   0 This contest already finished, so we are not able to submit any problems :(When will the problems be uploaded to some other OJ? Or when will we be able to submit the problems in URI?
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +7 The next monday, november 20 at 13:00 UTC-05, you can submit the problems at http://matcomgrader.com/ There will be a replay of the contest at that time, after that I guess you can also submit the problems Sorry for my english
•  » » » » 7 months ago, # ^ |   0 Okay, that's great! Thank you!
 » 7 months ago, # |   0 Hi! Can anybody share the solution to problem B?? please :(
•  » » 7 months ago, # ^ |   0 You can try to "reverse engineer" the way the string was built. Think about the last typed character, if the current string is s1 s2 ... sn either the last character you typed is sn and it is a consonant or is s1 and it is a vowel. On the first case the string previously was s1 s2 ... sn - 1, on the latter sn ... s3 s2.The trick is that it's impossible to construct a string that starts with a consonant and has a vowel elsewhere and if the string has only consonants there's only way to type it. With this observation even a recursive solution is fast enough. check this solution for more details# Paulo Cezar P. Costa, ICPC-LA 2017, Buggy ICPC #!/usr/bin/env python3 def is_vowel(c): return c in "aeiou" S = input() N = len(S) # we will deconstruct the string trying to track where the bug might have # kicked in but instead of actually changing the string we just use some # variables to represent the current state of the string, we can do that by # keeping the positions of the first and last character of the current string # on the original one.. begin, end, ans = 0, N - 1, 0 # the amount of vowels in the current string is also quite handy vowels = sum(is_vowel(c) for c in S) while True: if begin == end: ans += 1 break # since we are only handling indices and sometimes we'll reverse the string # we need to adjust this delta here to figure out in which direction we are # moving when we remove a character. e.g. if begin > end and we remove a # character from the end we should actually increase end. delta = 1 if begin < end else -1 start_with_vowel = is_vowel(S[begin]) end_with_vowel = is_vowel(S[end]) if not start_with_vowel: # it's impossible to construct a string that starts with a consonant # and has a vowel elsewhere, since every time we add a vowels it goes to # the beginning of the string. on the other hand, if there are no # vowels, the bug would never kick in hence there's only one wayto type # the string (by always adding the consonant to the end) if vowels == 0: ans += 1 break if end_with_vowel: # S starts and ends with a vowel, so there is no choice.. # the vowel at the beginning was actually added last, we need to # reverse the string and remove the vowel from the end, new state is # (end, begin+delta, vowels-1) begin, end, vowels = end, begin + delta, vowels - 1 else: # S starts with a vowel and ends with a consonant, we have two options: # if the vowel was added last, this means the bug kicked in and we need # to reverse the string and remove the vowel from the end, getting into # the state (end, begin+delta, vowels-1). But by doing this we already # know that the new string will not start_with_vowel and this means it # only adds to the number of ways if there are no vowels left if vowels == 1: ans += 1 # otherwise the consonant was added last and we simply remove it and # keep counting begin, end = begin, end - delta print(ans) 
•  » » » 7 months ago, # ^ |   0 Thanks! I go to see.. I try this solution but give me time limit :( #include #include using namespace std; char palabra[100005]; bool vocal(char l){ if(l=='a' or l=='e' or l=='i' or l=='o' or l=='u') return true; else return false; } long long res = 0; void c(int i, int j, char dir){ if(i==j){ res+=1; return; } char letraiz, letrader; if(dir=='i'){ letraiz = palabra[j]; letrader = palabra[i]; }else{ letraiz = palabra[i]; letrader = palabra[j]; } if(vocal(letraiz)){ if(vocal(letrader)){ if(dir=='i'){ c(i, j-1, 'd'); }else{ c(i+1, j, 'i'); } }else{ if(dir=='i'){ c(i+1, j, 'i'); c(i, j-1, 'd'); }else{ c(i+1, j, 'i'); c(i, j-1, 'd'); } } }else{ if(vocal(letrader)){ }else{ if(dir=='i'){ c(i+1, j, 'i'); }else{ c(i, j-1, 'd'); } } } } int main() { // freopen("input.txt", "r", stdin ); scanf("%s",palabra); c(0, strlen(palabra)-1, 'd'); printf("%lld\n", res); return 0; } 
•  » » » » 7 months ago, # ^ | ← Rev. 3 →   0 You can save a lot of recursive calls by using the fact that it's impossible to construct a string that starts with a consonant and has a vowel elsewhere and if the string has only consonants there's only way to type it. I mean, right now you do save a few calls with that empty if(vocal(letrader)) (i.e. when the string start with consonant but ends with vowel) but if you add an extra parameter to your solution with the amount of vowels you can save a lot more. .// Paulo Cezar P. Costa, ICPC-LA 2017, Buggy ICPC #include using namespace std; inline bool is_vowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; } string s; int count(int l, int r, int vowels) { if (l == r) return 1; int dir = l < r ? 1 : -1; if (!is_vowel(s[l])) return vowels ? 0 : 1; if (is_vowel(s[r])) return count(r, l+dir, vowels-1); return count(l, r-dir, vowels) + count(r, l+dir, vowels-1); } int main(int argc, char* argv[]) { ios::sync_with_stdio(false); cin.tie(NULL); cin >> s; int vowels = accumulate(s.begin(), s.end(), 0, [&](int a, char c) { return a + is_vowel(c); }); cout << count(0, s.size()-1, vowels) << "\n"; return 0; } 
 » 7 months ago, # |   +13 My solutions to the problems I solved so farhttps://aleigorithms.wordpress.com/2017/11/14/icpc-latin-american-regional-2017/
 » 7 months ago, # |   +16 The judges shared their solutions here: http://maratona.ime.usp.br/resultados17/presentation_brazil_nopause.pdf It is in portuguese but Google translate or some other tool should to the magic :)
•  » » 7 months ago, # ^ | ← Rev. 2 →   +10 The explanations of problem K has several missing pieces. We need to brute force each possible subset of points to build the bipartite graph which is combinations of 14 in 7 (3432) at most. Also we need to run, not a standard flow, but a flow with lower bound or solve the equivalent circulation problem.Why in the statistic of this problem there are 0 submissions / 0 solutions when 2 teams solve the problems?
•  » » » 7 months ago, # ^ |   +8 Those statistics only consider the results of the brazilian teams before the scoreboard got frozen.
•  » » » 7 months ago, # ^ |   +16 This was the original intended solution (and that's why the number of dots is <= 15), but as you can see on http://codeforces.com/blog/entry/55700?#comment-395003, there's actually an easier solution (the one explained at the slides).
•  » » » » 7 months ago, # ^ |   +10 I didn't notice this solution until now. Actually it is better in complexity, and easier to come up with. I was biased for a similar problem I solved a few years ago when I was learning circulation.