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

Автор Gerald, 12 лет назад, По-русски

Всем привет!

Совсем скоро начнется очередной раунд Codeforces. Он пройдет по уже привычным вам правилам Codeforces.

Автор сегодняшнего раунда Михаил Граник (Fcdkbear), сейчас слушает лекцию в зимней школе по программированию в Харькове. Поблагодарим его за подготовленный контест!

Разбалловка на раунде будет стандартная: 500-1000-1500-2000-2500.

Всем удачи на раунде!

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

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

А на вопросы по условию будут отвечать, если автор где-то?

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

На самом-то деле сейчас уже разбор задач сегодняшнего контеста идет, но неважно :)

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

Good Luck Every One!:D

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

waaah, I hope, I could get better rank than last contest.. :D

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

Too bad, there's only Div. 2.

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

I didn't find any other contest with his name as a problem setter.I hope to see some great problems and a brilliant contest. HF & GL.

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

Удачи!

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

I hope I can get the good grades :) I am in China, so the local time in there is 11:30 pm. T_T but I still like attending the Competition like this to improve my Programming skills and English !

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

    I know that feel, bro. I'm in Indonesia and its local time is 22:30.

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

      I'm vietnamese, the same time with you Ariza :D. So tired but may be I will learn some thing good :D

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

    It's also 11.30 here. I'm doing my internship, hope I will not get fired for sleeping at work -.-

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

      I think it's better for you to hope to not sleeping at work. Trust me..

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

Будут задачи интересными?

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

Всем удачи!

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

Когда уже будут div1 по выходным :(

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

Hello, can you please explain why on task C the answer to the first test is 25 and not 26?

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

Зачем в Задаче C претест 8 с анти-Java сортировкой?

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

    Ну чтобы ребята сразу правили свой код!

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

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

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

Что не так с задачей B?

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

У меня у 1го такая картинка при попытке взлома? (Изображение в пред. правке) Браузер Chrome

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

    В Опере нормально, в Хроме ни 1го символа не разобрать. На прошлых раундах всё работало.

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

      У меня все читаемо, 2 успешных взлома. Можем у вас что — то не так с версией хрома? Моя 25.0.1364.97 m.

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

        Ну да, ведь только недавно стало возможным делать взломы на хроме.

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

        У меня такая же проблема, версия хрома последняя, как и у вас.

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

Типичный див2-контест: 4 халявки и одна задача, сложность которой как у четырех остальных, вместе взятых. Хотелось бы увидеть более сбалансированный контест с более сложными B-D.

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

    А что сложного в E? По-моему, наоборот плохо, когда много людей решают все задачи контеста. Хотя, D действительно должна быть сложнее...

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

    Последняя задача идейно не сложнее D.

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

    Б вроде норм, не слишком тривиальная. С слишком простая. Д вроде норм. Е типичная Е див2.

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

    Если судить по соотношению верных решений, то все отлично. Контест замечательный — спасибо автору!

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

I can't hack problem C due to file size restrictions, currently 256kb... This code:

int main()

{

int i = 1;

int n = 2 * 1e5;

int q = 2 * 1e5;

cout << n << " " << q << endl;

for(int p = 1; p <= n; p++)

{ cout << i; if(p == n) cout << endl; else cout << " "; }

for(int p = 1; p <= q; p++) cout << i << " " << n << endl;

}

generate a huge input (about 3.3 MB), it's a special input with maximum numbers for the queries and values N and Q, 2*10^5.

Currently, there is no way for send this input, or the code generator... :( ... then, I can't hack solutions, that surely get TLE on the finals tests.

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

    this issue has been discussed many times.

    you should use generator.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    #include <iostream>
    #include <cstdio>
    using namespace std;
    
    int main()
    {
    	printf("200000 200000\n");
    	for (int i = 0; i < 199999; i++)
    	{
    		printf("200000 ");
    	}
    	printf("200000\n");
    	for (int i = 0; i < 200000; i++)
    	{
    		printf("1 447\n");
    	}
    	return 0;
    }
    

    I sent this test to hack one solution of task C and got the incorrect test verdict with the message: FAIL Expected integer, but "#include" found (stdin) [validator validator.exe returns exit code 3]. Can someone say what's wrong?

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

      You submited it as test, not test generator. So it was got to validator as is. #include, which is first token is not an integer. Message informs you about it.

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

      There are tabs for that purpose ;)

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

Nice problems, Unfortunately I misread problem B so that I didn't solve it until last 15mins.

anyway I enjoyed the contest :)

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

