Блог пользователя k790alex

Автор k790alex, 6 лет назад, По-английски

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
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

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

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    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.

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Statements and inputs/outputs here.

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

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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;
      }
      
      • »
        »
        »
        »
        6 лет назад, # ^ |
        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.

        .
»
6 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
»
6 лет назад, # |
  Проголосовать: нравится +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 :)

  • »
    »
    6 лет назад, # ^ |
    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?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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).

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +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.