Блог пользователя abody97

Автор abody97, 13 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
ok i got it ,thanks

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
tutorial is something else
»
12 лет назад, # |
Rev. 4   Проголосовать: нравится -8 Проголосовать: не нравится

Just testing.