scott_wu's blog

By scott_wu, 11 years ago, In English

Hello everyone! Codeforces Round 174 will be held for both divisions on Sunday, March 17th at 7:30 PM MSK. The problem setters are abacadaea and me (scott_wu). We would like to thank Gerald for his help in preparing the contest and Delinur for translating the problems. We also thank MikeMirzayanov for creating such an awesome site. We are very excited as this is our first Codeforces round.

For this contest you’ll be helping Farmer John, Bessie, and the cows. We hope you enjoy the problems! :)

The score distribution will be slightly nonstandard.

Div2 — 500 — 1000 — 2000 — 2000 — 2500

Div1 — 1000 — 1000 — 1500 — 2000 — 2500

Good luck and happy coding! As always, to make the round more exciting, we recommend that you take a look at all the problems!

UPD: Our editorial can be found here. Thanks for participating!

Congratulations to the winners:

Div1

  1. al13n
  2. rng_58
  3. HELEN_KK
  4. wjmsbmr
  5. bmerry

Div2

  1. hockey_for_NOI
  2. Efremov_licesos
  3. Muali
  4. koratel
  5. lxfind
  • Vote: I like it
  • +323
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
  Vote: I like it +76 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it +85 Vote: I do not like it

Wow, finally some Americans.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    The moment I saw FJ's name I said it should be Americans :D

»
11 years ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    ...There is only one 2000 in DIV 1 !...
    ...there are two 1000 in DIV 1 !...
    ...Good Luck!... )

»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    There is no cow level.

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Like!! «Che Haali mide inja benevisi bad ina nafahman o kolli beshun bekhandi :D»

»
11 years ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    I just wanted to see how my avatar looks in the comments.

»
11 years ago, # |
  Vote: I like it +39 Vote: I do not like it

we always see beautiful problems in USACO contests.

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

»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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://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,

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can mail to the administrator about this issue

»
11 years ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

pretty good! Good luck to everybody.

»
11 years ago, # |
  Vote: I like it +42 Vote: I do not like it

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

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

»
11 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

My time to be pink coder :)

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    But I think it looks like purple more than pink ~>_<~

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      I think it will be better to mix both of them (purple and pink) to get Candidate Master's color).

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      i think it mix of both !!

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      How about :
      My time to be rgb(170, 0, 170) coder :)

»
11 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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 ??).

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    It would be good to have a possibility of reverting the vote. Some minuses may be done by mistake. It's an irreversible mistake now.

»
11 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    fermer?maybe farmer =D? Good luck, we will help you Mr. John!!!

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      oh sorry, its Technical error :D

      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it -7 Vote: I do not like it

        Lol, you get Technical error and '+' , i found you error and get '-', nice community -_-

»
11 years ago, # |
  Vote: I like it +53 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it -13 Vote: I do not like it

It will be produced in usaco's difficulty problems?

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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. :)

»
11 years ago, # |
  Vote: I like it -11 Vote: I do not like it

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

Спасибо!

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Если ты не заметил , задачи А всегда лёгкие и соответственно особого интереса не вызывают.

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      По сравнению с остальными они очень легкие, задачи состояла в том что надо считать сроку и вывести ее, только сменить первый регистр символа.

      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Сейчас задача А не очень лёгкая...Накаркал...

»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it -8 Vote: I do not like it

memeda

»
11 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think they mixed up A and B))

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

»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Someone else having problem to hack ?

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
11 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Why i cant hack?

Can't process your hack, try again

  • »
    »
    11 years ago, # ^ |
    Rev. 3   Vote: I like it +7 Vote: I do not like it

    In my room(num 24) was 0 hack.why? becose there was not some icon to upload generator.when you use input block ==> "Can't process your hack, try again" i saw >10 solution with TLE but I could not hack them :(

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      I hacked 4 solutions(with TLE too :)) without any problems.

      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        You are not in my room!

        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I just tried to say what I had no problems when hacks solutions. I think, you should write letter to administration.

»
11 years ago, # |
  Vote: I like it -9 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was seconds late to submit B :(

»
11 years ago, # |
Rev. 2   Vote: I like it +37 Vote: I do not like it

Not this time wjmsbmr

»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Thank you for very interesting problems.

»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Looks like we beat the USACO results :)

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When p = 2 I see some code return 1 in this case. I really don't understand why, because when p = 2 the only possible value of x is 1 , while (x-1)%2 == 0 , clearly.

»
11 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Now you can see wjmsbmr is not me LOL.

»
11 years ago, # |
  Vote: I like it -45 Vote: I do not like it

