aropan's blog

Codeforces Beta Round #92
By aropan, 13 years ago, translation, In English

"Tryam" to everyone!

I am an authors of the today's contest. First of all I want to thank Artem Rakhov [RAD] (thanks to him, you'll understand my problems) and Maria Belova [Delinur] (those who know my English level will understand a huge of my thanks). Also thanks to everyone staff for the wonderful of the codeforces system. And also thanks to Sergei Tarasov [Seryi] and Andrey Tkachenko [Tkach1024] for ideas generating and testing.

Good luck and have fun.

Today, a breakdown of score will be slightly different from the standard - for the second division is 500-1000-2000-2000-2500 and 1000-1000-1500-2000-2500 for the first.

And one more, but certainly pleasant news - register ends exactly at the start of the round.

Analysis problem.


How it was.
At 19:35 Moscow time reported that in pretests for 123B - Squares have errors (a special thank to him). Indeed, a special case was not considered (a = 1, b! = 1 and symmetric to it). We have made decision to exclude tests covered by this case. There were a lot of such tests in pretests. Test generator has been fixed, and all tests were changed. After that all submits have been rejudged. As a result some submits with WA verdict could get the AC and vice versa.

What we have now.
We believe that the round should be rating. But if the situation with the problem 123B - Squares is strongly influenced to you, you can send an appeal with the evidence of this in the form of a personal message to RAD no later than 11pm on November 4. We can either do this round unrated for you or remove excess submits.
At the end of the system testing rating will be updated. If you have no appeals, it will be your final rating.

Sorry for the inconvenience.

  • Vote: I like it
  • +79
  • Vote: I do not like it

Comments Comments (90)
| Write comment?
13 years ago, # |
← Rev. 2   Vote: I like it +30 Vote: I do not like it

In which language this word "Tryam"  belong to i think it's meaning something like "Hello" ,i tried to use google translator but it doesn't know it :)

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it
    Russian. This word doesn't mean anything, it's interjection.
    There is a very popular Soviet cartoon named "Tryam! Hello!" :)
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    Seems to be music onomatopoeia, like [trɐm]-[pam]-[pam], [pam]-[pam]-[pam], etc.

    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I fear difficult problem statements. :P But hope for excellent ones. :)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Looks like this round will be tougher than usual. So, be careful...
