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

Автор fcspartakm, история, 8 лет назад, По-русски

Привет, Codeforces! Это снова я=)

19 декабря 2016 года в 05:05 MSK состоится раунд Codeforces #387 для участников из второго дивизиона. Участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.

Этот раунд проводится по задачам второго дня муниципального этапа Всероссийской олимпиады школьников по информатике 2016/2017 года г. Саратова. Задачи были подготовлены силами Центра олимпиадной подготовки программистов Саратовского ГУ.

Хотелось бы сказать большое спасибо Николаю Калинину (KAN) за помощь в подготовке задач, Татьяне Семеновой (Tatiana_S) за перевод условий на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, а также Владимиру Петрову (vovuh), Алексею Рипинену (Perforator), Михаилу Левшунову (Levshunovma), Михаилу Пикляеву (awoo), Алексею Слуцкому (pyloolex), Ивану Андросову (BledDest), Олегу Смирнову (Oleg_Smirnov) И Роману Кирееву (RoKi) за прорешивание задач и написание разборов.

Участникам будет предложено шесть задач и два часа на их решение. Разбалловка будет объявлена позднее.

UPD Разбалловка 500-1000-1500-2000-2000-2500

UPD2 Разбор

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

  1. 248926

  2. vigoss18

  3. haleyk100198

  4. ouch__casquinha

  5. peijinz

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

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

Now this is what I call unusual time :D

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

Сон для слабаков!

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

5:30AM here...

It's cool :D...I'll try to join the contest...

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

    You are lucky, It's 4:00 AM here :D

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

      But I'm gonna stay awake till the contest starts :)

      PN. Of course it's just an excuse, I think I'll watch some movies and when the contest starts, I'll sleep :)

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

Why at this time?

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

Deleted

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

Просто интересно, для кого в такое время это проводят? Для охранников?

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

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

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

    Зато теперь все, кто может спросить "Is it rated?" спят.

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

Может быть авторы готовили контест для TopCoder и перепутали платформы?

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

iam gonna wait whole night for this contest !!! lets hope this contest bring positive rating change to all of us... good luck everyone :)

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

Its 05:11 AM here in India.
I randomly opened codeforces to check editorials and I am surprised by this highly unusual timing.
hope to get + ratings. :D

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

Contest==> 7:35 am to 9:35 am (IST)

Exam==> 10:00 am to 12:00 pm (IST)

But gotta do it, coz cant miss a codeforces round!

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

I think that this is the time, you Europeans and Asians, in which you'll know what people in America suffer. Regular codeforces rounds are at 10:35 here in Mexico, and I always have to skip classes to take them. But not today. Today is at the perfect timing of 20:05

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

Утро начинается не с кофе :)

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

Never awake early for college first time only for CF.

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

8:30 PM, on a Sunday night? This has to be the most convenient time for a contest ever for NA people. Can we do this at least once every two months?

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

I can't believe that I have just left my pillow and blanket to participate in this Round I haven't done that before, even to watch GOT

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

