Alex_KPR's blog

Codeforces Beta Round #69
By Alex_KPR, 14 years ago, translation, In English
Hi all!

Glad to see you on the Codeforces Beta Round #69. As you suspect, it's not an usual contest.

Every division has 5 problems. Some problems are in both divisions; other are meant for certain division. But from the participant's point of view there are no striking differences from other rounds.

Please notice that such an experiment is the first one, so some technical troubles and unexpected problems are possible. Please treat with understanding if it occurs.

Also: the costs of the problems in the first division are 500-1000-1500-2000-2000. In the second division the costs are classic: 500-1000-1500-2000-2500.

The round was prepared by Alex_KPR, dagon and Marishka. Also RAD and it4.kp helped very much. The statements were translated by Maria Belova. The whole process was supervised by Mike Mirzayanov.

Good luck all!
_____________________________________

Don't forget about voting!
_____________________________________

Top 10 participants in the first division are:
Place
 Who
1
  vepifanov
2
  KADR
3
  hos.lyric
4
  Zhukov_Dmitry
5
  e-maxx
6
  Romka
7
  ivan.popelyshev
8
  Shef
9
  RAVEman
10
  ktuan

Top 3 participants in the second division are:
Place
 Who
1
  Gluk
2
  nvilcins
3
  piloop

Congratutations! Good luck for everybody at the next round! 
_____________________________________

Editorial is here.
  • Vote: I like it
  • +177
  • Vote: I do not like it

Comments Comments (88)
| Write comment?
14 years ago, # |
  Vote: I like it +20 Vote: I do not like it
good luck and easy hacking)))
→ Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Very glad to see separate set of problems for each division in same round.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Common problemset is one of the main reasons for such frequent rounds
    → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
GOD BLESS US.. :)
→ Reply
14 years ago, # |
  Vote: I like it +305 Vote: I do not like it
Вместо голосований: поставьте здесь плюс, если вам понравилась идея разделения участников по разным контестам в зависимости от дивизиона.
====
Instead of poll: please click "I like" on this comment if you like an idea to split participants into two different contests depending of their division.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it -22 Vote: I do not like it
    Не могу удержаться
    Всем троллям на заметку: вот он-идеальный способ получить большой плюс:)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it
      Написать свой кодефорсес, покрасить свой ник в черный цвет и проводить опросы кнопкой "I like"? :)
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    I think it is better for participants from the second division, to have some easier problems, so that we avoid situation where a lot of them can solve none or only 1 problem.

    I also think that a good idea may be losing points for a task per second instead of per minute.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      There are a lot of Div2 only rounds that allow to solve more easy problems.
      → Reply
14 years ago, # |
  Vote: I like it +162 Vote: I do not like it