:)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    I think it is possible that all problems except div2-C/div1-A are easier than usual, though it's not too likely.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Server is very sloooow...
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Server hiccups! :)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Are we really starting in one minute?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I suggest this round be unrated.. 
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    I think the better option would be voting as in round 58 but not making it unrated.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    I guess that it isn't reasonable
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it
      It is. Statement of problem had changed during contest, as well as correct solution (that correctly handles a == 1 || b == 1) not passing pretests until deep into the contest
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    why? only few lagged in the beginning...
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Essential change of problem statement and pretests
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Totally agree((
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    that's why you've made 19 unsuccessful chellenges? :)
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Wow! 19 failed challenges! Is that a new record?
      → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    looks like people who had a better contest than they usually do, is saying to make it rated(not everyone). But isn't it justified to make the a contest unrated when you change the problem statement? You never know how that has affected somebody.
     
    Note : Making it rated/unrated is not going to change my rating massively, maybe that's why I'm neutral :P

    → Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Unfortunately I missed the round, but I'm looking forward to the editorials :)
→ Reply
13 years ago, # |
  Vote: I like it +31 Vote: I do not like it
Sorry to say, but this is very bad contest - no original ideas involved, just standard problems with some obious addons. B had some potential, but only with corner case (a = 1, b != 1)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it
    I agree that there were no highly original problems (and they are very difficult to come up with) but it is a contest between participants, not a contest for the best problems. Sure, it had more coding to it than usually but in my opinion it is not that bad .. once in a while.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +75 Vote: I do not like it
    Yeah, let's lose some karma :)

    I agree.

    Problem C:
    a simple idea + standard problem. Implementing solution for standard problem takes much more time than inventing the idea.

    Problem D:
    a simple idea + standard problem. And an awful statement. "We'll find a list of such pairs of numbers for which the corresponding substrings of string x are equal to string y. Let's sort this list of pairs according to the pair's first number's increasing. The value of function F(x, y) equals the number of non-empty continuous sequences in the list." Seriously? What's the point in encrypting n(n+1)/2 that way? I've spent several minutes trying to convince myself what "continuous" means (I've used the Russian statement, but the English translation is good, so the statement is equally awful), I couldn't believe this long paragraph is just about n(n+1)/2.

    Problem E:
    a nice, no so easy idea - but still with a tedious standard problem after it! Why 100000? Why not 5000?

    I'm sorry for being so negative, I hope you understand it's just my impressions. See http://www.mit.edu/~jcb/tact.html
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      First Time to see Petr Comments on Problems Ideas :)
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it
      what is "karma" ?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Read about it here:
        http://en.wikipedia.org/wiki/Karma

        In the context Petr used it, it's basically the same idea as saying "bad luck in the future". In other words, it could potentailly be bad luck to criticize a problem writer. That bad luck, or "bad karma" may affect you negatively in the future in the form of poor contest performances, or other such things.

        It's the idea that whatever you do comes back to you in the future. Do good, it will come back to you, do bad, it also will come back to you. So it's better to do good, if you can :).
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it
          I think Petr meant contribution as on a more popular IT Russian site habrahabr same thing is called karma
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it
            You are probably right, as I am not very familiar with Russian sites :).
            → Reply
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Will A (div.1) pass the system tests if I don't account for uppercase letters?
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    In the problem statement you can see this phrase "The only line contains the initial string s, consisting of small Latin letters"

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I use Russian ) There was "состоящая из строчных букв латинского алфавита" , which I think doesn't explicitly tell you whether those are upper/lower-case letters. 
      → Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
I'm observing div2 solutions for B written in python that pass with 980 ms and don't differ much from mine which TL-ed... Anyway, for me the contest was rather challenging though not so creative. Looking forward to the editorial.
→ Reply
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
There was a mistake in the note of A(div1), it puzzled me for a long time.
→ Reply
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Don't make it unrated!
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yeah it should be rated at least for div2
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Egor's earlier point ("Essential change of problem statement and pretests") holds for div 2 as well because that same problem he referred to was shared across divisions.

      So div 2 people could have been affected by that same issue, so it wouldn't make sense to rate the contest for div 2 and not rate it for div 1.

      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I know that same problem was shared across divisions, but I think that in div2 not much people have had approached that problem before changes were made.
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it
          Good point, but the contest needs to be fair for everyone, not just the majority of competitors. By the way, I'd like to see it rated as well, but not if it means the result would be unfair for other competitors.

          I do remember seeing that some early submissions were made for D, but I can't say for sure if they were made before or after the announcement.

          So if nobody was affected, then I think your point is valid.
          → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How that small solution works for problem Div-2-D ?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Admins/problemsetters please let us know if this round is rated or unrated. I think it should be rated.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    it will be rated, it's written in russian version of the post

    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    but you can make an appeal by sending a mail to RAD
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    in russian version:
    "Мы считаем, что раунд должен быть рейтинговым. Но если ситуация с задачей 123B - Клетки сильно на вас повлияла, вы можете подать апелляцию с доказательствами этого в виде личного сообщению RAD’у до 23:00 4 ноября. Мы можем либо сделать этот раунд нерейтинговым для вас, либо убрать лишние посылки."

    It means(shortly):
    "    If you want round to be unrated, and problem 125B-Squares made big changes in your points, you should apeal to RAD until that time."

    Sorry for bad english
    → Reply
13 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

 If someone wants this round to be rated, let him have it. There were problems, statement and tests were changed so this round should be unrated. Let's consider Egor's solution for problem B. He has the last submission skipped, which is accepted. Instead his earlier submission is taken into account, which fails. It's a joke, unrate this round.

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

    Sorry, but I just can't imagine. Statement was changed 35 minutes after the contest start. Tests were also changed. Status of some solutions were changed (someone was allowed to hack earlier than he should, someone lost time, someone made wrong hack). The judging is ridiculous (look above) and you still want to make this round rated, with option to write some strange appeals and made changes by hand - unbelievable.

    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    And what's the difference between this situation and betaround 90, when authors forgot about one special case too? That round was unrated.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks to cf, they've taken a good and fair decision
