Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке: https://t.me/codeforces_official. ×

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

Автор Zlobober, 9 месяцев назад, По-русски,

Всем привет!

Сегодня состоится первый тур Открытой олимпиады школьников — личного соревнования по программированию, ежегодно проводящееся в Москве. Над составлением соревнования работала Московская методическая комиссия, известная вам также по Московской олимпиаде для 6-9 классов, Московской командной олимпиаде и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466).

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

В связи с этим мы просим всех участников сообщества, собирающихся участвовать в соревновании, проявить уважение к себе и другим участникам соревнования и не пытаться читерить никоим образом, в частности, выясняя задачи у участников соревнования в Москве. Если вы узнали какие-либо из задач Открытой олимпиады (участвуя в ней лично, от кого-то из участников или каким-либо иным образом), пожалуйста, не пишите раунд. Участников олимпиады мы просим воздержаться от публичного обсуждения задач. Любое нарушение правил выше будет являться поводом для дисквалификации.

Раунд состоится в 11:05 9 марта по Москве и продлится 2.5 часа. В каждом дивизионе будет предложено по 6 задач.

Задачи раунда были подготовлены ch_egor, sender, flyrise, _kun_, malcolm, grikukan под руководством вашего покорного слуги с методической помощью от _meshanya_, GlebsHP, Endagorion и Андреевой Елены Владимировны. Часть задач для div2 была доработана командой Codeforces в лице fcspartakm, также важный вклад в виде обсуждения и выбора конкретных задач внёс координатор Codeforces KAN.

Всем удачи!

UPD: Email-рассылка о раунде содержит неправильной информацию о времени старта раунда и продолжительности. Вместо "12:05 9 марта, 2 часа продолжительности" должно быть "11:05 9 марта, 2.5 часа продолжительности", как было с самого начала указано в анонсе раунда.

UPD2: Раунд перенесён на десять пять минут, но мы полны энтузиазма :)

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

Division 1:

  1. dotorya
  2. Swistakk
  3. Syloviaely
  4. zscoder
  5. dreamoon
  6. SkyDec
  7. Marcin_smu
  8. yutaka1999
  9. Kostroma
  10. Will_Dearborn

Division 2:

  1. _ChenKerui
  2. Demerzel_IV
  3. 879333752
  4. yyc_jm
  5. Anson529
  6. iotang
  7. wcz112
  8. Hankpipi
  9. cyz666
  10. wwd2075

UPD3: Разбор наконец появился! Спасибо gritukan и ch_egor за воплощение его в реальность.

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

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

Very bad time plz extends start time..

»
9 месяцев назад, # |
Rev. 4   Проголосовать: нравится +26 Проголосовать: не нравится

The time is right for Chinese students! That's great!

