Ripatti's blog

Codeforces Beta Round #74
By Ripatti, 13 years ago, translation, In English

Hello everyone!

I am an author of problems of today round. This round is for both divisions. There will be 7 problems, the first 5 of them are for the second division and the last 5 are for the first one.

About points of problems. Today they are nonstandard:
for div2: 500-1000-1500-2000-2000
for div1: 500-1000-1000-1500-2500
Be careful.

RAD helped me for preparing the round. Delinur translated statements into English.

Good luck ans have fun.

UPD.
 winners of the first division
1. peter50216
2. tourist
3. ACRush

winners of the second division
1. iamcs1983
2. zyx3d
3. seanwupi

Editorial.

UPD.
Unfortunately, in author's solution of priblem E some bug was found. We thanks participant LinesPrower for detection of it. Author's solution was updated and all solutions were rejudjed. Ratings will be recalculated for all participants excluding Egor and Jacob. We apologize for this incident.

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

Comments Comments (76)
| Write comment?
13 years ago, # |
  Vote: I like it +14 Vote: I do not like it
CF #59(Div2) , CF #65(Div2) , CF #68 , CF #70(Div2) and now CF #74

Very Nice : Surely will have a good contest :D
→ Reply
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
good luck every one
→ Reply
13 years ago, # |
  Vote: I like it -8 Vote: I do not like it
It was nice contest.... i wanna know a few things as m a newbie...
1. What are hacks????
2. Is there any penalty for incorrect submissions
3. On what basis points are allocated to user who has correctly solved the problem!!
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    you can(and should) read it
    Today standart points for problems some unusaul
    div2: 500-1000-1500-2000-2000
    div1: 500-1000-1000-1500-2500
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    ... I found that  submissions that didn't pass the pretest ..will not cost penalty ... ;)
     . This is really helpful ..

    PS: .. The version of the Ruby compiler isn't clearly ...
    ... .. which induce me lots of CE && RE submissions more than once ..
    Maybe the version is 1.9.0 or higher .. cause the String::[] is return a char ... 
      
    ... And one more suggestion ... there should be one more language option named .. "Auto" .. ;)
    .. literal meaning .. auto-distinguish the language according to your suffix name ...
    ..simply "cpp" stands for GNU CPP .. "pas" stands for "Free Pascall / Delphi "... 
    which could also be some user-preset perhaps ..

    → Reply
13 years ago, # |
← Rev. 3   Vote: I like it +31 Vote: I do not like it