Вместо голосований: поставьте здесь плюс, если вам не понравилась идея разделения участников по разным контестам в зависимости от дивизиона, а нравятся больше стандартные общие контесты.
====
Instead of poll: please click "I like" on this comment if you do not like an idea to split participants into two different contests depending of their division, and you like typical common contests more.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    А в общем контесте подразумевается разделение дивизионов по комнатам?

    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Да, дивизионы в разных комнатах
      =
      In this case we suppose that participants from the different divisions do not share rooms.
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it
    а минусовать плохо, когда не просят! :)
    =====
    Don't cheat, people, who wants splititing participiants: don't minus this comment! :)
    → Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Вот не понимаю, почему большинство голосовавших поддержало идею разделения контестов.
    Если в общем контесте участники делятся по комнатам, то для div1 оба варианта совершенно одинаковы: они в своих комнатах решают контест div1.
    Получается, что участники div2 проголосовали за то, чтобы не иметь возможности пытаться решать сложные задачи. А они что, вечно собираются сидеть в div2?
    Я бы понял, если бы речь шла о том, что теперь всегда будет по 2 контеста. Но ведь контесты div2 only никто не отменял. 

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

      Потому что в раздельном контесте можно решить четыре задачи, а в общем только две. Первое делает человека более счастливым :о)

      Писать сложный контест и решать в нем только А и В -- это не очень круто тоже.

       

      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Я вчера писал див1 и решил только две задачи, но так сделало половина див1. Так что я вполне доволен:)
        → Reply
    • 14 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it
      Я голосовал за раздельные раунды, ибо сначала обрабатываются посылки див1, потом посылки див2:) Див1 ждет меньше времени и раньше узнает прошла у него задача или нет.
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      Разделение дает свободу в выборе сложности задач. Вам не кажется немного абсурдным, что начинающие школьники должны решать общий контест из пяти задач с, например, Petr'ом или ACRush'ем?
      Второй же дивизион при предложенном подходе сможет отработать пять идей по своему уровню. С чего Вы взяли, что они не будут иметь возможности решать сложные задачи? Напишут свой контест, потом прорешают div. 1. Вечно сидеть в div. 2? Ну что Вы. Подрастут, заматереют (всему своё время) — и пробьются в первый дивизион. И эта составляющая тоже очень важна.
      По-моему, могут быть две причины столь поздней попытки осуществить разделение: схожесть с топкодером и увеличение затрат на организацию раунда.
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it
        «При встрече с достойным человеком думай о том, как сравняться с ним. Встретившись с низким человеком, вникай в себя и сам себя суди»
        Конфуций.
        → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        зато тот, кто попал в div1 уже не может решать div2 only, хотя для некоторых это полезно.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          they can but out of competition ;)
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            На параллельных соревнованиях - нельзя
            → Reply
            • 14 years ago, # ^ |
                Vote: I like it -8 Vote: I do not like it
              и что? никто не отменяет div-2 only раунды
              → Reply
              • 14 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                Если частота появления контестов не изменится, то разницы я не вижу. А вот если рассматривать 2 параллельных контеста как -1, то это печально.
                → Reply
      • 14 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it
        Я начинающий школьник и хочу решать, как халяву, так и то что решает тот же Petr

        ЧЯДНТ?
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          удачи решить в дорешке то, что решит Petr - опять-таки, проблем не вижу
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            ну дорешивание и контест сильно отличаются. В дорешивании почему-то решается побольше задач (даже не учитывая разбор).
            → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Не понимаю, почему в этом обсуждении уже не в первый раз дорешивание упоминается. На CF можно решать задачи из архива, как и на множестве других сайтов. Но, согластесь, что соревноваться с Петром и дорешивать за ним - это разный уровень мотивации.
            Я не о шансах сейчас, да и не о Петре конкретно, а о самой возможности выступать в соревнованиях определенного высокого уровня. Что при разделенных контестах станет не всем доступно.
            А для начинающих, повторюсь, div2 only и возможность самостоятельно решать задачи с множества сайтов никто не отменял.  
            → Reply
            • 14 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it
              из-за div-2 участников необходимо давать необоснованно простые две первые задачи в div-1 раунде, чтобы их даже div-2 участники смогли порешать, хотя большинство div-1 участников тратит на них 10-15 минут и, частенько, не решает больше ничего

              так что же получается? div-2 участники обламывают фан div-1 участникам, а сами всё равно ничего не могут решить - не кажется ли это глупым?
              → Reply
            • 14 years ago, # ^ |
                Vote: I like it +5 Vote: I do not like it
              а о самой возможности выступать в соревнованиях определенного высокого уровня

              Претендуешь на высокий уровень? Имей высокий рейтинг.
              → Reply
    • 14 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it
      Согласен, пусть лучше вместо 5 контестов(по 7 задач) будет 7(по 5) и каждый сможет порешать каждую задачу. Решать то-то просто в архиве это совсем другое
      → Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
I would so love to have a chat room facility available on Codeforces, where people can discuss contests after round is over. Since we don't have that yet, if most of you use IRC, I've registered a channel on irc.freenode.net by the name of #codeforces. If you like IRC, please join.

(And yes, I can hand it over in case it gets some population, and CF wants it)
→ Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
During the whole contest i couldn't go to my room . When i click the room button it always takes me to room 1 where it shows there is no contestant !
→ Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Why was tourist crumbling in this contest?!
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I'm still waiting for system tests
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Can anyone tell me , what would be the answer for testcase:

    Problem D: DIV-2
    =====

    0 1  

    =====
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      If a = 0, b = 1, correct answer is 0.5.
      If q > 0, equation x2 + q = 0 has no roots.
      If q < 0, equation x2 + q = 0 has root
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      0.5
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        what about 0 3?
        Can you please explain the case about 0 b
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          If a = 0, then p is always 0. So we have

          x2+q = 0
          q<=0;

          result = b/2b = 0.5
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Unless b=0 also, in which case there is only one point to choose from and probability should be 1.0.
            → Reply
