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

Автор scott_wu, 13 лет назад, перевод, По-русски

Всем привет! Соревнование Codeforces Round 174 будет проводиться в обоих дивизионах в воскресенье, 17-го Марта в 19:30 MSK. Задачи готовили abacadaea и я (scott_wu). Традиционно мы благодарим Gerald за помощь в подготовке соревнования и Delinur за перевод задач. Большое спасибо MikeMirzayanov за создание такого отличного сайта. Мы очень взволнованы, ведь это наш первый Codeforces раунд.

В этом раунде Вы будете помогать Фермеру Джону, Бесси, и коровкам. Мы надеемся, Вам понравятся задачи! :)

Распределение баллов по задачам будет немного нестандартное:

Div2 — 500 — 1000 — 2000 — 2000 — 2500

Div1 — 1000 — 1000 — 1500 — 2000 — 2500

Удачи Вам и приятного кодинга! Как обычно, чтобы сделать раунд более захватывающим, мы советуем прочитать Вам условия всех задач!

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

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

It's like USACO only with faster results! :)

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

Wow, finally some Americans.

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

... There are two 2000 in DIV 1 ! ...
... Maybe I should think twice before decide which one should be attacked first ... )

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

В анонсе есть две опечатки. 1.Правильно не "Традиционно вы благодарим Gerald за помощь в подготовке соревнования и Delinur за перевод задач. ", а "Традиционно мы благодарим Gerald за помощь в подготовке соревнования и Delinur за перевод задач.". 2.Правильно не "Вы надеемся, Вам понравятся задачи! :)", а "Мы надеемся, Вам понравятся задачи! :)".

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

Will Фермер Джон and his N коров (1 <= N <= 100,000) make an appearance?

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

Фермер Джон со своими коровами постепенно захватывают просторы интернета, а особенно USACO и Codeforces)

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

.

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

we always see beautiful problems in USACO contests.

I hope we have beautiful and interesting problems in the first usaco-like code forces round !

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

Good to see Bessie and the cows invading the world of algorithms !

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

Hi guys, looking forward to round 174.

I wanted to bring up a problem that I found while solving other past problems. The Python language is not very well supported, so that even if a program has the right time and space complexity, it wont pass the tests because the tests have been written with C/C++/Java in mind.

for example I solved http://mirror.codeforces.com/problemset/problem/222/B but it would sometime pass and most of the times not pass depending on how many answers I would spit out at a time.

Is it possible to take some actions toward better support of Python? maybe supporting Python3x would be enough cause it has faster input/output libraries.

Please let me know,

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

pretty good! Good luck to everybody.

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

many coders from various countries have been holding contests;great!

and I wonder Bessie the cow and John the farmer will cause problems again :)

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

Counting both Div1 & Div2 , there are One 500 , Three 1000s , One 1500 , Three 2000s but Two 2500s break the sequence :)

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

Wish I can be red after this contest! I will do my best to help Farmer John to handle his cows!

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

My time to be pink coder :)

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

I hate "fading the more negative voted comments" feature of codeforces. It takes me more time to see the comments. I do not why I always open the comments with negative votes(they are interesting and I want to see what people hate and why ??).

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

Wow, its good.. everyone likes usaco problems and fermer John... So i wish everybody luck :D

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

will I have to insert "USER,LANG,PROB" headers in my code? :))

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

It will be produced in usaco's difficulty problems?

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

The score distribution look's pretty good to me.Wish we have a nice contest! Thank's goes to USA setter scott_wu and abacadaea. We like to help Jhon, Bessie, and cows with so much excitement. :)

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

В двух предыдущих раундах div 2, задачи "A" были очень легкие и интереса особого небыло их решать. Надеемся тут будут интересные задачи...

Спасибо!

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

Farmer John? I think I'll back to blue...

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

memeda

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

Nice and exciting contest, cute problems! I'm so sad because i couldn't register for it :((

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

I think they mixed up A and B))

Я думаю они перепутали местами А и В))

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

Someone else having problem to hack ?

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

    yep....There has been a while that I cannot lock my problem, and there has been a while that I cannot see other's locked solutions after I locked my problem, and there is the last moment after I submitted a hack waiting for the webpage to response for 10s it says contest end.

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

Why i cant hack?

Can't process your hack, try again

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

Finally see Americans set the problems, good job. Problems in the last contest are way too sophiscated, and this time the problems are beautiful.

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

