Serega's blog

Codeforces Beta Round #90
By Serega, 13 years ago, translation, In English

Hello everyone!

Welcome to the Codeforces Beta Round #90! I (Sergey Sukhov) and Alexander Ignatyev (aiMR) have prepared for you today's contest. We thank Artem Rakhov (RAD) for help and useful hints, Mariya Belova (Delinur) for translation of statements, as well as Michael Mirzayanov (MikeMirzayanov) for opportunity to conduct this round.

Good luck and high rating!

UPD. Unfortunately the mistake was found in author's solution of problem B, therefore this round will be unrated. We present our apologies.

UPD2. Analysis of problems A-D is published.

Announcement of Codeforces Beta Round 90
  • Vote: I like it
  • +52
  • Vote: I do not like it

Comments Comments (67)
| Write comment?
13 years ago, # |
  Vote: I like it -54 Vote: I do not like it
Good luck & Have fun :)
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 5   Vote: I like it -32 Vote: I do not like it
    Edit : Ignore
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 3   Vote: I like it +43 Vote: I do not like it

      I always downvote GL&HF messages. I hate them.

      They don't provide any info, I need to scrool it to check, is it any useful meesages about topic(i.e. next contest now) here.
      As for me, they are OK for chat, but not for forum or blog comment
      → Reply
      • 13 years ago, # ^ |
        ← Rev. 2   Vote: I like it -39 Vote: I do not like it

        Is wishing good luck bad at all??? Before any contest, any one can wish other good luck, this is like a love to all, or can be formality. But, why is this seems as down voted comment??? If anyone finds only useful info, then they only should search for that, not giving down vote to any comment which never seems like nonsense comment. Coz, every vote counts as contribution in Codeforces. So, we all should be careful of this.


        One thing, please look at this Blog, writer written in the last "Good luck and high rating!". So, what will you say? Is it down voted blog????

        → Reply
        • 13 years ago, # ^ |
            Vote: I like it +7 Vote: I do not like it
          It contains "Good luck and high rating!" among other things. It isn't about the color, but for me saying "Good luck and have fun" sometimes looks like begging for contribution.
          → Reply
          • 13 years ago, # ^ |
            ← Rev. 2   Vote: I like it -30 Vote: I do not like it

            But, may be this is not like what you are thinking, Actually I never think of this. Always saying Good luck before any contest to all the contestastent (online or onsite). As Topcoder gives us chance to chat, we can say Good luck to everyone by a General post, In codeforces, it give chance by comments. So, I don't think that saying Good luck is like begging for contribution. If so, then I will never say good luck. Coz, I don't like this types of thought like begging for upvoting.

            → Reply
        • 13 years ago, # ^ |
            Vote: I like it +9 Vote: I do not like it
          The difference is that ErzhanDS wrote only "GL & HF" but the topic consists of some information about who is the problemsetter.
          I consider "GL & HF" messages annoying, that is the reason why I have downvoted it.
          → Reply
13 years ago, # |
  Vote: I like it -10 Vote: I do not like it
