k790alex's blog

Solutions to The 2015 ACM-ICPC Caribbean Local Contests (Real contest) and Gran Premio de México & Centroamérica Fase III (2015/10/26)
By k790alex, history, 9 years ago, In English

http://halexv.blogspot.mx/2015/10/the-2015-acm-icpc-caribbean-local.html

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

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

I took place in that contest and I want to share with you my teammate approach to solve problem C, the idea was to count the number of sides of each shape counting their corners. The numbers of sides was the same as the number of corners. I think it wasn't a lot of code and the idea was simple.

BTW, you refer to problem G (Fear of the Dark) like no an easy problem. I am agree with you, but you only need to know a heavylight and thats all, it is a complex (algo/datastructure) and I dislike the way it was presented in the contest. The teams that realise(know) that it was a HLD(heavy-light-decomposition) just solve it. It was a great disadvantage for those who doesn't know HLD.

Beside that I liked the contest, and I am looking forward to take place in the next one

EDIT: I noticed now you solved problem H using backtracking. It can be solved using combinatorics with lower complexity.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Can you describe more the approach for solving problem C? How do you define a corner? How is supposed to work for a case like this: OOOOO

    About problem G, yes, it is straightforward if you know what is required but with little experience with these structures is not so easy to type a bug-free code, being the code so long is still harder to debug it, I agree with you about is a disadvantage for teams without knowledge about HLD and is a disadvantage for Java teams too because is a pain to get AC having the required knowledge, you have to increase the default stack size using a new Thread to avoid Runtime Error, fast input and care with things non algorithmic related to get a well optimized code, this takes lots of time.

    I liked the contest too, it was interesting and no so hard.

    About problem H, backtracking was the first idea coming to me and the complexity was acceptable, can you describe the combinatorics solution?

    Thanks.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      About problem C the idea to detect sides (as I said before) was to count corners. First a single square could be several corners at the same time

        12
1 OOO
2 .O.

      In this sample square at position (1;1) represents two corners of the shape, Imagine that you want to check if a single cell could be a corner in one of the four directions: NW, NE, SW, SE (Directions are diagonal) The amazing idea of my teammate was the way to check that: (x;y) is corner in direction d(remember that d is a diagonal) <=> if (x;y) belongs to one shape(it isn't empty) and (x+dx[d];y+dy[d]) is empty and (x+dx[d];y) == (x;y+dy[d]) ie, you need to check if the cell in the diagonal is empty and the common neighbours cells between current cell and the one in the diagonal have the same state(are both empties or filled). For each corner you should add 2 to the total side, but then notice that you have counted each side twice (one per corner) so dividing the answer by 2 it turns out that the answer = total corners.

      For problem H, the answer was: 2 * (C(o + e, o) * 5^(o + e) — C(o + e — 1, o — 1) * 5^(o + e — 1)) where C(a, b) = a! / (b! * (a — b)!) 2 times: because negative numbers. The substraction must be done only if o > 0, because you don't need to count numbers that start with zero(0), I remember that there was a tricky case in which we fail, it was something like 1 0, because number 0 should be counted, and the answer was 9.

      → Reply