I was thinking why codeforces is still in Beta version, Now I know the reason "504 Gateway Time-out".

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

I was seconds late to submit B :(

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

Not this time wjmsbmr

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

Thank you for very interesting problems.

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

Looks like we beat the USACO results :)

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

Haven't xperienced too hard DIV-2 A before :\

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

Now you can see wjmsbmr is not me LOL.

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

После третьего или четвертого взлома от Egor у меня начали закрадываться сомнения... Примерно после шестого я понял, что мое решение неверное, подумал — "да ладно... все равно я в ж***, так что пусть ломает, перешлю потом, мне не жаль... Если бы не он — я бы вообще не заметил баг..."

Возникло странное ощущение, что я сделал хороший поступок)

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

На чем все А ломали?

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

Strongly suggest unrated

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

Я надеюсь, что не зря использовал в A(div.1)/C(div.2) дерево отрезков с ленивым проталкиванием. Или есть более простые решения?

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

    Есть:)

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

      =(

      Ну расскажите хоть.

      UPD Спасибо за ответы.

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

        при первых двух операциях сумму и кол-во поддерживать поддерживать легко.

        Давайте теперь поймем сколько вычитается из сумму при третьей операции. ДЛя этого храним s[i] сумму добавлений на префиксе длины i

        Тогда при удалении

        sum -= s[cnt];
        s[cnt - 1] += s[cnt]
        s[cnt] = 0;
        --cnt;
        
        • »
          »
          »
          »
          »
          13 лет назад, скрыть # ^ |
           
          Проголосовать: нравится +1 Проголосовать: не нравится

          А можно пояснить шаг "s[cnt — 1] += s[cnt]" ? Почему есть влияние на какой-либо элемент кроме последнего?

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

            s[i] = x значит, что мы добавлили ко всем числам на отрезке 1..i по x. При удалении последнего элмента, нужно указать что мы добавили на отрезке 1..(i-1), иначе информация потеряется.

            PS: коряво как-то объяснить получается)

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

        После каждого запроса нужно знать только сумму. При первых двух запросах сумму просто обновляем (либо плюс x·a, либо плюс k). А при первом запросе добавляем к add[a] значение x. Когда будем элемент удалять, то всю add[last] прибавим к add[last - 1], а от суммы отнимем val[last] + add[last], сам же add[last] обновим на 0.

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

    Я сделал что-то типа пирамидки с помощью доп массива с общей сложностью O(n)

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

The Contest was so cool, i like the problems. but i couldn't solve them !!! If i had more time, i would submit problem C too, i solved it but for my internet connection error at the last minute! i couldn't submit it!

by the way, Thank you, scott_wu and abacadaea, for this beautiful problems with cows and farmer John!

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

First, I got the standard message, that the contest is over. But I didn't send some solution in time, so I entered the contest once again and sent the solution just to check if it was correct (as in 'practice').

And now I see it was sent on 02:04:28 and it was (pre)accepted for judging.

Nice try!

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

Amazing round ! The problems is interesting :)... But I made a silly mistake again in Problem C...sad >_<

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

Большое спасибо авторам за задачу A DIV 2 — познавательно!

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

Probably, first round, when I send solution for A just before contest ends. Thank you for great tasks!

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

[284C]

#include<stdio.h>
int main()
{
	printf("199999\n");
	for(int i=1; i<100000; i++) printf("2 1\n");
	for(int i=1; i<=100000; i++) printf("1 99999 1\n");
	return 0;
}

Why this generator gives Invalid Input? Please give me a hint. Thanks :)

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

if(Div.2)

swap(A,B)
»
13 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

... My solution for B(the easiest one) failed because of char mass[100000] instead of char mass[200000] :/ And I was late a little to submit C :/

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

у двух человек полностью одинаковые решения по 3-м задачам

lawliet_djez : A — 3338474, B — 3334615, C — 3341327.

metalopocalipsis : A — 3338366, B — 3334502, C — 3338081.

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

Thanks for fast editorial ! Great !

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

During the contest I didn't read the message about the contest duration had been increased by 5 minutes and I wasn't refreshing my browser after the message had been announced, then on my browser the contest was ended 5 minutes earlier, 2-3 minutes later I had finished my solution for problem A and I didn't submitted my solution because I thought the contest was over :(

on the next round I hope the system refreshing all contestant's browser automatically after the message has been announced

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