14 years ago, # |
  Vote: I like it +50 Vote: I do not like it
I would pay a lot for a feature "You used %lld, fool!" when submitting...
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Hahaha...Yeah that hurts!!
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    There is always a note in output section, so read the tasks carefully :)
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How do I see the standings for div 1? Can't find it...
→ Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
thanks for nice problems!
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why can't I register for practice nor submit the problems in the problemset? (I mean this contest only)
→ Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Is div 2 systest running in real time/replay mode? It's so slow =/
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi,
DIV 2 - C

Test case
5
Troll likes Dracul
Anka likes Chapay
Cleo likes Anka
Chapay likes Cleo
Snowy likes Hexadecimal
222 400 400

why the answer is 89 5

what im getting is 222(Snowy), 400(Anka, Chapy, Cleo), 400(Hexadecimal, Troll, Dracul) => diff 89, likes 4.

what's wrong?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    because the likes must be maximal and here 5 is more that 4
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Snowy, Hex

    Anka, Chapay, Cleo

    Troll, Dracul

    gives 89, 5

    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      Thx, I got it now.

      There may be few possibilities for min diff, I just took one with min value. That's really omg. :B

      got AC after considering this
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I didn't solve it too, but with another reason: inaccurately read problem statement and didn't round down x/y, so found best case in floating numbers. Fail

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

    Split them as (Snowy, Hexadecimal) (Anka, Chapy, Cleo) (Troll, Dracul)

    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Are the formulas used for calculating rating available anywhere?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I hope someone writes nice neat editorial for this round. Very eager to read about the probability of nature of roots of quadratic equation problem... (DIV2-D)
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I have to ask: was the double entendre in the title (and description) of problem C present in the original Russian version too, or was that a bonus for those of us who read the English version?
→ Reply
14 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Наконец-то в полку генералов прибавилось. Поздравляем vepifanov и hos.lyric!
=======
It's happened that to the regiment of generals some participants were added. Congratulations for vepifanov and hos.lyric!
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Problems are good.
Any trick on the Div-2 E. I try the DP solution but can not pass the 3rd test..
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi friends,
for problem A Div-2. i wrote this code

  1. #include<iostream>

  3. using namespace std;

  5. int main()
  6. {
  7.   int n,m;
  8.   cin>>n>>m;
  9.   int a[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
  10.  
  11.   for(int i=0;i<n;i++)
  12.   {
  13.     if(a[i]==n &&a[i+1]==m)
  14.     {
  15.       cout<<"YES";
  16.       return 0;
  17.     }
  18.   }
  19.  
  20.   cout<<"NO";
  21.   return 0;
  22. }
but it got failed on system test on this test case:
Test: #36, time: 10 ms., memory: 1356 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER
Input
19 21
Output
YES
Answer
NO
Checker Log
wrong answer 1st words differ - expected: 'NO', found: 'YES'

but when i ran it on my PC output comes NO.
Whats wrong can anyone tell me??
Thanks
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    your mistake is here:
    "for(int i=0;i<n;i++)"

    you should write something like this:
    "for(int i=0;i<14;i++)"

    it is out of boundary error

    and do not post your code here, please
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      oh.. thanks :)
      can anyone tell me where i can find editorial for this round?
      that would be very helpful
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I think it will be ready for hours

        now only russian tutorial is available, you may find it here and use google translator
        → Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    too late :(
    → Reply
14 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it
Same code, different result, why?
Is there something wrong with GNU C++ 4.6?
Because in my Code::Blocks 10.05 with mingw IDE on Windows, no RTE!
403082 Apr 20, 2011 10:40:16 AM hlahuhkln C - Heroes GNU C++ Runtime error on test 1 10 ms 1400 KB
403079 Apr 20, 2011 10:38:57 AM hlahuhkln C - Heroes MS C++ Accepted 30 ms 1400 KB
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    May be you have array of vectors in your function?
    vector<int> a[3];
    You know, if int a[3] defined in function it may not be filled with zeros. So, vector<int> may not be empty and even valid, so you try to do something with invalid vector. Of cause, it's RTE.
    May be Visual Studio initialize local variables, I don't know.
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it
      I got it!
      vector< vector<int> > g(3);
      Thank you!
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      I don't think it's true. Rizvanov in his post above referenced to some site, not a C++ standard - that's not a good source.

      And it looks like it's a bug in compiler, but not a "feature" of language. I think it's a nonsense when you can't simply use local array of structures or classes - should we call placement-new for each of them? I don't think so, C++ is not Java :)

      I reported the bug yesterday, and today it was fixed (the problem was in optimizer - BTW all such programs crash only in O2, and this is another hint that this is a compiler problem, not a language's one).

      http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48695

      → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Since  Mike has made some changes in Rating formula, it has become little bit difficult to get rating enhancement, you need to really perform well.

I think it is Quite Good in some sense.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    I understand (roughly) how the system works, however, I was quite surprised that by finishing 2nd (out of almost 1000 participants) I improved my rating by only 70 points. That's harsh. I hadn't participated for a while and had fallen to div2 because of the change in div1-div2 bound. So I expected this contest to be more a formality, but actually barely made it to div1. Had I failed a problem or two and I would have stayed in div2 despite being close to the bound.
    In general I think the system rewards low-rated coders who performed very good and average-rated coders who performed OK too much. It should be this way, but in smaller proportions.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Yeah, I also thought that you people should have got more ratings.

      → Reply
    • 14 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it
      I just tried to find out what would have happened to your rating if you have done the same effort in DIV 1.

      Even if I don't count your hacks and solutions to question 1 and question 2.
      your rank would have been 58 with total points = 2186 .
      ( counting the last 3 probs. since they were same in both divs)

      And you just navigate to standings page of DIV 1 and try to see the rating increase of rank 62 ( pdwd )  , he has got total rating increase of 129 .

      And now I am entirely convinced that there is some flaw in formula for DIV 2.

      Because you performed better than  pdwd that day but he got better rating , that is totally unjustifiable.

      If you count the extra effort  you put in to hack and solving first two problems then , I think you should get even much more rating.

      Again if we take the fact the you were blue and pdwd was high in violet , then also your rating should increase even much more.

      So, overall your rating should have increased at-least 170 (if go by the kind of rating increase in DIV 1) .

      Sorry Mike , This is not good.  X-(

      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        It's hard to design a formula which sounds "reasonable" all the times.

        In this case, pdwd successfully beat many high rated coders in div 1, so he deserves large rating increase. Although  nvilcins may do the same thing if he completed in div 1, it's just an "if". The formula is not intelligent enough to consider his effort in a different situation, and I don't expect that a formula will do so.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          So, its better to have merged event.
          (or dont give common questions , so that we don't have any concrete proof to complain).

          → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          You can have common ranking for common problems.
          And likewise rating for each problem and then weighted-average.
          → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
hi
I 've a comment  on  (Codeforces Beta Round #69 Div.2) I attend the contest and solve 2 problems . I 'm not generally rated on this contest (same rate since last one)and my chart wasn't updated to include this contest

I don't know what's the problem?

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    That is the strangest thing I've ever seen at codeforces .

    I would also like to know the real reason.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Div I, Prob D - I tried hard. But i fail to understand why the 4th picture in sample test case 1 is said to be incorrect. From what i understood, all the horizontal and vertical layouts satisfy the given constraint. It will be great if someone could clarify.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Take a look at the third condition:
    "if there is a horizontal domino chip with its left half in column j then there are no horizontal domino chips with their left halves in columns j - 1 or j + 1. "
    It's not equal to the second one.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Oh, i see. So it means, we cannot have a horizontal chip at columns j-1 or j+1 irrespective of row number. I don't know if it was evident enough by the problem statement to other coders, but i feel that this clause("no horizontal chip in column j-1 or j+1 regardless of row") should have been more explicit.

      Anyways, thanks a lot for clarification.
      → Reply