Strongly suggest unrated

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +105 Vote: I do not like it

    I can promise you not only unrated round, but more! You will be banned soon because of unfair play.

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 2   Vote: I like it +31 Vote: I do not like it

      first time seeing admins publicly announcing name of cheaters. I think the above statement of admin is result of outbrust of feelings. Shouldn't they give person a chance to explain his stance as Troy1118 is a member of codeforces for 2 year.

      I do not think his situation is like those unrated people who cheat in very first match. (It does mean at all that I am supporting cheaters. If he has cheated , he should be banned no doubt. But admin's reply again raises the question of whether a person should be given fair chance to defend himself and also of whether publicly anounce name of the cheaters or not ??)

      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it -17 Vote: I do not like it

        May be Admin has special powers. I did take the name of a person in the previous contest(link to comment) and got -40 + lots of advices.

        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          i think you got '-' because you reported it.

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      What has he done?

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Sorry for my interest, but can someone tell me why (s)he (Troy1118) is going to be banned ? Which rule did (s)he break ?

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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!

»
11 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
11 years ago, # |
Rev. 4   Vote: I like it +4 Vote: I do not like it

[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 :)

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it -12 Vote: I do not like it

    ignore it

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      here is one cycle with < and one with <=

      • »
        »
        »
        »
        11 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        There's no problem, he made n equals 199999 and outputs 199999 lines then

        UPD: Sorry, I thought you want to say, that he's checker is uncorrect, but you answered to guy thought like this :) My mistake.

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    As far as I know , Last line is printing extra "\n". So if you could change that, it will be fine.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what's validator comment?

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's FAIL Input can't contain chars with codes less than 32, but line 5 (1-based) contains [validator wfval.exe returns exit code 3].

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i had the same problem. you must swap 2 and 3 integers there: for(int i=1; i<=100000; i++) printf("1 !99999 !1\n");

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    .

»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

if(Div.2)

swap(A,B)
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

... 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 :/

»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Thanks for fast editorial ! Great !

»
11 years ago, # |
Rev. 5   Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    there's no way the browser could detect if new message was announced, except it was already refresh it every time, or doing it in background

»
11 years ago, # |
  Vote: I like it +29 Vote: I do not like it
»
11 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Thanks a lot for the editorial just after the contest!

»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    In case 3, you also have to set change[sz(v) — 1] to 0, otherwise when you add new elements after removing some old ones, the old value of change entry will fuck up your result. This is how my initial solution got hacked.

    And int overflow.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    int sum = 0; :(

  • »
    »
    11 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    Переполнение типа int

»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

poor system test!

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it +39 Vote: I do not like it

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?

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    You should think like this and submit: "I'll just submit to make sure it fail pretest so that I can focus on other problems"

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It doesn't make a sense. What was the point of waiting for somebody who submit the task first? It would be better if you didn't submit it at all.

»
11 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The next contest is div2 only, anyway. You can gain even more points if you participate in it, get a rating increase and then in participate in the next div1 contest, than if you actually got the 4 more points now and skipped the next div2 contest :D

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yes, you are right! But I can't participate in the next round. It's our New Year ceremony in Iran! :)

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this is the reason:

    int N = 20000+1;

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So 20000*(small constant) is not close to 262 MB. And N is a constant, why does it fail only on the 9'th test and not earlier?

      • »
        »
        »
        »
        11 years ago, # ^ |
        Rev. 5   Vote: I like it 0 Vote: I do not like it

        The problem is that your array is not enough. So when your code runs a large test, there may be some unexpected issues in the recursion and it somehow won't terminate. And when the recursion keeps going on, your memory will exceed the limit.

        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hm, thanks, but anyway I don't understand. Why doesn't it fail if I'm indexing out of my array; is it adding more memory by itself? haven't heard about similar never before; Also I don't see any bugs in my code, do you?

          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
            Rev. 5   Vote: I like it 0 Vote: I do not like it

            The recursion consumes memory itself since you have to store all the variables of the recursion.

            This simple program also runs out of memory (you can try it in "Custom test")

            `

            void go(int x, int y, int z, int t) { if (x == 10000000) return; go(x + 1, y + 1, z + 1, t + 1); }

            int main() { go(1, 2, 3, 4); }`

            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
              Rev. 2   Vote: I like it +7 Vote: I do not like it

              Thanks, I just understood you incorrectly the first time, of course I know recusion consumes memory.

»
11 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    sum -= bit.total(size - 1);
    bit.update(size, -bit.total(size));
    --size;
    

    I would try bit.update(size - 1, -bit.total(size - 1));

    EDIT: sorry, it won't work

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I figured it out, should be like this:

      ll d = bit.total(size - 1);
      sum -= d;
      bit.update(size - 1, -d);
      bit.update(size, d);
      --size;
      
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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...

»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

http://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"

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It seems that N, the size of your array, is a little too small. The sequence starts with one element, so it can have up to 200001 elements total.

    I've changed N to 200001 in your code and gotten AC here: http://www.codeforces.com/contest/283/submission/3347718

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      thank you!

      your problemset is really nice, though i have made a lot of mistake like this.

      hope for your next excellent round!

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      could you post somewhere test no. 10 for C Div2 problem? My solution still fails on it. :(

»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Print as many numbers as possible! I use printf("%.15lf") ..

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

»
11 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't see any mistake in testdata 10 which your submit 3350410 get WA, can you tell more?

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      maybe the mistake like this: 1 1 3 1

      so the ac code will give 3 but I think it should be 1

      I should go back to learn English....

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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]

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you should updating add[last] = 0 after removing last element of the sequence

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think that you forget to set add[last] = 0 in case choose == 3.

»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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. :|