MikeMirzayanov's blog

Codeforces Beta Round #12 (Div. 2)
By MikeMirzayanov, 15 years ago, In English
Hello again. I hope nobody has forgotten to register?

In this contest we will try alpha of our chat - if something goes wrong, we turn it off: please do not panic:)

Links:
Problemsetters: Дмитрий Матов и Игорь Кудряшов. Thank them for their contributions.

I wish you to advance to the first division.
Mike Mirzayanov.
  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (62)
| Write comment?
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is problem solution available
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yep
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Это не по теме . . . У меня гугловский браузер когда захожу на страничку рейтинг,то таблица вылазит за свои приделы,закрывая область моего профиля... это так и должно быть или я туплю? 
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Это у многих так... будет переделываться потом. Но странно что у тебя глючит.. на моём хроме всё норм
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Видимо зависит от разрешения. На 1280 нормально, но на разрешениях меньше могут быть проблемы.
          → Reply
          • 15 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Конечно зависит. А ещё и от браузера. У меня уже после восьмого раунда проблемы начались. 1024.
            → Reply
          • 15 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Кстати, такой вопрос:
            а смысл делать так
            Указывает на одну тему, но почему разница на 10?
            → Reply
            • 15 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Ага, есть такая бага.

              Проблема в том, что во второй ссылке темы не видно, первого собщения.


              Вторые сообщения приходят на почту.

              → Reply
              • 15 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                Переписывался с Майком, оказывается всё просто. Комменты это отдельный объект который привязан к другому объекту. Это может быть топик блога, может быть обсуждением задачи и т.д. Т.е. эти ссылки никакой связи не имеют.
                → Reply
            • 15 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Тогда хорошо было бы видеть то, у чему привязан комментарий.

              Спасибо за ответ.

              → Reply
              • 15 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                Ну это уже довольно старая тема, что из мыла нет редиректа сразу к топику. Опять же спрашивал на эту тему, насколько я понял там какая то принципиальная проблема.
                → Reply
            • 15 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Я не про редирект к топику из мыла.

              Я про то, чтобы к странице комментариев сверху прикручивался оригинальный пост.

              Кстати мы с тобой обсуждаем это не в той теме и в английской ветке к тому же...

              → Reply
              • 15 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                :-D Есть такое. 
                Не в том дело. Прикрутить ссылку просто так незя. Там как то надо хитро подумать на сколько я понял. В общем это видимо в туду. :)
                → Reply
    • 5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Where?

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

can anyone tell me in problem b  why we cant take m as integer and although m is given as integer

but if i am taking m as integer i am getting wrong answer. although  in problem statement  it is goven that  m may have leading zeros  but m is integer  so  no meaning of leading zeros.. so can any one tell me correct thing

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

    Leading zeros in M are very important, because they "take part" at constructing minimal number

    for example: M = 0123. minimal number is 1023. If you escape leading zeros in reading M you lost Zeros in result.

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

      first thing we dont have to find  answer for m we have to fing=d minimal number for n .

      so  ur example is nt correct

      i m asking here that what is importance of leading zeroes in an  integer 

      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        If you take m as an integer, there should not be any problems. Make sure you don't take n as an integer.
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Sorry, in the previous post I thought about I/O problem. But here is an algorithmic mistake, as explained in posts below.
          → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Sometimes providing corner cases helps much.
    I missed one such case in Problem B. Finally got ac just after the contest.
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can omit all corner cases if you read first integer as a string and sort it. Then you can just exchange first 0 with first digit != 0.
    → Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    *first leading 0
    → Reply
15 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Hello,

I could not find enough explanation about the standing page, in particular:
- what does the penalty represent ?
- for each problem, I finally understood that I have to click on the "+" or negative number but is there a specific penalty for each failed submission ?
(is there a forum for questions related to problems ? I am quite curious about case 9 for problem B - Correct Solution)

It was my fist participation and I really enjoy the web site and how it works, thanks a lot !!
→ Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it 
E:

for(i=0;i<n-1;i++)for(j=0;j<n-1;j++)a[i][j]=1+(i+j)%(n-1);

how to obtain this formulation? i use patterns but i need to determine a[i][n-1] by my self.
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it

@ADMIN    pls  make an statement about question b

in question  m is an integer

but  i got 3 wrong submission if i m taking m as integer

ans i got accepted wen i made  m a string.

why wrong on taking m as integer...?/? 

→ Reply
  • 15 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Test:
    4
    04

    Answer:
    WRONG_ANSWER
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      @ADMIN  i dunno but wen taking m as 04  if one using int  m then it will be  4 and answer will be "OK"

      so  there is no mistake in int m 

      correct me if i am wrong

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

        For M = 4 answer is 4. But Valera's answer was 04.

        Look at the M and Valera's answer as string(not as numbers)

        → Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