I submitted problem C a lot of times, but every time judge gave Wrong answer on test case number one. As test number one is same as given in the sample input , I checked on my computer. It was working fine.

I could not even run my code on custom test because Custom test did not work properly and issued an error : Form elements must not have name or id of "submit".

Could anybody tell me what the problem could be ??

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

    did you make sure that you give your variables and arrays initial value 0 ?

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

      All the arrays were globally declared. I am only using the indices of the array on which I am overwriting data.

      Do I explicitly need to make all the global variables zero ??. I think they are zero by default.

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

        I don't know why this is happening to you,

        but sometimes I face the same problem so I give zero value to arrays and it will be solved

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

          I am not able to use custom test due to error "Error: Form elements must not have name or id of "submit".".

          It gave output 21 on the test case no one as shown in the final tests. I really do know why it showed output 21 ??

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

    In your compare function, what happens if a.value != b.value and a.type != b.type?

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

      Oh yes, this is where the actual problem lies. It was somehow working fine on my computer. Thank you very much :)

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

    I suggest you to test your code on custom test to see how it works on CF Compiler. I faced the same issue earlier and they told me to do it when I asked in clarification.

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

I think these problems are very good without problem statement of B. I'm not good at English, so I used translate system. But I couldn't understand problem B at all. I wish there had been an explanation for samples...

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

Всем привет:) Так как пост про раунд по определенным причинам мне запостить не удалось, напишу кое-что здесь.

Во первых, я традиционно хотел бы поблагодарить MikeMirzayanov за созданную систему, Delinur за перевод задач, и, конечно же, Gerald за огромную помощь на всех этапах подготовки контеста.

Надеюсь, вам понравились задачи:)

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

I DP problem C but it seems like there is a trick for this problem :(

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

TL по E на 70-м тесте — это не круто!

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

It is the first time that I solve all the problems in a Codeforces Round! THX!

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

Here's an unofficial editorial: http://www.codeforces.com/blog/entry/6778

Great round!

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

 OMG someone fake me

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

Can someone explain why my solution http://mirror.codeforces.com/contest/276/submission/3189675 gives output '141517992919' on Codeforces compiler and '9382' on my compiler (which is the expected answer)? I am using i686-apple-darwin11-llvm-g++-4.2 compiler.

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

    On this test your program produces

    /usr/lib/gcc/x86_64-unknown-linux-gnu/4.7.2/../../../../include/c++/4.7.2/debug/vector:336:
        error: attempt to subscript container with out-of-bounds index 65, but     
        container only holds 65 elements.
    
    Objects involved in the operation:
    sequence "this" @ 0x0x8058170 {
      type = NSt7__debug6vectorIiSaIiEEE;
    }
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    On my computer it also gives output 9832. I do not why this is happening. Same is happening with me in problem C with test case number 1. :(

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

    I have same problem with problem — C . My solution 3189369 failed on Test-3 ( According to Codeforces ) , But its giving expected 9382 on my pc( Ubuntu-12.04 ).

    When i tested here , its giving different result . Can anybody help me to point out errors in my code ..?

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

Как в С++ функцию xor (^) испольовать для long long? Я пробовал возвращает только int.

В чем разница между long long и __int64?

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

    Ни в чём: http://msdn.microsoft.com/en-us/library/cc953fe1.aspx "long long Equivalent to __int64." Разве что __int64 совсем нестандартный.

    Оператор ^ работает для long long так же, как и для других целочисленных типов.

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

    У меня ^ сработал нормально для long long. А разницы между __in64 и long long нет. В каком-то заголовочном файле прописана такая строка #define __int64 long long

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

      А функция сдвига (<< и >>) не работает для long long?

      l = 1 << 40;
      cout << l << ' ';
      

      Вывод: 0.

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

        работает, просто правильно писать l = 1ll<<40;

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

          а что значит 1ll?

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

            Это значит, что 1 у нас будет не int, а long long. По умолчанию, все целые константы имеют тип int.

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

Thanks for the contest, very nice problems, everything clear in the statement. I enjoyed this contest ;-)

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

My submission 3189731 failed for test 20. What's wrong with my code? On my pc it gives the correct answer.

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

the problems is very good for me

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

Funny, the same algorithm gave me TLE in java but not in c++. java -> http://ideone.com/wkFEuE c++ -> http://ideone.com/fsUknS Good Codeforces, nice way of discouraging non-c++ coders on your platform

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

    You have to know, that Arrays.sort in Java works in Theta(n^2) time for some arrays of n elements. Learn Java.

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

    sort() in java might degenerate to O(n^2), if it applies on an array of primitive type

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

      So, should I use Integer wrapper? it does not pass either.

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

        I recommend you to shuffle array before sorting.

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

          Is there any method to confirm if shuffle will always lead to a better performance? Also what exactly could be the cases when the Arrays.sort() leads to O(n^2). I am asking as the description given on official Oracle page is quite blurry.

          This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

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

            What is the probability that from a given worst case — order of elements, doing shuffle you will obtain the same order? The probability to win lotto is bigger than that :)

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

            Theoretically you can still hit the worst case after shuffle, but the probability of this event is negligible. You can see the anti-Java-sort testcase generator here.

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

              Actually, my generator is not working properly: recursion's depth is not maximal. There's a bug somewhere but I couldn't find it :(
              Nevertheless, it works about 2.5 sec. on Codeforces servers.

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

