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

Автор awoo, история, 7 лет назад, перевод, По-русски

Привет, Codeforces!

21 августа в 18:05 по Москве начнётся Educational Codeforces Round 27.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Раунд будет нерейтинговый. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Иван BledDest Андросов, Владимир vovuh Петров и Михаил MikeMirzayanov Мирзаянов.

Удачи в раунде! Успешных решений!

У Harbour.Space есть для вас небольшая речь:

We are delighted to welcome the 2017 ACM-ICPC World Champions, ITMO, to our 2nd Hello Barcelona Programming Bootcamp in collaboration with Moscow Workshops ACM ICPC starting September 27.

All the top Russian teams are coming, including St. Petersburg State University, MIPT, Ural Federal University, Tomsk, Novosibirsk, Saratov and Perm, as well as the world’s top universities such as Waterloo, Central Florida, Hangzhou Dianzi, Singapore, KTH and dozens of others — so far teams from 30 countries have signed up.

The event’s gold sponsor is Sberbank, the biggest commercial and investment bank of Eastern Europe and Russia. Thanks to their support we expect that the top participants will be awarded valuable prizes, alongside high-profile internship and job opportunities.

We can’t wait to see all of you coming to learn, practice and compete on the international stage, smoothing your road towards April World Finals in Beijing.

Ps. Registrations close on September 1.

UPD: Разбор доступен по ссылке

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

Rank Competitor Problems Solved Penalty
1 uwi 7 288
2 quailty 7 314
3 Andrei1998 7 318
4 rajat1603 7 374
5 fatego 7 374

Поздравляем лучших взломщиков:

Rank Competitor Hack Count
1 uwi 455:-11
2 halyavin 305:-4
3 STommydx 103:-2
4 Lhtie 48:-2
5 step_by_step 44:-28

Было сделано 1326 успешных и 300 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Problem Competitor Penalty
A ksun48 0:01
B ygmngm817 0:03
C markysha 0:03
D EKGMA 0:10
E halyavin 0:37
F eddy1021 0:34
G const_int_magic 0:08

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

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

why is the Announcement too late?

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

I want nothing but a clear problem set.

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

Is it rated?

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

    Lucky for you, it is!

    "Educational rounds" are a GREAT way to increase your rating!

    I wish you high rating in every upcoming educational contest!

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

What is high-profile internship?

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

"After the exam Polycarp can justify his rule violations by telling the driving instructor that he just didn't notice some of the signs."

Unfunny meme amirite

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

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

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

How to solve E and F?

Is this a valid approach for E:

2D ternary search to find the placement of the (k + 1)th center of ignition and then binary search to find minimal time. The complexity will be which is about 300 mln operations and should fit in TL. The only thing I'm curious is if the ternary search will be correct.

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

    for E
    Consider binary search on answer
    Find leftmost line which will have atleast 1 unvisited cell , similarly find rightmost , topmost line and bottom-most line
    This is valid if (right — left) <= 2 * x and (bottom — top) <= 2 * x if we are checking for x.

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

      How to find leftmost line and other 3? You find leftmost of these k burning points, and then k — x but problem is if k — x < 0, i mean if that point is pretty close to left border.

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

    for F If N > M just transpose it
    So now N ≤ 15 , so just do dp with bitmask

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

could anyone explain to me the first test in D ?

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

I got WA at Test Case #8 in problem D. Couldn't figure out why?

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

    When you get new speed of car, you cant only check last speed limit. You need to have stack with speed limits. Example you have signs with speed limits of 100,120,150 respectively. Then , you drive 160 and you only check last speed limit which is 150. But you also must care about signs 100 120. So , maintain a stack of speeds, go back while speed.top() < curr_speed and increase counter. You can see my solution at my profile.

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

      So by that, you mean with this test case

      4 1 50 3 50 3 100 1 60

      The ans 0 instead of 1? Could you explain to make more sense to me or point out which part of the problem exactly define this criteria? Thanks

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

        Of course answer is 0, how can it be 1? You drive 50 while limit IS 50 so its OK, then you switch to 60 while limit is 100, thats OK as well.

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

          I mean when the speed limits are 100, 120, and 150, and you drive 160, the 100 and 120 is included in the violated signs, right?

          But, why when the speed limits are 50, 100, you drive 60, the 50 limits doesn't noticed too (unlike above)?

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

problem G is this with Q = 1

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

4

1 100

3 50

3 50

1 50 why is the ans 2

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

    You only need to remove (or "didn't notice") two road signs to drive without violation

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

      even 1 can be the ans because after the second sign he changed the speed!!

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

        Yeah, I agree that one is more make sense. But, I've clarified similar question to the problem setter, see below.

        Question: 3 1 100 3 50 3 50 The ans is 2

        Question: 3 3 50 3 50 1 100

        The ans is 2

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

    Because you are passing two signs with maximum 50 with speed 100.

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