can anyone tell me in problem C ,what tricks
→ Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Any hints / explanation for Problem - D (Ball) ? Its a nice problem.
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How to do with Problem D？ Can anyone tell me？
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    I have sorted by first parametr and then make rmq where indexes were second parametr and value is third. Becouse of stecific rmq request you can use Fenvik tree insted of interval tree and I have done it.

    But i saw tthat some submited solutions are more easy.
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      is problem D smilar to this one .
      http://www.spoj.pl/problems/MDOLLS/
      Quick Sort and Binary Search ?
      Sorry for my bad english .
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        No, they are not similar. Here we have 3 parameters to look for and range is [0,109] for each value, and at most 5x105 such triples and we need to just find for each value, if there is a value greater than this.
        ---
        @kuniavski: could you please explain it a little more. Each value can be as large as 109, so how are you using a BIT ?
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Of course firstly i mae them smaller. the absolute value are not necessary. So you can say that malist value is 1, next is 2 and etc. So values should be not more 5x105.
          → Reply
          • 15 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Thanks. Done it :) . . superb problem it is ! Any other ways of solving it, other than 'sorting with x and using rmq ( or bit ) on (y,z) ' ??
            → Reply
            • 15 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Could you please describe this approach more specific?
              → Reply
              • 15 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                Approach is, we sort it with X and process the bunch of entries with same X at a time.., thus reducing the problem to take care of Y and Z. As relative difference only matters, we can enumerate all Y's, thus getting them in range [1 - 5x105] in worst case. Now, with Y as key and its corresponding Z as value, (Y,Z).. we can use BIT, to store the cumulative maximum. From this, we can query "what is maximum Z for Y in range [1,y]?" in O(log n) and also can update this table in O(log n). I hope you got rough idea of what we are doing.
                ...
                I think I have written a well readable code.. you can check that by clicking the number of solved, beside this problem in the problems list. Submission id is 40387.
                → Reply
                • 15 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  i can't find this code with id 40387.
                  can you mail this for me?
                  with best regards.

                  mail:
                  [email protected]
                  → Reply
                  • 15 years ago, # ^ |
                      Vote: I like it 0 Vote: I do not like it
                    sorry dude, typo.. its 40837 actually. You can find it here ( http://www.codeforces.com/contest/12/status/D?order=BY_PROGRAM_LENGTH_ASC )
                    → Reply
    • 15 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      I don't know what is "Fenvik tree",  nor can i find it by Google it . Can anyone tell me ?
      → Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it

@ADMIN  can you please give us input.output of problems ...

so that we can find bugg in our programs

→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How do you think, why 40676 doesn't pass, while 40679 is accepted?
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Let't start the challenge :) I see the case, who else?
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Wrong answer on test 31.

      It was my fault, that's why i know the case too. =)

      → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      n=0 ?

      btw, it would be nice to be able to link to the actual solution (I guess vihrov's links work only for him)
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        No, they don't :(.
        → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        When they say "there is no misleading 0 in the first number", I think N <> 0 :D.
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          I don't know, in the problem it's said that "0 ≤ n"
          → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Well after my registration I found that I'm on train to Beijing to attend APIO2010 when the contest started.

I calculated the time wrongly due to the timezone difference.

I wonder whether it will affect my rating. I really hope I can cancel my registration but it seems impossible to do so.

And I really hope that zero submissions will not affect the rating. (I don't know whether topcoder is like this due to the fact it doesn't support PASCAL).`
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    For solving timezone problem now you can use this calendar (for Codeforces by darnley) or this (by me).
    I think possibility to check contest time at timeanddate.com will be implemented, but later.
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thanks, but it seems impossible to cancel the registration now.

      Time on that calendar is still Moscow Standard Time (UTC +4), so i had to add 4 hours on it.
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        There is no need to cancel registration. The rating changes here only if you have submitted a solution.
        Yep, you have to add this calendar to your account at google.com (there is a link in bottom right corner), after that you'll see all events in your time zone. :)
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Works now, thanks.

          BTW, are you one of the administrators of this website?
          → Reply
          • 15 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it
            No, I'm just an annoying flooder sometimes helping others to solve their problems.
            → Reply
            • 15 years ago, # ^ |
                Vote: I like it +3 Vote: I do not like it
              Well the website becomes better due to the help from people like you.
              → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        "And note that with Google Calendar you can set SMS and e-mail notifications, in order to never miss a Codeforces round. Not only can you do this for a single event, but I also recommend you to go to the Settings menu and set automatic notifications for all events of this calendar."
        (Codeforces Calendar)
        → Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it

@ ADMIN  whenever i got mail for new comments i got this url to .ru extension like

"http://codeforces.net/comments/349#comment-4505"

so u can make it   ".com"   for english users......

→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    BTW (I'm from Russia), I receive urls from:
    codeforces.ru
    codeforces.com
    (and even!) www.codeforces.com

    Besides they have different cookies and I need login every time to make some action (answer, give plus, etc).
    → Reply