Почему это вот эта посылка дает ва 59, и если исключить этот тест полное решение

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

    Может, потому, что этот тест валит это решение? Ваш Кэп.

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

C. Little Girl and Maximum Sum

Whats wrong with my code( 3189369 ) ..??

Its giving correct solution for Test-3 on my pc(Ubuntu 12.04), but it failed . :O Does anybody care to explain it .??

Same code gave different output for Test-3 here :O Can anybody help me ..?

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

For problem B, what is the answer for "aabb" ? Below is what i feel, please correct me

The first player can for palindrome "abba". He takes off 'a'
Second player can form palindrome "bab". He takes off 'b'
First player cannot for a palindrome and hence Second player wins.

But correct official answer says "First". What am i missing ? Can some body explain how First player can win ?

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

    The first can already reorder the string to a palindrome.

    "If the player before his turn can reorder the letters in string s so as to get a palindrome, this player wins."

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

    The first player can for palindrome "abba". He is a winner! Second — losе

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

    player wins if he CAN form a palindrome before deleting operation

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

Прав ли я что stl-овский sort в с++ это аналог QuickSort?

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

    sort не совсем QuickSort (но похож). Там и QuickSort, и HeapSort вообщем много намешано...

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

    В G++ используется Introsort, который в худшем случае работает за .

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

for problem D... can anyone tell the answer of input is 15 and 17..?

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

Why did this submission generate WA? 3186879

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

The author's Editorial in Russian : Codeforces Round #169

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

Screencast of me solving this round.

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

Когда будет разбор? Хотелось бы разобраться как решать.

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

Hi, I would really appreciate some help debugging my code to problem E. I guess my idea is basically something similar to other people solutions, here is a poor described sketch of it (I apologize for that): ... (if you want to read it it is on the previous versions of this post ;) )

Edit 1:

Got Accepted! After debugging for 5h I made some small modifications and it passed the tests.. I am too tired now to check what the error was, I need some sleep :p, I will check it tomorrow and update this post!

Here is the accepted submission: ACC

Edit 2:

Found it! It was a very silly mistake (embarrassing), on naming who is the tail of the current branch. Thank you all and sorry for bothering :)

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

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

    English editorial was published 2 days ago. Please check my blog before making such funny jokes.