k790alex's blog

By k790alex, 10 days ago, In English,

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!!

 
 
 
 
  • Vote: I like it  
  • +13
  • Vote: I do not like it  

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you re-post this blog when you HAVE problems to discuses ?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
9 days ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

statements are Here. Please, do not discuss solutions until the end of the contest.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The contest is held onsite, so contestants will not have access to the discussion here on codeforces.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).

»
9 days ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

Livestream of the competition on youtube https://www.youtube.com/watch?v=SF_HvzWJnwE

Scoreboard of the caribbean subregion: http://live.uclv.edu.cu/

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody share the solution to problem L?? By the way, the intended solution to problem K was brute force + max-flow??

  • »
    »
    7 days ago, # ^ |
    Rev. 10   Vote: I like it +18 Vote: I do not like it

    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 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Statements and inputs/outputs here.

http://maratona.ime.usp.br/resultados17/

»
7 days ago, # |
  Vote: I like it +8 Vote: I do not like it

The problems will be available to submit here: ACM/ICPC LATIN AMERICAN REGIONAL 2017 REPLAY CONTEST

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      2 days ago, # ^ |
      Rev. 2   Vote: I like it +7 Vote: I do not like it

      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

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi! Can anybody share the solution to problem B?? please :(

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! I go to see.. I try this solution but give me time limit :(

      #include <stdio.h>
      #include <string.h>
      
      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;
      }
      
      • »
        »
        »
        »
        4 days ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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.

        .
»
6 days ago, # |
  Vote: I like it +13 Vote: I do not like it
»
4 days ago, # |
  Vote: I like it +16 Vote: I do not like it

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 :)

  • »
    »
    4 days ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    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?

    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Those statistics only consider the results of the brazilian teams before the scoreboard got frozen.

    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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).

      • »
        »
        »
        »
        4 days ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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.