This round for div1 or div2 ?
→ Reply
13 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Because this contest for both of Division, so please make the problem for both Division (Not for Div 1 only) :-)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Highest number of registrants this time ( 2000+ ) :)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    wow it's 2010 registrants. it should be one more registrant and it would be cool :p
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      I said to a friend of this round, and he remembered the need of registration just a few seconds after registration was closed... He should have been the 2011-th :(
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
unrated round, isn't it?
→ Reply
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it
what's the trick in problem B?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it
    Trick is we can already saw all k cards, but there are enough theorems to form one more card of the same size. Say n = 13 and k = 5
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I didn't understand your description, can you say an exact case?
      → Reply
      • 13 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        13 5
        1 2 3 4 5 6 7 8 9 10 11 12 13
        5
        1 2
        3 4
        5 6
        7 8
        9 10

        edit: some solutions will try to grab 12 and 13
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        8 3 
        12 2 33 3 33 3 3 3 
        3 
        1 2 
        3 4 
        5 6 

        ans is 7 18
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it
        8 3
        1 2 3 4 5 6 7 8
        3
        3 4
        5 6
        7 8
        Correct answer is 3.5 7.5, not 1.5 7.5
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          How is it? theorem 3-8 are seen,only 1 and 2 left. a card with 1st and 2nd theorem will average 1.5 .

          Am i wrong?
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it
            But we already saw all 3 cards
            → Reply
            • 13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              i just got it accepted. I have added an extra check,how many distinct cards i've seen so far.  Thanks everyone for helping.
              → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            But it can only be divide to 3 cards. So 1st and 2nd theorem  can't form another card.

            → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            But there are only 3 cards (k=3) and all of them have been already used: 3-4,5-6,7-8. So there are no other cards on the table.
            → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I want to know what is wrong with problem B.
is problem B's description wrong or the author's solution wrong?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    author's solution wrong
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So even the pretest are wrong?

      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        pretests seems to be ok
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          If the pretests seems to be ok, I don't understand why it will be unrated.
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it +17 Vote: I do not like it
            hacks depends on authors solution
            → Reply
          • 13 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it
            After tricky case was announced, I started thinking about it and eventually found it and resubmited. Which I could do, because I haven't locked it yet. So, even if pretests were OK, and now they removed my +25 in challenges as well, it's still unfair to those who locked in.
            → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      What is wrong with author's solution to Problem B
      → Reply
      • 13 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        you can read other posts here. 


        Egor says: Trick is we can already saw all k cards, but there are enough theorems to form one more card of the same size. Say n = 13 and k = 5
        → Reply
13 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

Can anyone please help me as to why this solution of mine  to problem B is getting runtime error(on case 5).I have worked on it but not finding the reason.
This code is in JAVA.Here is the link.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    You use nonexistent elements of array "c". The size of array "c" is "t", but "i" is running from 0 to "card".

    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I think there should be more questions (maybe 7) in dual rounds, so there can be more easy ones for the low rateds.
The easy tasks could be assigned very few points, so the top rateds could just skip over.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    "The easy tasks could be assigned very few points, so the top rateds could just skip over."

    But they wouldn't skip over them, because nobody is going to miss out on easy points, regardless of whether they are high rated or not.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Well if they would get more pts/min by going for the harder tasks, maybe they would :)
      Otherwise the joined competitions could be 2½ hours...
      But of course if more tasks would result in fewer competitions, that wouldn't be good.
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    If you have such 7 problems already prepared, you can then simply run separated contests as usually...
    → Reply
13 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it
sorry, duplicate
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it
sorry, duplicate
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

i think its not right that contest is unrated , we can just ignore problem B and count points with 4 problems, for someone who wrote contest well is not fair not to update his rank , in all case authors are guilty not coders

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

    Imagine someone who spent his time on solving B correctly and then got his solution ignored. Someone else could skip B or have an incorrect solution, and that gives him an unfair advantage...

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

      i have 1528 rating, when i wrote 4th problem i was at 16 place, and i was happy and i thought my rank would be increased then authors wrote that round was unrated, is it my falt ?but at last my code had time limit at 28th test :( 

      → Reply
13 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

I think it's funny how the tricky case in B is so easy to miss that even the authors of the problem themselves missed it ;)

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In problem B, can anybody tell any efficient way to count distinct number of cards that Vasya has seen.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    set<vector<int> > myset;
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I've put all the used questions' numbers in a set and then when looking at the new card, I checked if that set already contains a question from it. If it does, we have already seen that card.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    bool used[n]; //used[i] true if we saw i-th theorem
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    If we count how many different theorems(not cards but single theorems) has Vasya seen then we can check that this number is lesser then (k*n/k) and this will do the job.

    To calculate number of different theorems you can use a set, or an array as RiaD-WaW said.

    The number of differrent cards is the number of different theorems divided by the number of theorems in a card.

    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Since two equals cards will be given as two (possibly) different permutation of the same set, and there won't be any theorem in two or more different cards, one could just pick any theorem i from a card (say, the smallest one) and set used[i] to true (where used is a bool array). The number of true elements in used will be also the number of different cards given.
    → Reply
13 years ago, # |
  Vote: I like it +18 Vote: I do not like it
Now i get, why all this rounds are beta.
→ Reply
13 years ago, # |
  Vote: I like it -8 Vote: I do not like it
In test case 9 of problem B:
3 2
1 2 3
2
1
2
Answer is 1.00000000 2.000000000
Is that correct??? I think it should be 1.00000000 3.00000000.Please tell me if I am wrong??
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I'm already have two cards,therefore 3 can't be considered.
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You need to read better condition: "Besides, no theorem is mentioned in more than one card (that is, theorems won't be mentioned in any card)."

    P.S. And that was previously stated!

    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    you have already known the 2 cards thus there is no other cards to check even if the rest theorems can make other cards
    → Reply
13 years ago, # |
  Vote: I like it +13 Vote: I do not like it
While there's an editorial yet, someone has some hint for problem D?
→ Reply