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

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

Всем привет!

Скоро, 24 января в 19:30 MSK, состоится очередной Codeforces Round #226 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.

Задачи были подготовленны группой авторов в составе — Алексей Чесноков (CleRIC), Кирилл Бутин (KirillB) и Иван Попович (NVAL). Это наш первый раунд на Codeforces и мы надеемся, что все пройдет хорошо.

Вам предстоит помочь герою задач — обычному медведю.

Благодарим Gerald, Delinur, Aksenov239 за помощь в подготовке соревнования и MikeMirzayanov за систему.

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

Удачи!

UPD: Раунд перенесен на 5 минут позже.

UPD: Разбор задач

UPD: Надеемся, что раунд вам понравился.

Поздравляем победителей:

  1. cptbtptp

  2. SquirrelDetected

  3. MahooshojoNHB

  4. Dong5k

  5. yada

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

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

November 29th?? When you click the link, it shows the correct time.

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

Fianally a new contest author for Div 2! Sounds good...

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

I think this is contes — very simple contest ! :)

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

New contest author, I am look forward this contest :D

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

It feels so good to be div1 and participate at these contests....It's so relaxing....

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

It is so relaxing to be a div1 and participate at Div.2 Friday evening...Thanks for the round!

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

good luck and have fun.

hope all get positive ratings :)

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

Only div2...But It doesn't matter.Just enjoy this contest!

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

Finally can join a contest without any pressure...

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

whats meant by "Div. 1 participants can take part out of the competition"?

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

Мне вот интересно, если див 1 участвует вне конкурса, могут ли они делать взломы?

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

I want to rating under color of my eyes... (red)

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

I was always curious why not just to add 2 more problems and make Div1+Div2 round instead of just Div2 one. It seems to me that the level of Div1 problems is not always very high — for example, take a look at D and E from previous round 225. They're just medium, not hard and still were not solved by a lot of contestants. I mean, one doesn't need to overestimate level of Div1 participants but it would me much cooler to have more frequent Div1 rounds.

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

why +5 min ?

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

5 minutes delay?
Why!?!

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

Страсти накаляются

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

А! О! Какой ужас! Перенесли на ПЯТЬ МИНУТ! Уписаться.

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

Как решать C ? и что там за четвертый тест?

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

    В четвертом тесте, некоторые L и R > 10^7. Нужно учесть этот вариант.

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

