PrinceOfPersia's blog

Crypto Cup 1.0
By PrinceOfPersia, 10 years ago, In English

Hello everyone.

Soon, On the night after the Halloween, there will be a Codeforces gym contest, named Crypto cup 1.0.

Like its name, it's a cryptography contest and for all problems, you are given some sample encryptions encrypted using a certain algorithm and you have to write a program to decrypt the given messages.

There will be 18 problems and you have 6:30 hours to solve them. I hope it will be interesting.

Problems are prepared by me (PrinceOfPersia) and tested by Damon also thanks HosseinYousefi for editing problem statements.

For practicing cryptography, we recommend SecutiryOverRide's cryptography challenges.

Also, this round needs a little Algorithm and CS knowledge.Don't forget to pay attention to problem's titles, they might be helpful ;)

Currently, problems are being prepared, so you're unable to see the contest in gym contest list yet.

Problems are in decreasing order of difficulty.

UPD: Duration has been increased by half an hour, now it's 6:30 .

UPD2: Please note that contest will be held on November 1st, because it had overlap with Shahid Beheshti University ACM.

UPD3: Now it's in the Gym contests list.

UPD4: Registration is open.

UPD5: Contest is over.

I hope you enjoyed the problems.

Congratulation to the winners who solved all the problems :

  1. I_love_Hoang_Yen

  2. Team Flareon : Localhost, DiEvAl, Visconte

  3. kennethsnow

  4. niklasb

  5. 135678942570

Complete standing

Be aware, our standard rounds are coming... ;)

Announcement of Crypto Cup 1.0
  • Vote: I like it
  • +132
  • Vote: I do not like it

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

Cool, crypto CTF at CF =)

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

how to patipate,can it held on webstie

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

I hope it will be a rated event for both divisions. :D Finally I will get to code Caesar cypher(Rot13) and other cool algorithms like transposition, substitution(Monoalphabetic && Polyalphabetic) in reverse(decryption). m = D{key}(m')

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

what are the stars near contests in gym?

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

CS knowledge like Counter Strike knowledge ? :D

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

well this will be an interesting way to get rid of my boredom(since there is a lot of time before the new contest)

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

the interesting picture :>

I hope the questions will be interesting too!! :)

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

nice,and could you put the Shahid Beheshti University ACM into the gyms too,thanks

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

im searching for a team is there any?

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

Happy Halloween :)

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

very nice problem I love them !:)

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

ridam 2 in c0nteste2n baw....... hadeAghal nmiriDd b Sme reza...... tnks :x

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

    please write in English you are very Rude .....!

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

it was really good but the time of contest was so a lot and i resigned from coding after 2 hours

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

Some violet colored participant like to ask: can you give me code of N or B please ? here is code of H ;) : ...

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

I_love_Hoang_Yen, kennethsnow and 135678942570 are first to get the full-score.
Congratulations!

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

What is the solution of 7th test case in task G?

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

Problem G case 7, "use some bazinga order" we (non-native speaker) just guess it is an amazing answer. :-)

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

can somebody tell, how to solve N?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 5   Vote: I like it +13 Vote: I do not like it

    ** spoiler alert **

    If you really want to see solution, click on Rev until you see it.

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

      Thanks, I observed it for 1 hour and didn't find it:( Then I left this contest.

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

      I don’t understand how you can just guess the 12 unknown patterns.

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

        Spoiler (See Revisions)

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

          Sorry, I don’t see what you’re talking about. You’re just reciting the input data and saying “look, there’s a pattern”, which is not very helpful. There certainly is a pattern (as I describe in my answer), but you don’t even attempt to explain what it is. As for this particular thread, my very point is that finding a pattern is, you know, a bit different from guessing.

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

            In this contest you sometimes just had to use your intuition and make educated guesses. Also see other tasks like L or G. Most of the sequence here was known and a good guess for the pattern was +1 +7 +1 +7 +1 ...

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

    spoiller alert

    from test cases, you can see a pattern going on. for instance, 0 is a, 8 is c, 16 is e, 17 is f, 25 is 5, 4 is i... and so on.

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

    Permute the bits in each number and treat it as an alphabet index.

    The first thing to notice is that the numbers are all smaller than 32 and that the task description guarantees that they all correspond to letters. It seems that the numbers are (in some way transformed) alphabet indices.

    At this point, we can compare some encoded and decoded indices. We can see that that ‘a’ is zero both encoded and decoded if you take alphabet indices to start at zero (which we can now try to assume), and in other indices bits seem to move around. We should also take a look at the problem name: it seems like it has the first letter in the middle… in fact, it seems like all the letters are shuffled.

    Together, this leads to the guess that perhaps the encryption just permutes the bits in the binary representation of the index. This permutation can be reconstructed from the sample data; a quick way is to start with the indices that have only a single bit set, namely, 4, 8 and 16 (because we can immediately see where the permutation moves that bit). We do indeed get a single permutation that holds for all of the sample data, and so the problem is solved.

    The problem name is a shuffled “Permutation”.

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

      used wordlist and regex

      p[letters]{10}

      to guess the word :D

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