Я встал в 4 утра. Но у меня отключили электричество... Пошел плакать((

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

This round timing reminds me of TopCoder SRMs timing.

Most TopCoder SRMs were hold at time like this and I had to wake up after the mid-night to take it.

But I think it deserves.

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

i hope the round will deserve stay awaking for 4 am

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

Hopefully I can gain ~300 ratings from these two rounds so that I could rush a purple before the year ends.

Just 110 more to go =]

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

It's 18:35 here. But I think it's a little early?

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

Can anyone explain how to do D? Is it dp (I was using a 3D dp table but couldn't implement it properly)?

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

    No need of DP, you can do it with a min heap. Store the difference(number of summer days) between two consecutive winter intervals and process them from lowest to highest.

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

      Ah that's a lot simpler than I thought it would be. And it makes sense when I think about it.

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

    No, greedy works. Split the array into segments of negative values. Sort the distances between consecutive all-negative segments in increasing order and just keep using winter tires to join them.

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

    the given test case in D , third one answer shouldn't be 2. If he wants minimum tire changes then he must club summer days with winter , if possible . According to that ans can be reduced to 2.

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

    I believe greedy works: on all the negative days you have to use winter tires. Pick the smallest interval (non-empty) that is bounded by two consecutive winter days, and fill use winter tires over that interval. Of course you have to account for the corner cases and whatnot.

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

    Mine was a greedy one. I just kept cancelling any swapping between the two days with negative temperatures and the distance between them is the smallest until I run out of Winter tears. But I am still not sure that this solution is correct. :D

    UPDATE : mine is incorrect :D

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

    Greedy works just as other comments have stated, remember to always consider the final segment of non-negative temperature AT THE VERY LAST. Now I thought it a bit more I just missed a hacking opportunity on someone who sorted the final segment with the others.

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

Nice Contest.

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

Almost no hacking in this contest. There were literally no hacks in my room :o

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

Almost no hacking in this contest. There were literally no hacks in my room :o

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

My idea around D was something like this:

Let's assign Winter Tyres W to all negative temperatures and Summer Tyres S to others. Let initial answer be the worst case of exchanges required.

Now, if we convert a segment which is of the form: WSSS...SW to WWWW...WW then we reduce 2 exchanges. So, we try to cover the smallest segment first and greedily try to reduce exchanges this way.

My implementation gave segfault on Pretest 3. Dunno if this would work — can someone point out where this could go wrong?

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

    this was my idea too and got ac after contest. just remember to add first exchange and last exchange(which if happens, both will be 1).

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

    If you have the last few days covered by S, consider replacing it with W to save one switch. Since you only save one, which is less than the normal two, check this case at the very end.

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

TFW you know that problem F is a problem about binary search and combinations but you suck hard at combinations... WITH 90 MINS LEFT.

void recursion(struct me, int remainingTime){

if(remaingingTime)

       remainingTime -= 0.1;

}

I thought I was stuck forever.

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

    Can you give an outline of your approach?

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

      Use binary search to find the answer, and count the combinations of non-interesting numbers smaller than var(mid).

      I didn't manage to find the combination formula though.

      Use a vector of decimal based numbers will help during processing.

      Edit: Whoops I was wrong. Seeing the tutorial reminds me that using dp to count the combinations is a common technique which I learnt in other round's tutorial...

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

How to approach E? I made a recursive function but could find no way to optimize it.

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

Greedy... greedy everywhere

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

Bye expert! Just I was some hours blue

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

I hope there will not be another contests at this time again.

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

    I think it is a cool time during semester break. It's morning in eastern Asia so I could join the contest with a fresh brain instead of a tired one on the usual time.

    The amount of people available on this time slot is really low though...

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

      I agree with you about participating with a fresh brain but it's not a semester break for everyone. I'm working on semester projects now and it's 10 days away from the beginning of the semester exams.

      I don't know if it's a good time for many members or not. but I didn't see anybody upset from the usual time.

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

    What time is it now in your country?

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

C failed systest

  • y tho bro?

opens the code after 10 secs

  • aaah, f***, I forgot to ignore the one with insufficient number of servers...
»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Such quick system testing !!!

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

What is problem D test 31? Any ideas?

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

    I think it's some thing like this :

     8 7
    -1 -1 -1 0 0 -1 -1 0

    Considering segment [4, 5] gives optimal answer even though it's length is greater than segment [8, 8].
»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Wohooo! First place in my room for the first time! ...and I got WA on problem A because of uninitialised variables, how embarrassing :P

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

    A reversed case for me. I saw someone's code could possibility cause RE since it could check out-of-bounds values, but I didn't have the courage to hack that guy.

    He coded something like this:

    int d[4], z = 0;

    while(d[z] == 0)

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

why my source is runtime error in Problem E? http://codeforces.net/contest/747/submission/23126016

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

An unusual timing for the contest, the number of problems, and system checking was so fast! I like this contest

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

Last ACC in the Round :D

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

Is here anybody who solved D with binary search? :D

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

you know it was a greedy contest when nearly 400 solutions fail system test for D.
wasted whole time on D in search for a O(n) dp solution. :(

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

    It's so hard to set a question which denies O(nlogn) while accepting O(n) though.

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

      haleyk100198 you did very great today.
      How did you solved D and E so fast?

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

        For problem D I got a little bit lucky to notice the greedy approach, so I only have to spend some time on refining the code to handle the corner cases.

        For problem E, managing a file tree is a quite common practice problem. (I am surprised that it showed up as a regular round problem E)Whenever I see such a problem I just go straight for stack, and there's no other tricks needed so I got it almost instantly.

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

Good morning! can anyone explain D for me? is it DP? i wanted to do this with 3x dp2D but i can't!

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

    Check the comments above, there is a populated comment above which should guide you how to solve it with greedy.

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

So excited about being a Candidate Master!!!

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

although i solved 2 questions ,_ better than every time_, my rating points decreased ! could anyone explain to me the rating process and why i decreased please ?

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

Can anyone help me why 23126693 got WA?

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

    You made a mistake to consider the final segment of non-negative days with other segments.

    For example:

    10 8

    0 -1 0 0 -1 0 0 0 -1 0

    Your code considers to use the winter tire on segments : [2, 5] and [9, 10] (1-based), as it recognises the last non-negative segment [10] has the best greedy value, but the correct answer should be [2, 9] as using winter tire on [6, 8] further reduces the result.

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

    try this case:

     8 7
    -1 -1 -1 0 0 -1 -1 0

    Answer should be 2 instead of 3.
»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

In problem 747E - Comments, my code receive TLE in maintest 9. However, when I resubmit the same code, it get TLE in test 29.

Here is my code in the contest: 23123300.

And here is my resubmitted code after the contest: 23128262.

You can use compare button to check whether they are same.

I so worry that may people could fail system test because it (not me because I still fail with test 29)

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

    I don't think this should be a concern as your code was very close to TLE on test case 9 in both submissions. It is known that CF running time has a delta of around 30ms, which should not cause problems to most submissions. (As always, you run a risk of submitting non-optimal solutions)

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

http://codeforces.net/contest/747/submission/23124311

Can someone help me find out the mistake i made in problem C .

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

    You should prioritise using the unoccupied machines with smaller ids, instead of the ones who were released earlier.

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

    I think your mistake is that you do this (servs[i].f=(t+(d-1));). If only x (x<k) servers are available, you print -1 but don't reset the ending time of those x servers.

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

I woke up early for the round 386, waited for this round and will wake up early tomorrow again for next round, hopefully there are more often 'daily' rounds

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

why for this input:

10 5

1 1 1

2 1 3

3 2 3

4 1 1

5 2 1

answer is : 1 1 5 4 5, but not 1 1 5 4 7 ?

at second 1, there're 10 unoccupied servers and we need to occupy 1 sever for 1 second , sum -> 1;

at second 2, there're 10 unoccupied servers and we need to occupy 1 server for 3 seconds(sec. 2,3,4), sum -> 1;

at second 3, there're 9 unoccupied servers and we need to occupy 2 server for 3 seconds(sec. 3,4,5), sum -> 2 + 3 -> 5;

at second 4, there're 7 unoccupied servers and we need to occupy 1 server for 1 second, sum -> 4;

at second 5, there're 8 unoccupied servers and we need to occupy 2 servers for 1 second, sum 3 + 4 ??

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

For problem E, I traversed the string once and stored the strings at the index of its level in a vector and later displayed the contents of vector level wise. The total memory taken by the vector will then be equal to the memory taken by the string.

But I am receiving a runtime error on system test 26.

http://codeforces.net/contest/747/submission/23129959

Is there something fundamental I'm missing out? Thanks for any help in advance.

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

Hello, I have a small doubt regarding problem E. My submission 23125639. The code for converting string to integer is for(int i=0; i<lol.size(); i++) cnt[(j-1)/2]+=(lol[i]-'0')*(int)pow(10, lol.size()-i-1); This is giving me wrong answer on test 18. But when I replace this with the inbuilt function, atoi(), the code is getting accepted. I'm unable to understand why. Help would be appreciated

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

    The power function returns a double type value which on conversion to an integer might cause some precision issues. Use a custom power function instead.

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

      For powers of 10, I don't think there is any problem with precision. If there is an error, it'll occur in the decimal places and it'll be ignored. Is there any case where a this conversion won't work? Thank you for your reply

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

    pow(int, int) actually calls pow(float,float) (or pow(double,double)). There are two problems:

    1)float can represent correctly (with no error) only integers with less than 6 digits.

    2)int(0.99) is 0 and pow() gives us only estimated value. It might give you 9999.99999 when you ask for pow(10,4). And it will be rounded as 9999.

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

      I forgot that pow can return a number slightly lesser than the number. Thank you for the clarification.

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

    Besides the precision problems, I think you should also learn the stoi (and stoll, stod etc.) functions, that helps a lot with converting string to numerical values. That saves a lot of time for coding a function that does the same thing.

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

thx a lot for these consecutive contests (#387,#386,#385,#384)...it helps our ACM team for ICPC-Tehran Region

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

Doesn't the problem B statement says coordinates to be lie between -1000 and 1000. But the output of the judge is considering the coordinates outside this range.

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

    I assume that you are talking about 749B instead of 748B.

    The range of x, y coordinates is only applied on the input, you can output any legit integers in the output.

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

Hey, can anyone tell how to solve D using DP? It has a DP tag, and I am practicing DP questions, so I would be more than grateful to know about that! :D