k790alex's blog

By k790alex, 7 years 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!!

Update 5: Solutions in Spanish

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

| Write comment?
»
7 years 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.

  • »
    »
    7 years 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.

»
7 years 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.

  • »
    »
    7 years 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.

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

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

»
7 years 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/

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

Statements and inputs/outputs here.

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

»
7 years 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

  • »
    »
    7 years 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?

    • »
      »
      »
      7 years 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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 years 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
    • »
      »
      »
      7 years 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;
      }
      
      • »
        »
        »
        »
        7 years 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.

        .
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it
»
7 years 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 :)

  • »
    »
    7 years 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?

    • »
      »
      »
      7 years 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.

    • »
      »
      »
      7 years 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.net/blog/entry/55700?#comment-395003, there's actually an easier solution (the one explained at the slides).

      • »
        »
        »
        »
        7 years 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.