In G, when I saw "lbciutrps", I immediately know that it is "strip club".. If my girlfriend knows, she would be mad ~~

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

    I wonder why you immediately know it. Is it your favourite word? Does this word always appear in your mind? :P

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

What is test case #4 in problem H ? (Can't find mistake in my code/logic).

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

Testcase #4 for H was weird: My Python program failed when it assumed the input to be formatted exactly as specified. Only after I modified the read function to ignore whitespace did it pass. I saw that other people had the same problem (runtime error on test 4) and I asked a clarifying question, but no reaction from the judges. I feel like that testcase should have been fixed and the solutions rejudged...

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

    My Perl program reads exactly formatted input too. Now, after I stripped lines from spaces + ignored empty lines, my code got AC too.

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

    Ah, so that was the problem! I rewrote my Python solution in C.

    Actually, my Python implementation should tolerate whitespace on lines… Were the lines split incorrectly? Edit: right; it seems from your comments that there were empty lines.

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

Thank you for the problems.

I see that some participants (including me) have problems with H's test 4. What is that specific about it?

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

    It's completely random :D

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

      Can't you agree that test #4 is incorrect? — has excessive input which is not defined in the section "input"? Empty lines they are. Can't you agree that there exist some test cases which has a statement's logic collision? If take first line of input twenty six zeroes, then 1) if follow "input" section — there must follow zero lines, 2) if follow upper statement — then there must follow more than zero lines. If contestant strictly follows what is written in "input" section, he knows how much lines must input include, and he can read all lines till the end of input file. If there are excessive — non declared lines — it's obvious that they can affect result of program. Others, who read not all lines of input, for example if they count from the first input line how much lines should follow, then use only them, but not use lines which follows later and which are not declared.

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

How to solve M?

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

    Letters with odd ASCII -> 191 - theirnumberinalphabet
    Letters with even ASCII -> 189 - theirnumberinalphabet

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

    Spoiler on revisions and code on ideone (http://ideone.com/G14Imp)

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

    XOR each byte with 222.

    One of the common symbols used to denote XOR in mathematics is the circled plus , which is hinted at in the problem name. (In fact, the TeX code for is literally \oplus.) The value 222 is easily determined from the sample data.

    In many programming languages including C, C++, C#, D, Java, Python, Ruby, Perl, PHP and JavaScript, XOR is performed by the ^ operator. Some others, such as Pascal and Haskell, provide an xor keyword or function.

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

Is any editorial-like thing available?

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

Interseting contest indeed. Without teammates,after solving 11 problems,I got stuck and went to bed(so sad) Will there be official/unofficial Editorial for this contest?

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

why we can't see others code for the problems that we didn't solve?
...i want to learn something new..

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

Funny contest!

Will there be Crypto Cup 2.0 in the future?

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

theme of the contest — search (binary? ternary? Web!)

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

Can someone provide some hint on how to use the tree from task P to decode? I can construct the tree from the Prufer sequence but not finding how to use that information to transpose the string.

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

    Root the tree (root is vertex 1), then sort the adjacency list of each vertex in increasing order.Then assign a character to each vertex of the tree, one by one using DFS (by starting time), ci is the character assigned to vertex i (Find the DFS order of the tree and call it b1, b2, ..., bn, so cbi = si). Then find BFS order of the tree (first all vertexes of first level, the second level,...), it is p1, p2, ..., pn. Answer is : cp1cp2...cpn .

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

Finally your standard round is coming!

→ Reply