Как все С (div 2) ломали??

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

Thanks a lot for the editorial just after the contest!

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

http://mirror.codeforces.com/contest/283/submission/3339789 в чем ошибка, скажите, пожалуйстаа

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

poor system test!

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

Can someone please help.I was unable to pass the pretests for div 2 problem C . Here is my code. I tried it with segment tree. I'm not experienced with segment tree. I've only used them once or twice.This code got WA in pretest 9.

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

Amazing round, cool tasks, like it. Thanks guys :)

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

Sad...I learnt a lesson from this round that I should be more confident..I worked out Div1.D at about 00:15 after the beginning of the contest,but I could't make decision to submit my code because I just think it's impossible for me to solve Div1.D in only 15min..So I stupidly did nothing but waited for someone who would solve it,and it's rng_58 at 00:34,then I followed him and got AC...What a stupid I am huh?

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

I haven't participated for a while. Can someone please tell me what is "bestRatingChanges"? Is it a new feature?

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

Can someone explain the solution for Div1 D Can't understand from the editorial

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

Damn... :( Can somebody share 4 more points with me...? :D

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

http://mirror.codeforces.com/contest/283/submission/3345114 interesting, why does this solution fail on memory? I think I have constant (but big) memory.

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

Not only the problems were perfect... you have also published tutorials in few minutes... fantastic :)

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

Does someone know why this solution failed precision check? Does that mean that the sum is wrong and is there a way to download the test?

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

Can anyone tell why my solution for Problem C Division 2 is gave WA. http://www.codeforces.com/contest/284/submission/3336215

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

could someone post the test no 10 or help to figure out why my solution on C Div2 fails on test no 10 ?

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

Yeah~ think my English is very poor ,not you in your problems' discribe.In pro B(div.2),I readed it again again again and again...I dont know what you want to say,I translated it in a variety of dirctions,but when I see the sample input&output,I thought im wrong...

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

The problems are interesting, it's good to see cows and Bessie again!

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

it there anything wrong with the checker of div.1 problem A?

http://mirror.codeforces.com/contest/283/submission/3331170

i just cannot figure out what's wrong with my submissions, while the checker said "Checker comment wrong output format Extra information in the output file"

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

Why my actual rank for Round174_div2 is different from the rank that appears on my profile? One shows #5: http://mirror.codeforces.com/contest/284/standings One shows #7: http://mirror.codeforces.com/contests/with/lxfind There might not be a big difference, but which one leads to the new rating?

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

My submission for Div.2 C, is giving WA on test 10's 103363rd number due to precision error :(

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

What a great contest ! I would like to say thank you to figure out my mistake! Expecting you can get great contest later~

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

I think I have a similar but more comfortable solution for Div.1 D.It depends on this property:

If a[i] has been determined,and a[i-1] should be replaced,then we can optimize a[i-1] that:

Proof:

If a[i] is even,k = a[i] / 2,then a[i - 1] = (2p + 1)k, a[i - 2] = a[i - 1] * (a[i - 1] + 2q - 1) / 2.

Then let r = 2p2k + pk + 2pq - p + pk + q,which is always a integer.

a[i-2]=k(k+2r-1)/2.So a[i-1]=a[i]/2 is better than any other a[i-1].

If a[i] is odd,k = a[i],then a[i - 1] = pk, a[i - 2] = a[i - 1] * (a[i - 1] + 2q - 1) / 2.

Then let ,which is always a integer.

a[i-2]=k(k+2r-1)/2.So a[i-1]=a[i] is better than any other a[i-1].

Using this property,we can calculate dp[i] with simply enumerating j from i-1 to 0.

There are many formulas.Although it's very natural to guess it's correct.The code 3335280 is easy to understand.

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

А почему не делается разбор на русском языке?

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

I think the data of div1 A have some problem! If it comes ti = 1 many people add ai * xi directly but actually there have a date's ai > the length of the current sequence. look my submit 3350410 3350482

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

div1 problem D how to prove that : if( j-i-1 < m2[j] ) then there aren't any cool sequence begins with a[i],ends a[j]

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

I saw the editorial for A in DIV1 but still got wrong on test 10, what's wrong ?3352082

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

it liked usacos problems..... But at the and of the contest was balk and finaly i hadnt time to hack :(

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

My solution Link , I don't know why i WA in test 5, I pass this test in the same code but submis in systems WA. :|