UPD: The Problem was fixed, and wish everyone will increase your rating.

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

    Maybe we should say "Perfect time for Asian users" :P

    (Although I found that I have to skip some classes just now if it actually begins at 16:05, March 9th, UTC+8...qwq...)

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

      Not sure if perfect for all of us, as some (including me) still have school during the time.

      Now I have to decide on whether to do contest or to attend class (most likely I won't :p )

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

    The time in the blog is the correct one, it is same on the contests page and in the blog now.

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

Will this round happen at 11:05, March 9th, Moscow time? But in CONTESTS, it will start at 12:05, March 9th, Moscow time. When can I enjoy it? (sorry for my poor English :(

UPD: Maybe Johnson_sky found another difference?

UPD2: The Problem was fixed. Wish everyone have fun.

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

    The time I showed was UTC+8, so I didn't notice the difference in the start time.

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

      utf-8 ? Do you mean UTC+8 ?

      In the blog, 11:05, March 9th, MSK == 16:05, March 9th, UTC+8 .

      But in the CONTESTS, it is 17:05, March 9th, UTC+8 .

      Obviously, they are different.

      And thanks for that you found another difference.

      UPD: The problem is fixed.Have fun.

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

...под руководством вашего покорного слуги...

Как то... Стремно...

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

Codeforces Round #469 (по задачам Открытой открытой олимпиады школьников)

Исправьте.

UPD Исправлено.

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

I don't know if I should skip the math class tomorrow to participate in this contest.

PS: Now it coincide with my midterm exam...

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

I hope this contest can help my rating increase to 2000+

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

Perfect time for some Asian OIers...At least for me...

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

I like this website .I have never experienced this exciting feeling before.I like these competition.also I am a newer ,I will fight.

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

Wow, this round starts after my University exam. So no problem in attending. I wish everyone good ratings.

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

I have lessons at 14:00(UTC+8) and it will lasts for 2.5 hour. So I can take part in this round if it will start at 17:05(UTC+8) but it moves to 16:05.... how disappointing.

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

Hope the statements as short as the announcement, wait it's not short :|

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

Perfect time for Asian users!

Nope! It seems to be Dinner time...

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

Something is wrong here. Originally it was 12:05. I also remember checking the time in the contest tab. Also in email it was mentioned 12:05 and now you are moving the whole contest by one hour just because you wrote this in the announcement?

First thing is that you should not move it. Announcement could be easily adjusted. Perhaps very few people clicked the url with time in this announcement. It is also a very short time for such a change.

Second thing is that you should send at least one more email with the correction. Why do you assume that everybody regularly checks main cf website instead of their email?

This round is already in an unusual time. If you won't make sure that everybody is informed about the change, the participation level may be very low but the frustration very high as a lot of people will appear here at 12:05 to discover that contest will have been running for an hour already...

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

    Agreed. If it was postponed that might be acceptable but now many will turn up too late for the contest.
    Lucky I happened to check this post once before going offline right now or I would have missed it too.

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

    I check cf more often than e-mail.

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

    Sorry, my fault. I found that the times changed just before a long train trip. I decided that the announcement in the post + the note in a registration form are enough. During the train trip I was out of Internet without any chance to send extra emails.

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

      I guess your train trip is over. So why you still haven't sent the notification?

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

        It finished ~30 minutes ago (I've sent the previous message from the train via phone). Anyway it takes 2-3 hours to send emails.

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

          I see. Just in case, I didn't mean to be offensive. Thank you for all that you are doing for CodeForces!

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

i will participate,when ever, what ever happend..

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

    my laptop battery is empty due to power outage for more than 12 hours now... wind storm cut Power cables .. so I did not participate. my luck ..

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

I'm really thankful to Zlobober and MikeMirzayanov for one more CF contest.Good luck for everyone.Only high ratings. :)

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

My score around the 1590 some times,hope I can overstep 1600,good luck to everybody!

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

    I can't overstep 1600 again,so sad.final test C is wrong answer.God always jokes me.......I must be overstep in tomorrow

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

Delay :|

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

Postponed by 5 minutes... You really want to confuse people...

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

"UPD2: Round is postponed by 10 minutes. Stay tuned :)"

it only says 5 on contest page

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
UPD2: Round is postponed by 10 minutes. Stay tuned :)

*5 minutes

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

Fun contest! Enjoyed the problems, especially Div 2 D and E (Div 1 B and C).

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

    is there anything to do with MST in div2E

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

      No, there is no MST

      There is Strongly connected components of directed graph.

      But I'm not sure if my solution correct or not. But pretests were passed

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

    How did you solve E?

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

      Didn't solve it in time, but I think I had the right idea.

      Basically, you create a dependency graph. That is, the vertices in the graph are the datacenters, and you draw an edge from datacenter A to datacenter B if bumping A's time an hour would force you to bump B's time as well. (That is, if an item x is stored in A and B, and B's time is the hour directly after A's time.)

      Then, the problem boils down to: I want to find the vertex in this graph, for which, if I pick it, the number of vertices that I am therefore forced to pick is the smallest possible. (In terms of the graph, this means that I want to pick the vertex v, who can reach the fewest number of other vertices.)

      So, we can observe that in any dependency chain, or dependency tree, or dependency DAG, we can always just pick some datacenter at the end of the dependencies — i.e. some datacenter, which might have edges coming into it, but no edges coming out. Then, if we pick that guy, we aren't forced to pick anyone else. So our answer is 1.

      However, if there are cycles, then it's trickier. If a vertex is part of a directed cycle, then we can't just pick a vertex at the "end of the chain", since there is no end of the chain. Picking any vertex (datacenter) in that cycle forces us to take EVERY vertex (datacenter) in that cycle. More generally, taking any vertex in a strongly-connected component implies that we have to take the whole SCC. So, the problem then boils down to: we want to pick the smallest SCC that has no outgoing edges. We can use Tarjan's or Kosaraju's to get the SCCs of the graph, and then find the smallest SCC with no outgoing edges.

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

        good explanation , I was thinking like what happens if chain length is more than h then it would be contradicting but if chain length is more than h then it wouldn't form a cycle .

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

Hacks?

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

我是中国人

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

Hmm... does anyone know about pretest 9 of Div1A/Div2C and Div1C/Div2E?

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

    Can anyone give the full solution of E? Mine had something to do with the minimum sized SCC of the induced hour-based graph but failed on pretest 4.

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

      I basically did SCC, and then you know that SCCs make a DAG, so you find the vertex with out-degree 0 in the DAG that has the smallest SCC size.

      Note: SCCs are of the graph where (v, w) is an edge if (v, w) share some data and (u[v]+1)%h = u[w]

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

      I did same and my code failed on pretest 5

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

      My solution is also based on SCC as well. I used Tarjan's Algorithm to have the SCCs sorted topologically.

      Anyway, it seems like I know what I did wrong, but I'm not so sure (since I couldn't find for myself any cases to prove it). If I was right, the mistake was in my way to choose the correct minimum-size SCC to answer.

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

    My original code for Div1C/Div2E got WA on Pretest 9 and I found a bug. For the test:

    5 6 4

    3 2 1 0 3

    5 4

    4 3

    2 3

    2 5

    2 4

    1 4

    My code would say the answer is 5, but the answer is 4 (just take 2, 3, 4, and 5). I don't know if yours also failed the same way, but the main idea was that cycles broke my initial algorithm.

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

      Well sadly mine returned the totally correct answer. Should be another case...

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

    My first wrong solution failed on 9-th pretest. The antitest for the solution was:

    00110100
    

    One of the correct answers is:

    2
    5 1 3 5 6 7 
    3 2 4 8
    

    When mine output -1. Check yours, hope it is what you search for.

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

    It is just 000111000111...111000 (block with len 3 repeated 66665 times).

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

      Can you clarify more? Are they 66665 three-digit blocks alternating?

      And the answer isn't -1, right?

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

        (000)(111)(000)(111)(000)...(111)(000)

        Answer is yes.

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

        You can see that one of the answers is 3-sequences length 66665: 0101010...01010

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

        Ouch, I understood my mistakes now. Perhaps I should redesign another approach for this problem.

        Thank both of you, ch_egor and nikich340 for helping me out! ;)

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

          Yes, your answer output -1 on short version of that test:

          000111000111000

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

bad explanation for B div2 :|

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

Div2B statement is horrible.

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

How to solve Div2 D?

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

    Yes, I saw that 549 passed it and feeling that I'm a bit stupid :P

    I managed to solve only the inverse task (find final position of some number).

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

      Here's a kind of hand-wavy explanation

      The optimal strategy is to always move the rightmost number.

      If you simulate a decently sized example (like n=8), you can note that essentially every odd-indexed number stays where it is, and there's a steadily-moving contiguous "blob" of numbers moving from the right to the left.

      Given an index i, we want to find out the index that it originally came from. To do this, first, let's try to find the index that it came from on its most recent jump. Let's say n=8, and we're looking at index 4 (using the 1-based indexing in the problem). (I highly recommended drawing out this example and simulating it. If you've done that, you'll see that the number that ends at position 4 is 7. So we want to find out where 7 was before its last jump.)

      Every jump that takes place is of the following form: it's a number leapfrogging from the right of the blob/train to the left. And it's leapfrogging over ALL the numbers in the trainblob.

      So, if we can figure out how big the blobtrain was at that point in time, then we can figure out how far our number leapt to get to where it is now. Well, we can note that every number that started to the left of index i has not moved yet. And, every other number besides those must be part of the train. So, the amount of numbers in the train is n — numbers_to_the_left_of_i.

      By examination, we can see that there are i/2 numbers to the left of i. So, the amount of numbers in the train that 7 leapfrogged over was n — i/2 = 8 — 2 = 6 (including itself). So the position that it came from was i + (n — i/2). And before the 7 was at that previous position, we can calculate its previous-previous position in the same way. We can iterate that i = i + (n- i/2) calculation until i is odd, which is its starting place. And the value of the number at a given position p is (p+1)/2

      edit: Tl;dr read xiaolongbao's comment

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

      How do you do the inverse task?

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

        I found position differences for all numbers in small array(8, for example) and find the next pattern:

        1: []
        2: []
        3: []
        4: []
        5: [7]
        6: [5]
        7: [3, 6]
        8: [1, 2, 4]
        

        So, initial position for number x is a = 2x - 1, initial position difference is k = 1 + 2(n - x), which doubled on each iteration. Reduce number position while we can do it.

        int get_pos(int x) {
           int a = 2*x - 1;
           int k = 1 + 2*(n - x);
           while (a - k > 0) {
              a = a - k;
              k = k * 2;
           }
           return a;
        }
        return k;
        
    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Same with me .

  • »
    »
    9 месяцев назад, # ^ |
    Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится
    lint getAns(lint now){
        if(now % 2 == 1){
            return (now + 1) / 2;
        }else{
            lint x = n - (now / 2) + now;
            return getAns(x);
        }
    }
    

    that is all, if u still have problem can reply me

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

      any logic explanation?)

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

        u can see the kwangg's explanation. it's very detailed

        now, i explain my code

        it's obvious that if the num which less than n/2 will fixed

        for example n = 6:

        1_2_3_4_5_6 -> 142635
        

        1 and 2 and 3 is fixed

        so

        if(now % 2 == 1){ return (now + 1) / 2;}
        

        if u wanna find the ans of position 4

        1_2?3_4_5_6
        

        when a number will go to position 4 , you can know that there is no space in the back of position 4, and the number which position is 8 will go to position 4, so u just need find the number which will go to position 8, then recursion.Until the beginning, there is a number in this position. Obviously, at the beginning, the number must be in the odd number.

        lint x = n - (now / 2) + now;
        return getAns(x);
        
