dzy493941464's blog

Codeforces Round #FF(255)
By dzy493941464, 10 years ago, In English

Hello everyone! Codeforces Round #FF(255) is coming soon! We invite you to participate in this round, the round will be held in both divisions.

In this round, the boy DZY appears again! As we all know, he loves many things. This time he also brings us many interesting problems, which are easier than the problems in last round, but he still needs you help. In return, he will present rating to you.

Many thanks to Gerald for giving us much advice and helping us to prepare the round. Also many thanks to MikeMirzayanov, who created such a wonderful platform.

The problem setters are jcvb, jiry_2 and me. This is our first Codeforces round :)

Come and join us in helping DZY again, and you will take the high rating home!

Good luck and have fun! :)

UPD

In Div. 1, scores for each problem will be 500-1500-1500-2000-2500.

In Div. 2, scores for each problem will be 500-1000-1500-2500-2500.

UPD

The contest is over. Thanks for participating.

Congrats the winners.

Division 1:

  1. vepifanov
  2. subscriber
  3. RAVEman
  4. ztxz16
  5. anta

Division 2:

  1. llllllllllll
  2. geniucos
  3. Misha100896
  4. Temirulan
  5. wwt15

You can find editorial here.

  • Vote: I like it
  • +198
  • Vote: I do not like it

Comments Comments (188)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +33 Vote: I do not like it

What round 255? You mean Codeforces Round #FF (Div. 1), Codeforces Round #FF (Div. 2), no? :D

→ Reply
»
10 years ago, # |
  Vote: I like it +49 Vote: I do not like it

easier than the problems in last round — sounds great! BTW, in last round every problem was solved by >=10 contestants, hard to believe that this time problems will be even easier. But if they do — it will be nice:)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +55 Vote: I do not like it

    Surely it will be :) Wish you high rating ~

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +33 Vote: I do not like it

      You were not serious about easier problems, right?)

      Thanks for interesting contest. I personally think that problems were a little bit too hard. First 3 problems are enough to get into top-5, and nobody solved E... You expected such results? Could you please tell us what was your prediction of AC range for every problem before contest?

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

        We've compared each problem in our round with the round #254. And we think our problem is easier.T^T

        → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +15 Vote: I do not like it

Hope this time problems could be more interesting than the last ones :).

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

if i remember correctly, in the last round most of the problems were about you.
maybe now it is time for some revenge. ;) we will see.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    hope not to be in your room :D like TC srm :|

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

      Having skilled challenger in your room gives some advantage on CF. It increases chances of your wrong solution being cracked during round so you'll have an opportunity to fix it and get some points (instead of flat 0 without that challenge).

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

        well, i am certainly not a "skilled challenger". :P

        i actually had to resubmit my 250 (which explains my low score of ~100) because i found bug in my code after i submitted.
        as it turned out, 4 others in my room also failed on the same case as my first submission.

        P.S. ofcourse, your point about having a good challenger in your room is true. :)

        → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it +21 Vote: I do not like it

      LOL, but i changed nothing for you. your solution would have Failed System Test anyway.
      but ofcourse it changed something for me, i got +50 points for making it Challenge Succeeded. :)

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        but you should not have challenged the problem of a guy who wished you luck before the contest :P

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

          In that case. Best of luck everybody.

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

          LOL, nothing personal, as u know. :)
          in fact, i don't even look at the handle when i open code of participants in my room.

          → Reply
»
10 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Chinese(Hangzhou Xuejun High School) round again!

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

    Looking forward to Raccoon Round :D

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

      you give me A Pretty Good Idea on setting a Contest！ Racoon Round may come soon~

      → Reply
»
10 years ago, # |
  Vote: I like it -44 Vote: I do not like it

FF :) С юбилеем!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Early annovzbbsbsnxnnsnd...

→ Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Seem that, DZY himself is the problem setter this time.

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

    Is it easy??

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

      It's obvious that the problems will be much more difficult than you've expected.

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

    So cute profile picture :3

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

      If you meet MinakoKojima herself some day,you will find she is much more cute than the profile picture.>_<

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        What do you mean? Lol, I don't understand xD Anyway, now I have to meet her :D

        → Reply
»
10 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Last time I didn't really enjoy DZY problems... Wish this time better than last time...

→ Reply
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Why Codeforces Round #FF(255) but not Codeforces Round #255 ?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it +25 Vote: I do not like it

    because 255 is a very big and special number... It's the biggest number char(C++) or byte(Pascal) can hold! (UPD: thanks vas.and.tor, who points out my mistake that unsigned short contains 0..2^16-1... Fixed.)

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

      I guess it's "unsigned char" in C++. Biggest "unsigned short" can be around 32767.

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

    maybe this is why.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I like he also brings us many interesting problems and I like more which are easier than the problems in last round

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

This is the first contest dzy493941464 hold. Hope him success in this contest

→ Reply
»
10 years ago, # |
  Vote: I like it +25 Vote: I do not like it

I think Div 1 E will be 3000...

→ Reply
»
10 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Crap. It's DZY again. I'm scared.

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

You should also mention about the unusual time of this round so that no one might miss it.

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

    It seems that the "Event Time Announcer" is wrongly showing this: Event Time in Moscow, Russia 5:00 While it's going to start in 17:00 (Likely a mistake --> 17 = 5 p.m) So its start time doesn't really differ from the last one ;)

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      i think what m17 means is that most CF rounds start at 1930 MSK, but this one starts at 1700 MSK.

      → Reply
»
10 years ago, # |
  Vote: I like it -14 Vote: I do not like it

easy problems are not good, because the rating matters how fast you solve the problems :/

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

    Easier problems are good, because it matters how many problems you solve and not just how fast you can solve them.

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

      First of all sequence of problems should be without large gaps in dufficulty, so a bit stronger contestant may easier overcome weaker one by number of problems and not just by time — we are competing in solving first of all, not in typing speed, right? Otherwise there is no difference — "500 guys solved 3 problems, 20 guys solved 4+" and "500 guys solved 1 problem, 20 guys solved 2+" are almost same scenarios for me.

      As I mentioned in russian topic after last round, that round was pretty good — every problem was solved by 10+ users, nobody solved all 5 problems, number of AC is decreasing from A to E...

      And I compared that round with "standard 1/5/50/500 round" (talking about number of users with first 5/4/3/2 problems solved). In my personal opinion rounds like previous one are way more interesting than "standard 1/5/50/500".

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

a math round?

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

    It's only a normal CF round. :) Wish you high rating ~

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, ladies and gentlemen! It's DZY's show time! :)

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

As it is Ramadan, is it possible to shift the contest at least 30min ? Current Contest starting time is same as the iftar time here in Bangladesh.

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

    But great time in Iran! After the contest and system testings we have about 40 minutes to solve the unsolved problems and guess what after that! Iftar time! :)
    And it's similar for Russia! (But just for their international time! As you know, Russia is really long country and I think the difference between it's leftmost city and rightmost city is something about 9 hours! Russians correct me please).

    → Reply
»
10 years ago, # |
  Vote: I like it -33 Vote: I do not like it

why is Codeforces Round "#FF" ? 0xFF = 255, maybe the Round #FF is the next of Round #254 ?

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

That sounds Great! I hope it can be successful.

→ Reply
»
10 years ago, # |
  Vote: I like it +22 Vote: I do not like it

I can't participate to this contest because of the flight to IOI place.

→ Reply
»
10 years ago, # |
  Vote: I like it -86 Vote: I do not like it

What does fuking FF mean?

→ Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I think the next contest will be "Codeforces Round #100" as: FF + 1 = 100 (base 16)

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

hmm, really odd email i received from Codeforces.