E/Div2
At the first time i read the statement , I thought n,m<=5000 ,so i have to look for a O(N*M) solution and It 's really hard to solve , why so many people accepted ? I can only solve it in O((N*M)^2) .  It takes me 50 minutes to notice that n*m<=5000 , it's 1:53:00 , too late . My rating continues to decreases :( . this is the fourth consecutive time
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi, I was encounter something strange.

In the problem C, I was received two same hacking.
I was success defense at the first one, but the second one I got TLE.
Is this situation regular?

Actually, I can't 100% sure that two hacking are the same.
Since I can only see a part of the input：
######
1 5000
RRRRRRRRRRRR....
######

But I guess they are same.
Thanks.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    1 5000
    RRR...RRLLL...L (half of 'R', half of 'L')

    I think this one makes you TLE.
    Some brute force algorithm is O(N^3) on it.

    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    How could you see the input used to hack your code?

    I tried to see the input used to hack my problem A viewing my code
    at "my submissions" and by double-clicking the score/points of problem A
    at the "room" area. But in both cases I just saw the pretest cases, it didn't
    show the hack input.

    Thanks.
    → Reply
13 years ago, # |
  Vote: I like it -6 Vote: I do not like it
How can my solution fail for 1 5000 R* when on my local machine it runs in 0.4 secs. Is that CF judge that slow? I thought the complexity of the solution would be R*C ^ 2, with a dfs for every node atleast for that case.
→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
why I can't see rating graph in my profile page ?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Some features are temporary unavailable during the contest. Will be restored soon.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
it's for all!
i think for increase speed of process!
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
What time analysis will be up???
→ Reply
13 years ago, # |
  Vote: I like it +33 Vote: I do not like it
During the contest(hack), the window to view codes was too small and I could not see the entire code when the code contained a long line. The view sometimes collapsed.
I hope the UI of current hack window will be improved.
→ Reply
13 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

My solution doesn't produce any output. I submitted many times during the contest. What is wrong with this solution. It works fine in Ide one and locally too.

Link.http://www.ideone.com/BcunL.

Edit: During the contest my submission ids were:
492767
492737
492505
492349
492236
492131
492074
492035

After contest:
494437
494398
494274
494260
494238
494173
494293

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

    You need System.out.flush() in the end
    ouups, nevermind, you have close
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    System.out.println(res.toString())

    Edit: The problem with your template in nextLine() try simple main and it will pass.
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      No it does not help. But it works locally and in Ideone. Have you tested it on your system ?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Yes, I try your solution and it is accepted,check it now.
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Could you paste it in IdeOne ? But what exactly is wrong is what I would like to know. It worked under my system, IdeOne. But why didn't it work in codeforces ?
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            http://www.ideone.com/6ESAG

            I just replace your main with another tested main with the same code in your method solve() and it runs smoothly !! I recommend test your main template before use.
            → Reply
            • 13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Thank you. I submitted it and it was accepted.

              But did it work under your system? I have been using my template for a while now and never had problems.

              Submitting it many times and getting a wrong answer on Pretest 1 is a bit frustrating. Could you post your observations on what could have gone wrong.
              .
              → Reply
              • 13 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                I can't recognize the problem in your template, so what about change your template you can try this one 
                It is the same of your template with small changes I remember i took it from Egor
                → Reply
                • 13 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  But did it run in your system ?

                  My template is similar to Egor's. I will go through it.

                  Edit: Oops, I meant whether my solution ran in your system.
                  → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
why my rating doe'snt update?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi everyone.

C\DIV 2.

can anybody explain me why the answer is 0 for the test case like this

5 2 9494412
5484 254 1838 18184 9421

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Because he can move diamonds only two times between two checks. But he should do at least three operations to steal a diamond.
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Why does he need to do at least 3 operations? Why can't he move one diamond from 5484 to 254, and then take one from the 1838 for a total of 2 operations and resulting in 5483 255 1837

      Nevermind, that would change the sums on the later parts of the array. Sorry for the confusion.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        After this operations we have
        5483 255 1837 18184 9421

        But it's easy to notice that 1837+18184 is not equal to 1838+18184.
        → Reply
      • 13 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Sum 1838+18184 will differ from 1837+18184.

        → Reply
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Good Questions.
Specially div2 E.
Every -one got tricked very badly.
1.Few got tricked that they did not notice n*m <= 5000.
2.Few got tricked that, after noticing n*m <= 5000 , they just thought...
WoW!!!  5000*5000  will pass,so easy ,  hahaha, I can write this
(Didn't Even think for a single minute that this cannot pass, even after having 1 hr at hand.)
That was me .   Kill me !!  :(
---------------------------------------
P.S : Now I notice , it was required to make a graph and re-assignments of left,right,up,down . 
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
For problem C:
The brute force algorithm has O(N^3) time complexity for some data.
Some people use it and get a due TLE.
But when I hacked masha_and_beer's code using the data: RR...RRLL..LL
It returns that his code runs about 1000ms and get the correct answer.

I think his ideal is just the simulation without any optimization.
And I copy his code and run it for the data I hacked him, it runs about 23 sec in my MacBook.
But I run it code using Custom Test, it runs in 1sec.

Can anyone explain why his magic code runs so fast on the judgement and can Pass? 
Thanks.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it 
    move[dir][opy][opx].x = px;
    move[dir][opy][opx].y = py;
    The code is not pure simulation. It does remember something :D
    (edit: I can't use this editor correctly...)
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thank you, I understand now.
I think his ideal is something like Path compression, which I also used to solve this problem.
But my approach is union-find sets.

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    So, why did it ran for 23 secs on your Mac  And  1000 ms here?
    Please throw some light.

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Oh, I did't really know why now.
      I run his code in XCode on the MacOS, it only cost 4 sec.
      But in Dev-Cpp on WinXP it cost more than 20sec.
      Can anyone explain it?
      It happens not once, I noticed that before this time.
      All the time it happens the code use vector, map or some others in STL.


      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it
        Looks like you compile without optimizations (-O2).
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Oh my god, you are right.
          I add this optimization and runs in about 1sec.
          Thank you very much, I had troubled with this several times.
          → Reply
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Can any one tell me where is the editional?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Lesson: Try to learn all aspects of C++ STL then use them

During the contest I used a O((R*C)^2 log (R*C)) algorithm for problem C which I thought that would work but surprisingly it got TLE. when I debugged my code after the contest, I found out that copying the "map"s takes too much time...
→ Reply
13 years ago, # |
  Vote: I like it -15 Vote: I do not like it
peter50216 - это Митричев чтоли? :)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it
    Это его китайская копия =)
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Chip Play  For every point, starting from it dfs a time to find the length ,whether the complexity is O ((n * m ^ 2)?

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    note to this test:

    1 5000
    RR..R(2500)LL..L(2500)
    for this test case, the complexity is O(n3).

    you can use linked-list for AC , for each cell which has chip, consider four pointer.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
When will the editorial will appear?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can I hack someone's submission  after the contest? If so, and  how? thx for explanation!
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
could someone please tell why the loop in the solution of "Problem C - Robbery" has i+=2 , shouldnt it be i++. Why are we ignoring the even numbered terms . I mean why are we considering 0,2,4,6..... and ignoring 1,3,5,7 indexed terms. ???

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

    Because there is only one way to steal the diamond: inc all odd cells and dec all even cells.
    How long can it continue? Of course, min(all(a[i])) where i is even
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Because there's only 1 way of moving diamonds so that Joe can get more diamonds.
    Consider: a[0], a[1], a[2] ... a[n-1].
    Sums are (a[0]+a[1]), (a[1]+a[2]), ... , (a[n-2]+a[n-1]).
    (n-1) sums mustn't change, and their sum mustn't, either.
    We can see that a[0] and a[n-1] are counted once, while the others are counted twice. Therefore, if Joe want to get 1 more diamond, he will move 1 diamond from a[0] (or a[n-1])  to the middle, so it will be counted once more, and move 1 diamond from a[n-1] (or a[0]) to his pocket.
    This is how Joe should move diamonds:
    Move 1 diamond from a[0] to a[1] -> (a[0]+a[1]) won't change, but (a[1]+a[2]) will increase by 1. So Joe doesn't need to move from a[1], but a[2] to a[3]. And so on ...
    0->1 , 2->3 , 4->5, ... , (n-1) -> Joe's pocket.
    Joe can get more diamonds unless 1 number in a[0],a[2],a[4],...,a[n-1] = 0.


    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Where are the solution to the Problems??? plzz reply m a newbie...
    → Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
I solved 90C Robbery in div2 only contest, but the time the number of problems I solved in the problemset increased by 1 was when I sovled the same problem(89A Robbery) in div1 contest for practice.
Could you make the system to where when I get AC the number of problems I solved in the problemset increase by 1 regardless of where I solve it?
→ Reply
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
The top 3 contestants are now the same as in TC:) Things will converge in the last.
Of course, this peter is awesome too... He reminds me of what Petr did in TC when he first entered the website years ago.
GL, HR & HF Everyone!
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    peter50216 won the div2 of Topcoder too a day before his first codeforces round.

    sorry: he didn't actually won, i should have checked before posting..

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

      whats the handle of peter50216 in tc? he've beaten tourist in his first cf contest in div1,thats amazing.

      Edit: http://www.topcoder.com/tc?module=MemberProfile&cr=22929522 Thats his handle,participated in only one srm.
      → Reply