how to solve G ?

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

    If there is a cycle in the graph with cost C, for every path of cost x, there is one with cost x^C.
    So you can check out all the costs of simple cycles (get a spanning tree and check for each edge) and the shortest paths will be x^C1^C2... where x is the cost of any route you can find.
    To find the minimum of this value we can translate the problem to linear algebra, the XOR is the same as the addition in Z/2 space, so if we treat these costs as a vector, then we can find a linearly independent set which generate these vectors in the ZMXBITS/2 linear space using gaussian elimination.
    Now we can simply get any distance from 1 to n, and XOR with the elements of the basis greedily from the most significant bit to the least.

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

      what do you mean by "Z/2 space",please?

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

        The Integer modulus 2 vector space

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

          Is this advanced usage of linear algebra or some bacics? Are problems where u need to use linear algebra conceptually hard (for example this one) or, when u learn linear algebra, its natural after some thinking? Because when I see linear algebra im like wtf who can come up with solution for this

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

      Can you please explain me one thing....i understand that gaussian elimination method for minimising xor value but how can we say that number of simple cycles will be atmost 30...because gaussian elimination will take n^2logn(rows=n columns=30 bits)..

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

Alert!!! Alert!!! UWI started hacking!!!

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

Anyone could kindly explain why Wrong Answer on Test Case 8? Thanks

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

    in case if t==3 you might be changing previously increased speed in query 1 to -inf and than you pushed the speed limit in stack;

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

    Try this test case-
    5
    1 80
    3 120
    3 130
    3 140
    1 150

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

Can anyone tell me how there are this many solutions for G? I saw solution uses linear algebra. Isnt it really advanced topic for competitive programming? Anyone has any materials with codes for linear algebra?

Problem E is much easier in my opinion, but has less AC. Also, this is maybe the case because problem G appeared on codechef before (in even harder version).

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

4 1 100 3 50 3 50 1 50 who agrees with me that the answer should have been 1??

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

    No one. You drive with speed of 100. You see a sign with limit 50, you dont give a shit, so res++ You see one more sign with limit 50, you dont give a shit again, res++

    Totally, you must lie about 2 signs, because you didnt slow down TWICE, not ONCE. Result is therefore 2.

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

      the second time i see it and change the speed!! i could just say that i didnt see the first sign but as soon as i saw the second one i changed the speed after that!

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

        He changes the speed only when there is a type 1 event, otherwise he keeps the same speed.

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

          ok so is it like this that i should change my speed before the next speedlimit sign comes?

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

            Yes, exactly.

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

            Yes. When type 3 appears, it means you already passed sign with given limit. So you need to change speed BEFORE you see a sign.

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

    If you eliminate one of the speed signals you are left with 4 1 100 3 50 1 50 which is still a violation of the rules (when you cross the 50 limit you are travelling at 100). You need 2.

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

Why there's no sample explanation in problem A,B,C.

Thinking a harder version of the easy problems took up most of my time just because I misunderstood the problems!

:(

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

    Or maybe I'm too careless.....

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

      Careless I would say xD I solved first 3 problems in half an hour. This is my best contest ever (place 212. and you see how bad my rating is). So, If u just read carefully...

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

Помогите, пожалуйста!

Вот моя программа для задачи D: http://mirror.codeforces.com/contest/845/submission/29666261. Я пытался решить её, создав вектор скоростных ограничений. Но получил неправильный ответ, когда количество событий было велико.

Подскажите, пожалуйста, что я делаю не так.

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

Help me, please!

Here is my program for problem D: http://mirror.codeforces.com/contest/845/submission/29666261. I tried to solve it using the vector of speed limits. But I get "Wrong_Answer" when the number of events was great.

Can you, please, tell me what I'm doing wrong.

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

Almost everone solved problem G in same fashion ( finding basis and all ), is this some standard method for dealing with this type of problems? can anyone give any link to some theory and more problems on it.

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

Me Right Now..

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

7 1 20 2 6 4 6 6 2 In the third example Polycarp should say he didn't notice both "no overtake allowed" that came after "overtake is allowed" sign. Any explain for me? I think it doesn't makes sense.

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

    If he doesn't say that, then the last overtake would violate the rules (he overtook another racer when overtakes weren't allowed)

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

Now its halyavin.. :3

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

Can someone provide a test for which this doesn't work? http://mirror.codeforces.com/contest/845/submission/29651836

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

Full test cases are visible even when 24 hour hacking phase is running, but they should not be visible.

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

Could someone point out where my code for problem-D is giving error? Link is https://www.ideone.com/VjSB5c Thank you.

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

    It's not enough sometimes to delete the previous sign. For e. g. if there is a speed limit sign of 50, then a speed limit sign of 30, and after that he goes with 100 speed, then in your code he only has to say he didn't see the 30 sign, but then he should think the speed limit is 50, so he is still speeding.

    Also you don't reset the speed limit after deleting a sign, so if there is a 30 sign, he goes with 50, then he goes with 70, then you add 2 to ans instead of 1.

    Solution: