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

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

My first blog post, so exciting ^_^

Ehm, the Internet Problem Solving Contest will take place on Saturday 8.6.2013. The practice session lasts 24 hours and ends at 8:00 AM (UTC), while the contest itself starts at 10:00 AM and lasts 5 hours.

The tasks have similar format to CodeJam ones — there is an easy and a hard subtask for every problem, you're given the input data for each subtask and have to submit the output in the format required. Except there's no time limit between downloading the input and submitting, and you aren't required to submit your code (in fact, not even to code anything :D). But there are limits on the number of submissions for each problem!

The problemset consists of standard algorithmic tasks of varying difficulty, as well as some unusual tasks (like a task without a problem statement), tasks touching what you might experience in real life, or interactive ones, where you get feedback for your output and base your next output on this feedback.

The contest uses ACM-ICPC scoring rules, and every subtask is worth 1 point.

There are 2 divisions: open and secondary-school. There is also a separate scoreboard for single-person teams in each division.

I'm sure the contest will be great. Don't miss it!

EDIT: If possible, send a postcard to the organizers. Apart from earning -60 penalty minutes (in case it arrives before the contest), you're enlarging their collection :D

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

»
12 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Just in case, if somebody miss the direct link — http://ipsc.ksp.sk/

»
12 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Actually, postcard will deduct 60 minutes (and not earn 20)

This year due to Russian post meltdown we would not send a postcard

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    WTF did I just write... yeah, of course. Edited. Still, it'd be nice to have as unusual postcards as possible :D

»
12 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Practice problem P2 is fantastic! Had a lot of fun solving it )))

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Even practice tour seems to be pretty challening! Can't wait for the main contest!

»
12 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Is anybody facing the issue with http://ipsc.ksp.sk/ ?

It looks like it crashed, I can't even ping it

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

is the website down?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Right. I wonder what happened... CF anyone? :D I'm sure it's temporary.

UPD: It's working again.

»
12 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

До начала совсем немного, а я и cerealguy ищем третьего в команду на IPSC

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    О, классно. А каким критериям он должен удовлетворять (язык, местоположение)?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Язык — любой. Местоположение — где угодно, с доступом в интернет:)

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Это хорошо. Тогда я могу, у меня вообще команды нет. Если вакансия еще открыта)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Участвуйте вдвоем. У нас тоже команда из двух человек.

»
12 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Сайт прилег?

»
12 лет назад, # |
  Проголосовать: нравится +71 Проголосовать: не нравится

How to solve H2?

  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    Send HTTP request, with Accept: text/tattoo and play a little game with monster :) Pretty easy.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    Send an HTTP request to the page using the HEAD method. Actually I haven’t even tried other methods, so maybe any method works. Anyway, here’s an example (with extraneous headers removed for brevity):

    HEAD /2013/real/problems/h.html HTTP/1.1
    Host: ipsc.ksp.sk
    
    HTTP/1.1 200 OK
    H2: A blue monster approaches you and says: "I know the word you need for H2. But I won't talk to you unless you feed me first. I'm in the mood for some dessert... its name doesn't matter, but it must contain chocolate."
    

    Send a cookie with ‘chocolate’ in the value (if it doesn’t contain ‘chocolate’, you get the same response as before):

    HEAD /2013/real/problems/h.html HTTP/1.1
    Host: ipsc.ksp.sk
    Cookie: name=chocolate
    
    HTTP/1.1 200 OK
    H2: "Yum! All right, if you answer this question, and do it quickly, I'll tell you the answer for H2."
    H2-Question: How much is 665 plus 192?
    H2-Answer: (your answer)
    

    You need to resubmit the request with an additional request header H2-Answer: 857. If you try to answer by hand, you’ll get something like:

    H2: "Too slow! Try again!"
    H2-Question: How much is 265 plus 29?
    H2-Answer: (your answer)
    

    So you write a program and get:

    H2: "Correct! The word you're looking for is CLASSIFICATION."
    
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      In fact, one can submit H2-Answer by hand, but it would be too slow to type the whole request by hand. Using a tool like curl would do.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    First, we make a HTTP HEAD (or HTTP GET) request and read the head of the response. It is the “head of the slave”, because the “slave” is defined here: “problem statement is the slave we sent to you, carrying the secret message”.

    sh$ curl -I ipsc.ksp.sk/2013/real/problems/h.html
    HTTP/1.1 200 OK
    <...>
    H2: A blue monster approaches you and says: "I know the word you need for H2. But I won't talk to you unless you feed me first. I'm in the mood for some dessert... its name doesn't matter, but it must contain chocolate."
    

    A “dessert with chocolate” is cookies, or, in our case, HTTP cookies. The name of a cookie doesn’t matter, but the cookie itself must contain the “chocolate” substring.

    sh$ curl -b 'some=bbbchocolateaa' -I ipsc.ksp.sk/2013/real/problems/h.html
    HTTP/1.1 200 OK
    <...>
    H2: "Yum! All right, if you answer this question, and do it quickly, I'll tell you the answer for H2."
    H2-Question: How much is 93 plus 76?
    H2-Answer: (your answer)
    

    Then we have to compute the answer quickly enough and pass it in H2-Answer HTTP header. If we don’t do it quickly, the response will contain the next question. Otherwise, it tells the correct answer.

    sh$ curl -H 'H2-Answer: 169' -I ipsc.ksp.sk/2013/real/problems/h.html
    <...>
    H2: "Correct! The word you're looking for is CLASSIFICATION."
    
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    Using wget -S which prints the server response with monster message. Later setting desired headers in this way: wget "--header=Cookie: dessert=chocolate".

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Shame on team. We couldn't solve J1/J2 — it looks like my boolean algebra lessons made no sense to me. Could anybody explain it?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Did anyone else get this for C1?

CHANGE 1607055075 TO 0

then

GE 1704106159 TO 1

then

GE 1 TO 1

»
12 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Preliminary version of the solution booklet has been published: http://foja.dcs.fmph.uniba.sk/ipsc/BOOKLET.pdf

»
12 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

Am I the only one who googling this thing "tattooed by Histiaeus on the slave's head" and read some historical paper just want to know what word that writen in Histiaeus slave's head because you think the answer is like that ?

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve D?

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I'm sorry, that was not in English. And now my English is not good.

    d1. dp[mask] — — maximal answer for permutation of letters in mask answer is final position of pointer in greedy algorithm of collecting letters from string. if dp[mask] <= n, all is OK.

    d2 is interesting for me too.