→ Reply
13 years ago, # |
  Vote: I like it +15 Vote: I do not like it
When will the rating update? It seems that round is not unrated but I can't see any updates.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I managed to fail problem A because my primes array is 100 not 1000 as I wanted. And the correct version with only one extra character works ...
Do you usually test your problems on big inputs to at least make sure that it won't crash? I mean make some random string of 1000 chars for example and just check whether your code will work. Or you don't do it because it's a time waste?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    some advanced coders can write right solutions without testing it.
    But we are violet and should be very carefull! If you do not test, you take a big risk
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      ... and we are not violet now!
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Wow, you had a great round I see. Congratulations! 

        Ah, I wish I didn't make that stupid bug... It's not my biggest fail though. Much bigger fail was when I didn't manage to solve the easiest problem from the last day of the Ukrainian team selection test to IMO and I was out of the team, placing 7 (the team has 6 members). After each of the previous days I was in the team, however that round changed everything. I and the guy who placed 6 where sitting next to each other at the appeals stage, there was a difference of 1 point between us (in his favor) and I simply couldn't do anything ...

        However, another guy from Lviv fucked up even more at the team selection test of 2008, I guess. The jury gave him full points for the solution that had a little trick in it and was in fact wrong. 
        There was a tough competition that year and he was placing 4-th with person placing 7-th lacking 5 or 6 points to him. During some break (before the results announcement) he discussed his solution with other member from Lviv (who was definitely in the team already, I think he was 1st or 2nd) and they found a bug in that solution. Unfortunately, the person who placed 7 heard that (
        And when the results were announced, he surprisingly saw he has full points for that problem (obviously he didn't complain). The appeal phase was over, the team members named (he was among them) and everybody was about to leave. And here is a quote from that unlucky person (from the time he was telling me this story): "I was already packing my stuff when I saw the person who placed 7th in the corridor, we said goodbye to each other and I couldn't understand the strange evil smile on his face". Later that day the jury was told of that incident, they rechecked the solution and found a bug and the team members was re-announced with that unlucky guy moving out of the team...

        I think the failed problem at CF isn't nearly like that)
        → Reply
        • 13 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Don't worry. I submitted A+B+E. Only E survived the tests. It looks funny in the scoreboard. After that A and B, each with one line more, got accepted :)

          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            auch ... That's the largest loss for today I guess.

            still 1 character is less than 1 line :D
            → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          I see you have interesting olympiad life and you are from Ukrain, or from Canada? Imigration complete?
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Nope, I'm still Ukrainian. I just went to study in Canada. However, all those contests were mathematical. I started doing cf&tc last summer only.
            → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    no, I only try to notice all sizes of data struct which I use
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I failed my B on 125th test because of my INF was 1 << 35, not 1 << 34 and because of that my color won't change to red.
    Could you imagine that?

    By the way, I am sorry about your mistake as well. Wish, you won't do that one more time.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Auch ...
      Don't worry, there still are lots of rounds ahead to become red )
      → Reply
13 years ago, # |
← Rev. 2   Vote: I like it -52 Vote: I do not like it

Nevermind

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it
    Жалко, тут нет опции спрятать коммент, такой же, как спрятать пост в черновики.
    → Reply
13 years ago, # |
  Vote: I like it +31 Vote: I do not like it
I am not going to send official appeal because I don't care that much about rating. I would like to describe what I had during contest to satisfy questions of "how can one lose much by such a minor change".

I wrote some solution to B, it failed pretest 7.
I found one mistake, resubmitted. It failed pretest 7.
I tried changing int to long long in one place even though my calculations were saying that everything should fit in int. It failed pretest 4.

Now I spent lots of time trying to figure out what can be wrong with false overflow or something like that because the should-be-more-correct solution fails some case that the should-be-worse one doesn't.

(This part is no longer related to problem B, it's just a continuation using bad strategy. But it was caused by lots of wasted time.)
Finally I gave up and looked at the scoreboard and read C+D+E. My chances of getting sane score (without B!) were quite low at this point so I decided to go for E. I had the solution but didn't code it in time. This way I am left with just A at the end.

Now the scoreboard says I failed on pretest 4 at all 3 submissions but I am sure it was saying 7 before.

I don't want to whine. I don't need the contest to be unrated. Ok - it seems a bit unfair but as I said before, I don't care about rating. I just saw several people asking what so bad happened to consider making the round unrated so I wanted to share this story.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it
    Something like this happen to me problem 'B' Div2 ,just reading it and didn't think on it just start to code it has no idea just implementation
    i implement it but I'm shocked when i got TLE test case 5 and i'm sure about my code complexity and constrains of the problem is too small 
    so what's the wrong???.
    after more changing on my code and more lose of time, i discover that the way I use to convert from string to number take more time just use " itoa() " instead of my template then "Passed System Test". >.<
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Correct me if I'm wrong, but I think there was broadcast info saying the tests have changed? ;) (I think that broadcasted messages should be stored in "questions" section btw.) 
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    I think that this type of a contest must be prepared perfectly. A mistake in the solution of one task ruins the whole effort. The situation is irreversible (it's not only about wasting the time and points for the task but also the bigger problem with illegal and wrong hacks) and it's undeniable reason for unrating the round.
    → Reply
13 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

I reduced Problem A (Prime Permutation) to the problem ``given two sets , determine whether there exists a partition of A such that .''  Actually Problem A was a very special version of the latter problem in which only one element of B is greater than 1, which I didn't realize during the contest :-(.

The question is how to solve the latter problem in general.  During the contest I thought it could be solved by DP and bipartite matching, but I couldn't finish coding.

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
hey, can anyone tell why is it giving WA on judge, this code is working perfectly on my machine ?
http://ideone.com/Go65C judge is giving WA on 2nd test case ?
3 3
010
909
012
→ Reply
13 years ago, # |
  Vote: I like it +14 Vote: I do not like it
Too bad that nobody is checking problems quality before contest. Otherwise, problem D from this contest would not reach any normal contest, except maybe some training contests following lecture about suffix arrays.

I don't understand why making this contest rated would make it any better? I think it should be unrated without any discussion (I didn't participate, so I don't have personal motives).
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Ratings have already changed for those who do not complain personally to RAD [with a reason , how wrong statement affected him]
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it
    So, it means that some coders get rating update and some don't ? If so, wouldn't it cause any unnecessary rating inflation then?
    → Reply
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
I sent a message to RAD before 11pm on November 4 but it's unread an my rating is updated but i don't want.
sorry for my bad english.
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Could pls someone give a hint about C/div.1 (E/div.2)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Already answered by myself :). The idea comes from criterion: bracket array is correct, if and only if:
    1) there exists at least one path with correct sequence and
    2) brackets on diagonals (i+j=const) are the same type.

    so, initial 2-D problem comes to the analogous 1-D task, where you need to find m-th bracket sequence (adjusted to some dancing with priorities.)

    → Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Is it possible to solve 'B' Div.2 with Ruby ???
I think 1 sec is too short for Ruby user.
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Could anyone give some hints on how to solve problem E?  Some solutions look very short; I don't see how to simplify the expectation over all possible paths, all possible entrances/exits for the maze, though.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Suppose the entrance and exit are fixed. For a given edge x, what is the expected number of times that the DFS will traverse it before reaching the exit? For edges that lie on the path from entrance to exit, it's 1, because we will always traverse them exactly once. What about, say, another edge from entrance - what is the possible cases for it? Can we traverse it 0 times? once? twice? more? What are the probabilities of those cases?


    Please tell if that's not enough to figure it out.
    → Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it

could anyone tell me how to solve problem D?

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is there any english editorial??
→ Reply