abody97's blog

TC SRM 516 Div. 2 Tutorial / Editorial
By abody97, 13 years ago, In English

Hi! Although you might not want to hear from someone with such a rating, well, give me a chance, I hope I do better in upcoming rounds :D
1) The 250-point problem: ( Link )
In this problem, the main thing to notice is that the sequence is either of the form "xo" or "ox" repeated n / 2 times. Thus, we can test the known letters and see which type they match, and print the one that matches.
2) The 500-point problem: ( Link )
Here, the most important note is that if x XOR y = z then y = x XOR z. So, we can try all pairs of a plaintext XOR a ciphertext to be key, then check if it's valid. A key is considered valid if, for every ciphertext, there exists a plaintext which when encrypted using the current key gives this same ciphertext.
3) The 1000-point problem: ( Link )
First, you need to read the statement carefully, as it clearly states that the characters in the original message are distinct, and thus the characters in each subsequence are distinct. Now, we can consider the given subsequences as "letter x is before y" relations and put those as edges in a graph. Note that if you're given a subsequence x1, x2, ..., xn, then for each i, xi comes before all xj : i < j <= n. Now that we have the graph, all we have to do is a topological sort. Since we're being asked for the lexicographically minimum string, among the zero-in-degree nodes, we choose the one that corresponds to the lexicographically minimum character.
I hope the explanations were clear, if you notice anything wrong or vague, please tell me :D

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
The 1000-point problem:
can you explain how you created the graph to handle case like
{"cz", "za", "xy"}
the answer would be
"cxyza"

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

    First of all, the subsequence "cz" tells us that 'c' comes before 'z',"za" tells us that 'z' comes before 'a' and "xy" means 'x' comes before 'y'. So the edges are: c -> z, z -> a, and x -> y. Now, the topological sort would do something like this:
    - We have 2 two nodes with 0 in-degree, which are 'c' and 'x'. We choose the lexicographically smaller one, which is 'c'. We delete all edges coming out of 'c', ( c -> z ).
    - We have 2 nodes with 0 in-degree,  which are 'x' and 'z'. We also choose the smaller one, which is 'x'. We delete all edges coming out of 'x', ( x -> y ).
    - We have 2 nodes with 0 in-degree, which are 'z' and 'y'. We choose the smaller one, 'y', and delete edges coming out of it, ( none in this case ).
    - We have 1 node with 0 in-degree, which is 'z'. We choose it and delete edges coming out of it, ( z -> a ).
    - We have 1 node with 0 in-degree, which is 'a'. We choose it and delete edges coming out of it ( none ).
    - We're done, as we chose all nodes.
    - The resulting string is: "cxyza".
    Hope it's clear :D
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
ok i got it ,thanks

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
tutorial is something else
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I don't know what you mean, really
    What do you mean by "something else"?
    → Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it -8 Vote: I do not like it

Just testing.

→ Reply