»
9 месяцев назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

I belive that everybody wrote this contest right.

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

Anybody initially stuck on test case 9th of (Div2 C/ Div1 A) and then later able to successfully surpass that??

I m still getting WA on 9th test case :(

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

    Yes. Though I was stuck in this case for only 5-10 minutes, still this might help. First of all, the test case is 000111000111000...000 for 66665 times. The length really doesn't matter, the shorter version f this input is 000111000111000. What you may have done wrong is that you may haven't considered detecting 01010 type of strings with multiple 1's. In other words, this test case is the combination of 0101010 (long zebra string) and 001100 (overlapping zebra string). I handled each of them separately, but test 9 got me. Got AC after correcting this bug. I hope this helps.

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

    A straightforward implementation of Div1A/Div2C using sets passes.

    See this http://codeforces.com/contest/950/submission/36136531

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

Нет в мире справедливости))))

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

anything special about test 15 in F? And should there be answer YES or NO?

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

    Just some random test with answer "Yes" and n = 2600.

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

      Anything special about test 7 :D?

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

        Small manual test.

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

          Duh, I got WA on it because of overflows and I lacked few seconds to submit version with define int long long which already passes this test. I hope that my final version will not get AC (I think it won't), otherwise I can be declared incredible loser :P.

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

Can anybody please explain the complexity of my code for problem Div2 C. I think it will fail system test.

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

Div 2 D?

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

    If you're looking at an odd index, print the number that was there originally, i.e. (i + 1) / 2.

    Otherwise, assume that that location is currently the rightmost blank not filled in. For example, with N = 7, if we're looking at index 4:

    1_2_37465

    The number which will occupy the second blank is equal to the rightmost number in the current list. There are no blanks to the right of index 4, and there are 2 numbers to the left of index 4. In general, there are i/2 numbers to the left of a blank. Thus, there are N - i/2 numbers to the right, and since they're all filled in, we can say that the answer for index i is the same as the answer for i + N - (i/2).

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

      Very nice explanation. Thanks.

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

      any intuition on how to calculate the time complexity of the above solution?

      Upd: Nvm figured it out. this seems similar to a binary search relation where Right is always 2*N and Left keeps becoming MID.-->(left + right)/2 --> i = (i + 2*N)/2.

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

Two identical codes with just reformatting from moamen_ahmed and BaSSam_RaMaDaN.

Here are the submissions: 36101349 and 36100512.

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

Oh boy..

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

Idea for div2 E?

»
9 месяцев назад, # |
Rev. 9   Проголосовать: нравится +64 Проголосовать: не нравится

Congratulations zscoder !

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

    Thanks for the wish :)

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

      I get motivated by your rating graph. I also showed my friends. This is what never give up. Congratulations...

      I am a newbie and I feel sad. I know much more thing but in contest 1-2 problem-solving.After the contest I have done the problem but problem in the contest. Please give me some suggestions so I can improve my coding skill. I am waiting.....****

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

    I also congratulate to Yuta yutaka1999 Takaya for being legendary grandmaster!

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

