artie's blog

Google Code Jam 2014, round 1C
By artie, 12 years ago, translation, In English

If there are people who did not advanced yet then welcome — it will be your last chance to advance to round 2
Place and time.
It is only 6 hours left till the start!

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

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

Any idea for problem C ?

→ Reply
»
12 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

can anyone give a hint on how to solve problem B?
P.S. i could solve C-small (with a solution, probably the most complex solution that solved it correctly :P), but not B-small!

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

    duplicate post

    → Reply
  • »
    »
    12 years ago, hide # ^ |
    ← Rev. 7  
    Vote: I like it +3 Vote: I do not like it

    Since I'm in the mood of writing hints, here's some for the actual gcj problem:

    1. (Small input) N <= 10, sounds like a good problem for an O(N! * something) solution!
    2. Build a graph with letters as its vertices. If you have a letter 'x' following a letter 'y' in a string, add an edge from y to x.
    3. What if there are cycles in this graph?
    4. If you are told that the answer is not zero, how would you calculate it?
    → Reply
    • »
      »
      »
      12 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      i was asking about GCJ round 1C, which took place earlier today.
      not about CF round 245! :)

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

      I thought about this approach. Won't it involve finding the number of Eulerian paths in the graph so formed? (Another hint in this regard would be much appreciated)

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

        Again, a stronger hint in edit.

        1. Is the absence of cycles enough for the answer to be nonzero or should you forbid something else?
        → Reply
  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    As you asked, a hint: build a directed graph on letters (for example, if there goes letter b after a in some string, so you should add an edge from a to b). Ask questions (or for complete idea of solution) if needed.

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

WTF is happening with scoreboard? Today I found myself 6 places lower than yesterday morning. It didn't make me out of Round 2, but still is interesting.

→ Reply