MikeMirzayanov's blog

2014-2015 CT S02E11: Codeforces Trainings Season 2 Episode 11
By MikeMirzayanov, 10 years ago, translation, In English

Welcome to 2014-2015 CT S02E11: Codeforces Trainings Season 2 Episode 11 (2011-2012 ACM-ICPC Latin American Regional Contest + Extended). The training duration is 5 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

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

Comments Comments (25)
| Write comment?
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Will you or someone else answer the questions about the problems? Last gym I have a question but no one answer in the end...

→ Reply
»
10 years ago, # |
  Vote: I like it +14 Vote: I do not like it

thanks MikeMirzayanov for all contest in Gym :)

→ Reply
»
10 years ago, # |
  Vote: I like it -18 Vote: I do not like it

not able to download problems statement

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

link for download

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have to create a trie for the portuguese words and a trie for the reversed spanish words, then, the number of words will be: (states of port trie-1) * (states of span trie-1)-(repeated words).

    You can find the repeated words by travessing both tries.

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

      I had a similar solution where I traversed the Portuguese trie, and if a node didn't have an edge for a letter C, then I added the number of Spanish suffixes starting with letter C to the answer (which can be easily computed by going through Spanish trie once). The logic is that all resulting words will be identified by their longest Portuguese prefix. The only exception are words that are actual prefixes of Portuguese words, but those are easy to deal with by making sure there is a Spanish word ending in its last letter.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How is problem J solved?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the problems B and H?

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

    To solve problem H you have to realize that for the condition to be held, the path must consist of bridges only. After you generate the graph of the bridges, the queries can be replaced by the question: Do S and T belong to the same component?

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

    For B, rotate the pyramid so that the top is in (0,0) and rows become diagonals. Now if you took the ball at (i,j), you also need to take all balls in the rectangle from (0,0) to (i,j). Now the problem can be solved with simple DP that answers the question for rows starting from i, and columns up to j.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry but I'm a bit sucked. Can you provide the dp state representation and transition? thanks

      → Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it -13 Vote: I do not like it

F in all tests in problem C doesn't exceed 100, what is very strange due to statement 105 border =)

UPD: Sorry, but that was lie. Code with assert(f < 100 * 1000) gave me RE2. The mistake was in bad-showed test.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

http://codeforces.net/contest/475/submission/8883485

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I got TLE on test 2 on problem A? I used O(n) solution.

http://codeforces.net/gym/100540/submission/8871278

→ Reply