How the hell could this guy jackichul solve D just 3 mins after E? And his solutions of D and E also had different style from A, B and C.

  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. She/He may have seen this problem earlier and simultaneously thought about D and E and/or C or anything. I can guess because I did the similar thing too, only for 10-15 minutes though.
    2. Also, this Div2 D problem was too easy. I solved it in under 8 minutes, though the contest page won't show that because, as I said earlier, I was busy debugging my C problem at the same time. So, yes, it could be done in 3 minutes, not impossible. A bit surprising, but nothing odd. I hope it clears your confusion.
»
9 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

36111831 can anyone help me to find out the runtime error??? TIA

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

That feeling, when you realize your solution is wrong and you know how to fix it :) But you had already locked the problem...

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

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

How to lose 10 places for nothing:

Write endl instead of '\n' in B, but pass pretests anyway. Panic and resubmit.

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

Hello Sir. What is intended solution for problem div1. F. My friend from Russia say that author solution is . Is it true? KAN ch_egor sender flyrise _kun_ malcolm gritukan _meshanya_ GlebsHP Endagorion

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

    Is it true?

    No. Author's solution is O(n2). Stay tuned for the editorial.

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

    My solution (that should be quadratic on a random instance) gets TL on test case 17. Not surprisingly.

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

What is wrong with the 55th test case in problem Div.2E/ Div.1C?

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