I'm glad to invite you to take part in Codeforces Round FF (Div. 1 and Div. 2). Actually it will be two separate rounds "Codeforces Round #254 (Div. 1 Only)" and "Codeforces Round #254 (Div. 2 Only)".

firstly, there's no # before FF, which is usually always seen in all CF rounds.
secondly, "Codeforces Round #254"? seriously?

PS: take this as constructive criticism so that next time these mistakes can be avoided.

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

    That means I'm not the only one. At least not the only one to notice :D

    Maybe an automatic mailing system got confused: "Which name is round FF supposed to have? Oh well, I'll just use the latest one."

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

    The round number is greater than 254. Codeforces rounds always have had number not greater than 254!

    → Reply
»
10 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Oh my god... this is last round...

Next contest don't will... overflow byte..

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

    No problem. Contests will start again from Round #0!

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

Hello from Taiwan.

thanks for our last chance to practice before IOI. Good luck and have fun everyone.

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

    be careful! you will be demotivated if you failed a round just several days before competition. It may bring negative effect to the competition.. haha (at least I experienced this once.)

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      I already succeeded last topcoder round :D , I hope that I also succeed in this CF round.

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

        Ah OK then, at least you already motivated by something :)

        Anyway goodluck for IOI! :) It's very sad that I can't participate in IOI anymore :'(

        → Reply
»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Please prepare a readable and thorough editorial. Thank you :)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I hate when it says 'The solution is obvious' Waiiiiiiiit Nooo that is why I am here x)

    → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For me, entering this round means not watching the World Cup Final. it's difficult trade-off...

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

    No conflict between this Round and WCF ??!!! maybe you have no time for both

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

      yes, I have at most 4 hours to sleep, if I do both.

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

        Who cares about sleeping if World Cup final is just once in 4 years?

        → Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Soccer Maniacs wouldn't attend this round :v

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

Score distribution is a bit strange for me. 500 from Div1 used to be equal to 1500 from Div2, I guess, 1000-to2000, and so on. Today task C from div2 costs 2000, but task A in div1 (which used to be the same with Cdiv2) costs only 500. But, according to the logic of previous rounds score distribution, it must be 1000.

I understand, that authors know better, which one is correct, but isn't it a mistake?

UPD: Changed to 1500

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it -6 Vote: I do not like it

    I think This time task A Div1 Equal task B Div2
    My Guess is
    Div1 Div2
    A = B
    B = C
    C = D
    D = E

    so the difference between two rounds will be A Div2 & E Div1
    maybe I'm wrong let us see

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

After do contest I will watch FIFA World Cup between Argentina and Germany

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

div2 B shows 1000 in the contest.

→ Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I...don't understand why Div 2 Problem A begins with "DZY has a hash table..." Do the problem writers actually expect Div 2 contestants know what a hash table is? (Div 2 contestants that can solve Problem D/E are okay, but how about beginning contestants that can barely solve Problem A?)

Personally, this is approximately how I'd phrase it:

DZY has p buckets, one of which is colored red. Each bucket can hold one ball. For the i-th ball, DZY starts with facing the red bucket and turns clockwise for xi buckets before putting the ball into the bucket in front of him. However, sometimes DZY cannot put a ball because the bucket he's facing already holds a ball. Output the number of the first ball that DZY cannot put.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it -14 Vote: I do not like it

    There are alternative solutions for this problem without hashtable,We can do Vector Add numbers and Vector Add module for every number and every time , you must check , Are this number contains in this vector or not :) Hope it help

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

      I know there is a solution without hash table. (When I finished reading, I already got the solution using simple arrays.) However, the problem here lies on the wording. It feels like you need to know what hash table is (even if you eventually don't use it) just to understand the problem. My view is that problem wording should be as simple as possible, even if the solution can be terribly complicated.

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

        Here's a hopefully comparable analogy:

        You are given points on the plane, forming a polygon. It is guaranteed that the polygon has a dihedral group of order 8. (Test case has no picture of the polygon whatsoever.)

        You will most likely say "WTF" on the last sentence. Compare:

        You are given points on the plane, forming a polygon. It is guaranteed that the polygon will be symmetric like a square: when you rotate the figure by 90, 180, or 270 degrees, the polygon remains the same, and when you reflect the figure along some line, the polygon also remains the same. (Test case has a picture of the polygon, explaining the symmetries.)

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

    that's just a bluff :P

    we can see high number of accepted submission for that :)

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      In hash table, if you put more time one number than it is not collision, but in this problem it was colision :(

      → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In problem A (Div1), are we allowed to change the numbers to zero? E.g. what is the answer for sequence (1 1 2 3) — 3 or 4?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried hacking BhulJa div2 C which should have given garbage value for N=1 but it returned correct answer I don't know why .

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Hi, Can anyone please explain your approach of Div1 B / Div2 D ?

Thanks.

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

    The mathematical proofs are maybe a little bit long but pretty intuitive. Obs.: 1) It doesn't matter in which order you do the operations. 2) You can let 0<=l<=k be the number of line operations (and take the best variant at the end). 3) For a fixed l, use 2 priority queues to calculate the results for l and k-l elements picked both for rows and columns. 4) Combine the result for l (on rows) with the result for k-l (on columns) with a little bit of maths. 5) Don't forget about long long.

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

      Is this equivalent to the greed solution? In my solution, at each step, I would select the best row or column (the one with greatest sum) using two PQ. I don't know if greedy works (couldn't prove it), but it really feels like it should work. No idea why WA. :(

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

        I got WA on pretest 4 doing the same thing!

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        It doesn't work.

        2 3 6 1 1 1 1 1 1 1

        Sometimes you don't want to select the best row in order not to start getting negative sums.

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

        It doesn't work. Consider 1 3 10 1 1 1 1

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

        i'm just guessing here, but did u consider that every row's sum reduces by p during every column operation (and vice-versa)?

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

          Yes JuanMata. It looks like Greedy is a bad idea. (Greedy is almost always a bad idea. I will try to remember that next time) :(

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

            Actually there is a huge greedy part in the solution. You just have to be sure when you are using greedy algorithm, you should have proof or something (maybe not very rigorous).

            The greedy part here is that if you look at choosing rows and columns separately, when it's about rows, it's always right to choose the largest row. Same hold for columns. Than it's easy to solve this 2 problems separately and merge them. You're gonna need to brute force how many rows you choose.

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

              Forgot proof of a greedy strategy. Choosing largest row is optimal, because: (1) The order of rows chosen doesn't affect the final score; (2) Assume in the optimal solution the largest row was not chosen. Then, swap the largest row with any other chosen row. Obviously the score will increase, hence contradicting the optimality of a solution.

              You can also prove that you can choose just rows at first and then choose only columns. I guess the details are already posted (at least in the editorial), so I won't go further into details.

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

        No, its not equivalent. You solve the problem for only rows and only columns separately, and then choose how many rows and how many columns to use based on these results. The key observation is that each row operation reduces the results of each following column operation by p, and vice versa, so the total score is ScoreRows+ScoreColumns-NumRowOperations*NumColumnOperations*p, regardless of the order in which you do the row and column operations — this is because for each pair of RowOperation and ColumnOperation whichever comes first reduces the result of the other one by p, and there is a total of NumRowOperations*NumColumnOperations pairs.

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me to understand why my solution for div 2 problem E is too slow to pass test 9?

I use segment tree + lazy updates.

Thanks.

→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In Problem C, DZY Loves Sequences, I made a minor mistake of initialising a variable to 0 instead of 1. So naturally, it gave WA. But after correcting the mistake and trying to re-submit, it says that The exact code has already been submitted, and I could not submit it. How is it possible?

P.S. I had saved the file.

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I am being hacked at 17:57:37, The Codeforces send me the Announcement at 18:59:25, and I am very surprised about this (so bad)

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry if this is a stupid question, but how long does it usually take before the ratings are updated?

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

    It's not stupid! I've been asking this question from myself since i've been taking contests! It never has a fixed time. It usually takes half an hour before the system testing part and half an hour (or even more) after that for rating updates :)

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

my idea for C div 2 is split the sequence if it's not an increasing subsequence, and join with the neighbour if possible (change 1 number from sequence left or right, and made strictly increasing seq)

here is my submission http://mirror.codeforces.com/contest/447/submission/7087449

any other ideas or my idea wrong ?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can merge three consecutive segments(increasing sequences) also if the middle segment contains only one element and the first element of the right segment > last element of first segment + 1 .

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      hmm, cant think of test case for something like that while contest

      anyway, thx for the answer

      edit : my solution just lack +1 to the output if the max sequence isn't obtained from 2 sequence :)

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody explain me how to solve div-2 D . thnx

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I encounter a strange issue during the contest. my ID became duplicate and every time I refresh my submission page its contents were different !

and when I locked my problem C ! (notice to contest time running!)

and some seconds later :

I deleted all my codeforces' cookies during the contest but still nothing were changed!

what was the problem MikeMirzayanov?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I'll investigate it. Thank you. I'll exclude you from the rating. It seems somehow you were registered twice (race condition?).

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

      Yes, You're right. I have registered twice because I didn't see myself in registered users. Interesting racing condition!

      → Reply
»
10 years ago, # |
  Vote: I like it -10 Vote: I do not like it

why is system testing unusually slow today?

→ Reply
»
10 years ago, # |
  Vote: I like it +87 Vote: I do not like it

I will never believe in Chinese authors' word about easiness of the contest, specially of dzy493941464 :(

→ Reply
»
10 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Who's idea to make C and B same points. Oh, well done really, Solvers of B is 6 times more then C :

64 * 6 ~ 343

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

why most of div2 C submissions failed system tests ?

can anyone give me the tricky test case which most contestants couldn't pass ?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    I'm not exactly sure whether this is covered by pretests or not, but does your program work for 10 1 2 3 10 4 5 6 10? (Answer is 5; take indices 5 to 9 and change the middle 10 to something low. (Or indices 1 to 5.) You cannot change the middle 10 to 3.5 to take indices 2 to 8.)

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

    I'll guess just some cases:

    • n=1

    • the optimal subsequence takes 0 changes to make

    • the changed element is the leftmost/rightmost

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

      I missed the second point. :(

      Just added : if(!ans)ans=n;

      Became AC

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

    some forgot to check whether two segments of strictly increasing order are able to be merged or not, for example:

    6 1 2 3 3 4 5

    the two segments are [1, 2, 3] and [3, 4, 5]

    these cannot be combined to form one strictly increasing sequence.

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

    Try: 2 1 1 Answer should be 2

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    thanks all , I found the test case that my code didn't solve correctly

    5

    1 2 10 4 5

    the correct answer is 5

    → Reply
»
10 years ago, # |
  Vote: I like it +81 Vote: I do not like it

DZY definitely starts to please me.

→ Reply
»
10 years ago, # |
  Vote: I like it +47 Vote: I do not like it

three people scored 1134 points, and they took the (joint) 254th position.
this unfortunately means that nobody could take the 255th position in the 255th CF round. :(

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I got tle on test case 9 in div2-Q5. I used segment tree. was that too tight for the time bounds?

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

    this is my code, possibly someone could suggest an alternative -> direct link

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

      I have not tried the problem but maybe you could get the fibbonacci number using matrix exponentiation !

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Maybe problem with tree array size or recursion? When i downloaded your code and run it on simply test like this: http://morse.swirski.name/pastes/l6hriqm93kn5wx5gvxckznn0ibd5zvh program crashed in build_tree() function.

      When i change tree[] size i don't have this problem. But i'm not sure, cause it was on Windows 7 x64.

      P.S. Sorry for my english.

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

        if the solution did crash in build tree function, then it would had not run in that case. I checked the log and it seems that the tree was built perfectly but the program ran out of time while processing the M queries.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Wait... your update is logarithmic? You stop recursion only when low==high (in leaf). So update is too slow in my opinion (You must visit every leaf in (l, r) ).

          → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why DIV2 problem C's test 41: 6 7 2 3 1 4 5 answer is 4?

→ Reply
»
10 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Nice contest :D

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

Excuse me. But why my rating hasn't updated? I found that everyone's rating has been calculated but mine hasn't done.

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

    Oh, sorry. Only Div.2 competitor's rating has been updated.

    → Reply
»
10 years ago, # |
  Vote: I like it +17 Vote: I do not like it

You can view country wise standings here. Send your hugs or bugs here.

→ Reply
»
10 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Div1C http://www.spoj.com/problems/ANIL_PRO/ or http://www.hackerearth.com/problem/algorithm/fibonacci-updates/

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, I really appreciate an opportunity to test my solution for WA/TL on spoj during CF round, but I don't think it is a good idea to give such problems on CF rounds.

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

      I am sure it wasn't on purpose. It's impossible to know all problems from all contests/online judges. And it seems that it is not so easy to google the statement of this problem.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 3   Vote: I like it +1 Vote: I do not like it

        I am not sure that it is easy — did not tried to google this one, already seen it on SPOJ before)

        But now I tried to search for fibonacci updates array query problem and some other similar requests and both of these problems are at first page)

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

        not so easy to google

        I wouldn't be so sure. Just keywords from the problem statement, plus where to look (I always add "online judge" when I'm looking for a problem without specific source competition).

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

          Yes, you are right. I tried another search queries and failed to find this problem, but it is definitely not so hard to do this and authors should have do that.

          → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone try to solve Div2 C using two pointers?

→ Reply
»
10 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Is the contest unrated for Div.1??? The rating of Div.2 was updated, but Div.1 not.

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

    It went well and there was no announcement, of course it's rated. It just takes a long time for some mysterious reason.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    LOL, it's like this was a Div-2 only contest. :D
    seriously, i guess it's just a small system issue. i'm sure ratings will get updated soon. :)

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What asymptotics should be in Div2-D? I had O(pk) (I hope) and got TL. Now I wonder is it too bad or just Python?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Should be O(k logn + k logm)

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Solution from editorial works in O(k * log(n) + k * log(m)); however, it is possible to do it in O(k * (n + m)) and fit into TL easily (7093794).

    Upd. This solution is wrong (i described problem here). But you still can pass system tests with it)) Changing long into long long to fix overflow issues will make it correct, but with long long it does not fit into TL.

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

      Is long long that much slower than int? Is Codeforces on 32bit machines?

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

        Yes, it is ~2 times slower.

        You may change

        long si[12000],sj[120000]; into long long si[12000],sj[120000]; in my solution and it will work >2s.

        → Reply
»
10 years ago, # |
  Vote: I like it +22 Vote: I do not like it

i'm hoping that the ratings of Div-1 will be updated before the World Cup final starts.

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

    i'm hoping that the ratings of Div-1 will not be updated

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why DIV2 C test 27 1 1 2 3 4 answer is 5 (not 4)?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why this submission is giving Runtime Error?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it 
    vector<int> hashi(p);
for(int i=0;i<n;i++)hashi[i]=0;

    Something isn't right here...

    → Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Round Stats

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In question C. DZY Loves Sequences

Shouldn't the answer of (testcase #27) 5 1 1 2 3 4 be 4? Value of ai can never be less than 1.

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

    Read the problem statement carefully ... It says change one number to any integer you want.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't see why we need all the complicated logic in the editorial for Fibonacci problem. We can simply precompute the first 300000 values linearly and store them in an array.

→ Reply