Как делать C без факторизации всех элементов массива? 1731 мс как бы намекают...

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

    По всей видимости, никак.

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

      можно. Если предпочитать для всех чисел наименьшее простое число в разложении.

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

        Ну подсчитали (по всей видимости, линейным решетом) и что дальше? Вероятно, как раз таки факторизовать эти числа.

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

          leastprime[i]= наименьшее простое число, вот таким образом делаем факторизацую

          while (x > 1) {
             primes.push_back(leastprime[x])
             x /= leastprime[x].
          }
          
          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            Это и есть факторизация.

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

              извиняюсь я кажется подумал что с факторизации :(

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

        Фрагмент кода вашей программы:

        	while (x > 1) {
        		int p = prime[lP[x]];
        		if (ls != p) cnt[p]++;
        		x /= p;
        		ls = p; 
        	}
        

        Что это, если не факторизация?

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

          у меня такая же идея, по почему то не пашет 4 тест((

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

    Just calculate for each prime number of its multiples that are in the given set. The complexity will be N / 2 + N / 3 + N / 5 + N / 7 + ... = O(NlogN) where N is a maximum possible number (107).

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

      Я не знаю, что на меня нашло, но я ответил по-английски, хотя знаю русский:)

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

        На самом деле, там чуть лучше асимптотика ;)

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

Solution for B with n^2 complexity passed my hacking test :'(

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

    B is supposed to be solved in . ofcourse it will pass the hack!!

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

      There is an O(N) solution also.

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

        can u plz share the idea with us?

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

          For each occurrence of "bear", you have to count the number of valid indices to the left of this, and to the right. It will contribute countLeft*countRight number of tuples. For each "bear", left count will be the number of characters from 'b' of previous "bear" to this 'b'.Right count will be number of characters from this 'r' to the end of string.

          You can check my submission(5788550) for details.

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

    Man, just a piece of advice for you. On Codeforces if you wanna hack somebody on time limit, you gotta be sure, that his/her program will perform at least 10^9 operations on your test. Because the servers are really fast. On this contest I tried to hack a program, which performed in the worst case about 4*10^8 operations, but the result was just 1668 ms.

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

Из-за лагов на последних секундах не смог перепослать задачу :/

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

Couldnt submit my code in last 20 seconds :-@
Again loss of rating :-(

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

at last minute codeforces was unavailable, So I couldn't submit my soln.Did someonne else have this problem?

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

Couldn't submit a problem in the last two minutes because of constantly getting the message "Codeforces is temporary unavailable "

I really hate this!!!

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

Hello,

I need guidance on problem B.

Can it be solved by suffix array?

I thought of using suffix array + lcp to get all substrings only containing bear and count those.. Maybe even suffix tree was better choice but couldnt implement it yet.. was that the way to go?

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

    nope, solution is very simple. For each "bear" count positions on left from which we can start, it will be (i — prev 'bear' position), because we shouldnt use the positions already used by previous bear and positions on right on which we can end, it will be = n — i — 3. then increment ans to rightcount*leftcount, and change last bear index.

    sorry for bad explanation. if you disunderstand then look to others code

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

Codeforces is temporary unavailable :(:( It cost me hack in the last minute :(

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

Whats the idea of problem C ,i got TLE.

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

I liked problems very much,exceptionally problem C,thanks CleRIC for great contest ;)

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

I wasted 10 minutes to write a generator. It only gives the error that first line should not be empty.

http://codeforces.com/contest/385/hacks/91276/test

Can anybody help me why is this happening ??

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

Спасибо Вам! Отличный раунд!

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

For problem D constraint n <= 20 suggested that something like bitmask dp could be done. But I can not find any reason why not to use just all the flash lights instead of a subset of them ?

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

    Not sure but I think this is because the order of lights matters.

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

      I got the idea, infact it is true that all the lights can be used. But the bitmask can be used to extend intermediate result dp (mask) to dp (newmask) easily using geometric manipulations.

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

My hack #91170 was marked as unsuccessful. But the details contains "Time: 2152" and this problem (Problem C) has 2 seconds time limit. Doesn't 2152 > 2000?

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

    in the last two contests, i saw problems with time limit of 2 seconds, and submissions that took 2011 ms got accepted.

    wait 2-3 mins, i will post the links.

    EDIT: sorry for the delay, but finally found them! 5722902 5706257

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

    I'll handle it. Already has found the issue. Thanks.

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

    There may be something wrong.
    I found a successful submission for problem C which takes 2245ms to execute. 5796553
    And I hacked a code which causes TLE, according to verdict, it ran 2000ms.

    To keep contests fair, this problem should be deeply discussed.

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

What a "runtime error" contest!

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

How solve problem E?

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

What was the idea behind D? (n<=20 sugests that the problem is NP for bigger values of n). Was is something like meet in the middle?

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

    More like travelling salesman dp. For every subset of lamps store the farthest point that can be reached using them. When adding a lamp to a subset it is easy to see, how much it extends the reach.

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

    I just solved D, the dp[] size is (1<<n), than every step only turn on one unused light and update dp[cur|(1<<k)] (k is the unused light)

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

For the first time, my rating is going to go above 1500 (hopefully) :)

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

Any idea why http://codeforces.com/contest/385/submission/5798194 gives a run time error. But uncommenting the commented lines doesnt give. I cant see what fails.

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

    yes, i have the same mistake, the thingis that s.size() is an unsigned int... and when it is 1 and substract 3, it is 4294967294, because all the expresion is indeed unsigned int, and then when you access to the element 4294967294 of the string it give you RE, because it only has 1 element.

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

    I think there is nothing wrong on your code. but the compiler make infinte loop but I don't know why.

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

    because s.length() is unsigned int

    and by negating 3 from it, it will give another unsigned int, so

    s.length()-3

    will be some non-negative number

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

Rank 2:SquirrelDetected Registered: 4 hours ago(Before Contest)
Rank 3:MahooshojoNHB Registered: 7 weeks ago(Before Contest)
Rank 4:Dong5k Registered: 4 hours ago(Before Contest)
Rank 6:Uni Registered: 4 hours ago(Before Contest)
Rank 7:FastYes Registered: 3 hours ago(Before Contest)
Rank 9:akatsukiLH Registered: 9 hours ago(Before Contest)
The NEW brains...!

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

Can Someone Explain problem E in details (i.e : How the matrix was built?? )

// So far I go...
   |  1 0 1 0 1 0 |     | sx |
   |  0 1 0 1 1 0 |     | sy |
   |  1 1 1 0 1 0 |  *  | dx | 
   |  1 1 0 1 1 0 |     | dy |
   |  0 0 0 0 1 1 |     | M  |   M= Number of moves so far
   |  0 0 0 0 0 1 |     | 1  |   1= Constant term to increase M
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well, instead of the first 4 zeros in the last column, they all should be 2. I got a WA during the contest because of this stupid bug. Note that you need to decrease sX, sY by one to turn the coordinates to 0-index instead of 1-indexed to make it easier, consequently, you will need to add 2 to K in each step.

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

      Why they first 4 zeros need to be 2 ? What is the logic behind this?? I don't understand.. And when sX or sY is greeter than N we need to mod them by N ... how to apply mod N operation in matrix multiplication?

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

        Well, we will be working with 0-indexed coordinates, ok? Now, dx is updated as follows dx = dx + sx + sy

        But since we are working with 0-indexed coordinates then this should be dx = dx + sx + sy Why? Assume sx == 1 && sy == 3 in 1-indexed mode, now when we turn it to 0-indexed then we have sx == 0 && sy == 2, so dx should equal sx + sy + 2

        Now for modding by N part, you can mod every thing by N in every step of your calculations, because the only operations you do are addition and multiplication, and the mod can be distributed over these operations normally

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

MikeMirzayanov, пожалуйста, добавте возможность скачивать тесты или каким-то другим образом просматривать весь тест, ибо уже не первый раз по началу теста невозможно определить как он выглядит, почему решение валится и что делать((

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

    писать стресс!!!)

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

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

      где я ошибся?))

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

        Часто, если решение получает WA, то можно действовать по следующей схеме:

        1. Пишется генератор небольших тестов (достаточно небольших, чтобы и на них могло не заработать, и было не так сложно отдебагать)

        2. Пишется простое решение, которое точно будет работать (пусть и долго на больших тестах).

        3. Запускается батник, который по циклу (сгенерировать тест)  →  (прогнать оба решения)  →  (сверить ответы) не найдет тест, на котором основное решение не будет работать :)

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

    А у меня слетела, потому что не проверял случай, когда слова "bear" вообще нет. И как-то странно, что в претестах не было случая, где нет "bear". В дорешку сдал.

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

My solution of problem C fails on pretest 7. I just used a BIT with sieve of Eratosthenes. I can't find the mistake. Could someone help me find it? Thanks.

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

    just skimmed.. i guess you should run another loop inside this loop for multiples of i when notp[i]=false

    for(;i<mx;i++) if(!notp[i]) update(i,cnt[i]);

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

In recent contest, there are Div1 users that register a new account to participate officially!!
Why? What's the difference?
Then Div2 users should compete with some Div1 users, too!

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

where can i find test file for a particular case that my solution fails

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

Can anyone tell me why the first code got runtime error while the second got accepted ??? 1. http://codeforces.com/contest/385/submission/5791451 2. http://codeforces.com/contest/385/submission/5798703

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

Kept getting Runtime error on 385B - Bear and Strings Spent much time to figure out it..

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

Хороший контест, задачи интересно решать

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

Your first contest very good held.Thanks for this interesting contest :) CleRIC KirillB NVAL...!!!

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

Your first contest very good held.Thanks for this interesting contest :) CleRIC KirillB NVAL...!!!

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

The problem D is about Greedy and Geometry? I have no idea about it! Who can help me ?Thanks.

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

Thx for contest, it was my first contest that i get +rating) thx a lot)

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

CleRIC did a great job for his first time as contest writer, the problems were full of quality