q

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

Div1D/Div2F solution?

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

How to solve problem Div 1 D ?

My idea is as follows -

  • From the initial arrangement, greedily try to send right half ( = n/2 * b) of the students towards right. And remaining towards left.

  • At any instant, when first instructor is at room i. All students till room (d + 1) * i can reach to the room. So at moment we know maximum how many students can reach room i. Call this lsum. Also, let's keep track of how many students are are locked in rooms with room number less than i, call this lused.

  • Now if lsum - lused >= b we will lock b of them in current room. And conceptually push remaining to next room, i+1. After this, lused += b.

  • If lsum - lused < b we will lock lsum - lused of them in current room. In this case we increase counter, c1 += 1 indicating this will be reported by the instructor.

  • Similarly we will proceed from right side, (left and right both proceeding simultaneously).

  • In case of odd n, simply ignore the middle room. Because it will always have >= b students.

  • Implementation wise, I am moving two pointers l and r so compute the lsum and rsum for each i. Code 36115092

Where am I going wrong ?

Update : Nothing is wrong with this solution. Fixed implementation issue. Correct code 36121095

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

    I guess this If lsum - lused < b we will lock lsum - lused of them in current room. In this case we increase counter, c1 += 1 indicating this will be reported by the instructor. is wrong.

    By comparing your code, you can find it is better to let lsum - lused go to right room instead of lock them when lsum - lused < b

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

How do we solve Div2C fast? I tried 3 times and got TLE on test 8 for all 3 tries ... Can anyone give me hints or ideas?

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

    You can keep the basic idea from your solution.

    The reason why you get TLE is because you spend so much time searching for the next index i (O(n) in the worst case). You can find the index in O(1) time, if you keep track of the arr[i] which end in 1, and the arr[i] which end in 0. You can use two stacks/queues ending_in_zero and ending_in_one which store the indices.

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

Perfect time for Chinese users!

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

