artie's blog

Google Code Jam 2014, round 1C
By artie, 11 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

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

Any idea for problem C ?

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

    I was thinking, maybe it's always optimal to place the stones in a 'rectangle without corners'. But then, perhaps, the question is too easy..

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

      However, according to the Russian discussion, it is true))

      → Reply
»
11 years ago, # |
← 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
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    duplicate post

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← 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
    • »
      »
      »
      11 years ago, # ^ |
        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
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, I got it and to make up for the mess wrote some hints for a possible solution

        → Reply
    • »
      »
      »
      11 years ago, # ^ |
        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
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← 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
  • »
    »
    11 years ago, # ^ |
      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
»
11 years ago, # |
  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