I had solved Div 2 C in paper, but I couldn't implement that. My solution was something like: If first element is 1, then obviously output  - 1, so assume the first element is 0. Now create a string S0 and set S0 = 0. Now read of the digits after the first digit one by one: (a) If it's 0, then if there's a string Sj ending with 1, add 0 to that string, or if they don't exist, create a new string Si = 0 and keep track of it. (b) If it's 1, then if you can find a string Sk ending with 0, then add it to the end of that, otherwise if you can't find output  - 1. Add the end, output the elements which form your strings one by one in each line.

Now the reason I couldn't implement is that I couldn't figure out how you're supposed to keep track of the strings and the array indexes which create the string without creating an 200000 by 200000 array ? How you do that ?

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

    Why would you need a 200000 by 200000 array to track the strings? You could maintain two lists of strings, one for the strings ending with zero and another list for the strings ending with one. You should be able to pick the a string from one list and move it to the second list in constant time.

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

      OK, but how do you maintain a list of lists without knowing what will be the size of either one after the algorithm runs ?

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

What was the test case #8 in the problem Div 1 A? I have tried running my code on a lot of possible test cases and I am not able to find a test case that can cause a runtime error. I have even put an infinite loop to get a TLE in all possible situations where I might get a runtime error. Any help with it?

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

    Your code get RTE when the input is a string of length n = 199998 such that - first n/3 chars are '0' and last n/3 chars are '0' and everything in between are '1'.

    Tested on custom invocation. Btw, why use goto ?

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

    The error is because of order of line 44 and line 45.

    vals[0].erase(*it);
    pos = *it;
    

    When you erase from the set, the iterator it may have changed. Infact, the earlier it may already have been dumped (free) and is hanging. And you are de-referencing that to assign value in pos.

    This can be fixed easily if you reverse the order of those two lines. I hope, its helpful :)

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

      OMG, wasted entire contest in finding this error. It was not triggered on my system upon generating so many tests. Thanks a lot for the help :)

      I used goto because while writing code, I thought that there will be many places from where I will go to DONE, but turned out there were not much. In retrospect, I should have removed that and replaced it with another break statement.

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

http://codeforces.com/contest/950/submission/36125485 Я не могу понят почему у меня даёт WA. Объясните пожалуйста!

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

    Посмотри на строчку в выводе: 10 20 21 26 27 28 29 32 33 34 35.

    Если я правильно посчитал номера во вводе, то 20 символ — "0", 21 символ — "1", 26 — снова "1".

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

      Спасибо! Я почти полчаса искал не заметил этого. Вот сейчас исправил.

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

Where is the Editorial? :(

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

Hi everybody!

Thanks again for participation, we were really busy with the awards ceremony of the onsite round here in Moscow and I've literally only got back home from the Olympiad.

The editorial will appear tomorrow, we were not fast enough to prepare a well-written text editorial for the round yet.

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

Maybe that will look more like bragging but I consider this funny enough to point this out.
I already:
1. Took 2nd place on Codeforces
2. Took 2nd place on TopCoder
3. Took 2nd place on AtCoder
4. Took 2nd place on CSAcademy
5. Took 2nd place on Hackerrank
6. Took 2nd place on ACM ICPC WF
but I never won any of these xD.

Moreover in high school biggest deals for me were Polish and international olympiads in math and informatics and I:
1. Took 2nd place in PMO
2. Took 2nd place in POI
3. Got silver medal on IMO
4. Got silver medal on IOI
Already at that time I received nickname "silver human" and it seems I proudly continue to follow this path.

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

Still waiting for the Editorial...
BTW, div.2 E has so many test cases...
But finally I got Accepet, yeah!

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

div2-D.

I find out the sequences how A number changes its position .

but I can't understand How I know which number is in the given index/cell . Any hints?????????

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

Div 2- Problem C

The question has greedy tag, how can one identify if a question is based on greedy algorithm or not?

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

Just a final update: the great editorial by gritukan and ch_egor is there, be sure to check it out.

See you in next Codeforces Round in cooperation with Moscow Olympiads!

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

Когда выйдет разбор задач ?

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

Please someone help why am i getting TLE in ques C

http://codeforces.com/contest/950/submission/36191394

thank you

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

How many tests does 950A have?

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

Hi, I have a question. Why the verdict of my submission says "TIME_LIMIT_EXCEEDED" even when I am able to see the "participant's output". Here is my submission. http://codeforces.com/contest/949/submission/39421261

Thanks.