Sammarize's blog

Codeforces Beta Round 79
By Sammarize, 13 years ago, translation, In English

Hello!

I'm, Valeriy Samojlov, graduating student of SPbSU,  present you codeforces beta round 79. Today you will meet with boy Gerald and will help him to solve some living problems. 

Today we have usually cost of problems in both divisions: 500 - 1000 - 1500 - 2000 - 2500.

It my first codeforces round, I hope, problems will be interesting.

I want to thank Artem Rakhov (RAD) for big help with preparation of problems, Makar Krasnoperov (Connector) for some useful remarks and Maria Belova for translation.

Good luck for participants of both dovisions!


Contest is over! Congratulation to winners!

Division 1:

1. RAVEman

2. ilyakor

3. ACRush

Division 2:

1. SuperLight

2. xiaowuc1

3. Timur_Sitdikov

Editoral a appeared.

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

Comments Comments (58)
| Write comment?
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Everybody will show his best performance in this contest.... 

Best of luck ..
:)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Easy problems even the E was easy :) Nice contest.

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


Nice contest. :)

What is the complexity of the intended solution for problem D div 2? O(m) ? O(m*log(m))?
I tried to implement a O(m) algorithm, but maybe there is a simpler one in O(m*log(m))?

Any help appreciated!
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    There is O(m*log(m)) algorithm.
    The main idea is:
    1. If n is small, we can use DP - just calculate answer for each point
    2. Then, we understood that we are interested only in points, which are end point of some bus and our start point
    3. The last thing is to recalculate DP faster, than O(m). We have two types of events - some bus' segment is started/finished. Sort them and be happy
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks for the quick reply.  Indeed each update of step 3. can be done in O(log m). 
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I did a O(m) solution using a dp array .. and it exceeded TLE .. to me it's kinda weird cause there are only 1e5 distinct states for the dp, that is not that big and I think it should have passed the system.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        You sure your complexity in O(m)? Do you visit more than O(1) others dp states to calculate one single state? If so, the complexity is bigger.
        If not, it's really weird. A lot of AC solution have complexity O(m log(m))...
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it
          I guess you are right .. I checked my solution again and I'm doing O(m^2) .. 
          → Reply
      • 13 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        Take a closer look at your solution, it is not O(m). You have 1e5 states and you use 1e5 to  calculate the value for each state (the for in the dfs method). Conclusion: O(m^2) solution.

        Besides, I'm not a big fan of Java, but if it passes arrays around by copy, that's a huge overhead that you are not using class variables for the arrays...
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          yes you are right about the O(m^2) .. I totally missed that.

          Regarding java, I don't think it passes a new copy of the array. for objects more than the primitive data types, it passes the object as a pointer to the same memory location.
          → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Or just scale n to O(m) and run dp.
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      Actually, I have trouble understanding how to do the update faster than O(m):

      Call num[t] = number of ways from the position t (a bus stop or the value 0). 
      num[max_t] = 1 and the result to return is num[0].

      the update rule at time t is:

      num[t] = c*num[next_t]

      where t is a bus final stop, and next_t is the next position where a bus stops.

      and c is either r or r+1

      with r = number of buses that start before or at t, and stop at exactly next_t.

      c = r+1 if there is a bus that starts before or at t, and stops strictly after next_t,
      c = r otherwise.
            
      I see how to get the value r in O(log m),
      but to determine efficiently whether c should be r or r+1, I'm at a loss. 
      Anyone knows? Or is there a simpler way to look at it?

      Thanks for your help.

      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it
        The key to solving the problem is to look at it from the other side. Instead of defining num[t] as the number of ways to reach the end from position t (and then solving back to front), define num[t] as the number of ways to reach t from the start.

        With that definition, num[0] = 1, obviously, and to compute num[t] for increasing values of t, we can do:

          for each bus starting at s and ending t:
            for s <= i < t:
              add num[i] to num[t]

        Of course, we must first compress the coordinates into a range O(M) so our num array is small enough. Additionally, to avoid an O(M) inner loop, we can keep track of the accumulated sum of num[0..i]; with that, we can compute sums of num[i..j] efficiently too.

        If you can read C++, my commented solution shows the details.

        By the way: don't feel too bad about not being able to solve this one. I thought it was a pretty hard problem, despite its point value. I'm rated red here, but I could not figure this out to save my life during the contest!
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Thanks for the explanation, and the clear solution.

          It's tricky to adapt the outer loop to include the computation of num[0..i] from num[0..i-1] in O(1). 

          → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    There is O(m^3/2) solution that can get accept to
    idea is seperate array in to  m^1/2 array
    → Reply
13 years ago, # |
  Vote: I like it +16 Vote: I do not like it
Pretty fast system test it was :)
→ Reply
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Can some one explain div2 E? I am bad at vector calculation.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    If you think about it, the vectors you can construct with the given operations are the same as those when you start with rotating A up to four times, and then adding C or one of its rotations to A.

    This is convenient, because we can just try the four possible rotations of A and subtract them from B. Then the question becomes if we can express the resulting vector with integer coordinates in an orthogonal system with C and its rotation as axes.

    So after we compute D = (B - roti(A)) for i={0,1,2,3} we want to check if there are integers x and y such that x*C + y*rot(C)=D. Since C and rot(C) are orthogonal, we can decompose D into independent components using scalar projection, and from there we can compute the value of x (or, in this case, just check if its integral). For example, x is integral iff C·D = 0 mod |C|2, where · is the dot product.

    A different approach for the last part is to write the equation     x*C + y*rot(C)=D as a system of linear equations (C, rot(C) and D are all known) and solve that using Gauss-Jordan elimination. This is a bit more work if you don't have code prepared for this, but requires less thinking if you do.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      quite nicely written.I understood everything.I want to study this topic thoroughly . suggest me appropriate material if u can
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Not sure if this is the right place to ask, but I haven't found it anywhere... what happened to the rating graphics on user pages? I cannot see them under linux with firefox or chrome.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    They are disabled in the contest time .. it should be updated now .. 

    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    In the contest, it will temporarily stop some of the features. This will make the system faster.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can any one tell me if i wrong to use %lld in c++?
it should be %I64d instead in this contest ? 

i fail one prob because of this : (
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    %lld is for linux, %I64d for windows.. and codeforces sytem runs in windows..
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Actually %lld is for GNU Compilers, and %I64d for Microsoft's. And the real problem is that %lld doesn't work correctly in 4.6 GNU Compiler port on Windows, which is using here
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        Really actually: it's a feature of the C library, not the compiler.

        Both POSIX and ANSI C allow ll as a size prefix, but Microsoft doesn't implement either standard.

        If GCC on Windows calls the printf() implementation in Microsoft's C library, then it probably behaves incorrectly too. The fact that it works on Linux is not thanks to GCC, but thanks to the GNU C library.
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it
          Also, Visual Studio handles %lld correctly. So if you want to submit solution which uses %lld, you can just choose MSVC compiler instead of GNU one.

          → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes, you can read it in FAQ and btw it's often written in problem description.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      yeah but no task in this contest which expected to use %I64d..
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        therefore it wasn't written in this contest)
        → Reply
        • 13 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Normally when you need them it is specified on the statement.
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Firstly, I wrote this round in Java, and, btw, I didn't need any long variable ( c++ long long equivalent).
            → Reply
            • 13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              I don't know how you solve E but my solution have to multiply somepoint and . . .  . since coordinate are in range (-10^8,10^8) so it overflow when i use integer?
              → Reply
            • 13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Therefore then I try to test after the contest i found that my solution fail in really small input (which is correct in my computer)
              → Reply
13 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I can't understand the algorithm for Prob E-Div2/Prob C-Div1.
why after vector A rotated,both [(B-A)cross C]%C^2==0 &&[(B-A)dot C]%C^2==0,the answer is YES?
Could anybody explain it for me? Thanks!
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    i think it's C^2?
    if  [(B-A)crossC ]%C^2 ==0 && [(B-A)dotC ]%C^2 ==0 ] answer will be "YES"

    it's because if you dot vector  AdotB = ||A|| ||B|| cos(zeta) and if you divide by ||B|| it's ||A|| cos(zeta) (which mean size of vector A (cos zeta) that parallel to B . . .   ( AdotB  % B^2) ==0 use when you want to check if ||A|| cos(zeta) %B ==0 

    in the same way AcrossB product ||A|| ||B|| sin(zeta). 
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Why should I check if |B-A|sin(zeta)%|C|==0 and |B-A|cos(zeta)%|C|==0?
      What's the intuitional meaning?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        |B-A|cos(zeta)%|C|==0 checks whether |B-A|cos(zeta) is x times as much as C ,iff |B-A| can rotate to be parallel to C. And How can I ensure that the condition can be obtained?
        And what does |B-A|sin(zeta)%|C|==0 mean?
         
        → Reply
        • 13 years ago, # ^ |
          ← Rev. 5   Vote: I like it +1 Vote: I do not like it

          you can rotate C by 90degree and obtain C' ( rotate A and A will see that C is rotate by 90 degree)

          and vector can construct by 2 unit vector that perpendicular to each other
          ( like x= |A|cos(zeta)*i and y = |A|sin(zeta)*j in x and y axis ) and we use vector C and C' to represent unit vector so any vector construct by these should have size x time to |C| (it's (B-A) = xC + yC' (B-A)cos(zeta) = xC && (B-A)sin(zeta) = yC' )

          sorry if it's hard to read my english is not good.
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Can you explain why this condition sufficient ?

            → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            (A rotate90) + C  is not equal to (A + C) rotate 90

            so isn't it possible that the answer is something like 
            ((((A + C) rotate90) + C) rotate90)  +C    ?

            is the approach you've mentioned check this ?
            it seems to me that it just check 
            A + tC 
            (A rotate 90)  +tC 
            (A rotate 180)  +tC 
            (A rotate 270)  +tC
            where t is some scalar
             
            I don't understand....
            thx.

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

              ((((A + C) rotate90) + C) rotate90)  +C    ?
              you have C that rotate 2 two time so it become -C 
              so we consider only C and Crotate90

              so we check
              B-A+ tC + rCrotate 90\
              B-Arot90 + tC + rCrotate 90
              B-Arot180+ tC + rCrotate 90
              B-Arot270+ tC + rCrotate 90
              → Reply
              • 13 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                isn't (A+C)rotate90   != A+(C rotate90) ?
                suppose A = (0 , 1) C = (1 , 0)

                ((A+C) rotate90 + C)rotate90 != ( A+ - C )

                → Reply
                • 13 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  you right
                  but
                  ((A+C) rotate90 )rotate90 = -A-C
                  (((A) rotate90 )rotate90+C)rotate90rotate90 =A-C
                  → Reply
                  • 13 years ago, # ^ |
                      Vote: I like it 0 Vote: I do not like it
                    thx for the reply. I get it though I don't know how to prove it formally for general case that rotation of "any combination of A and C"  is combination of "rotation of A" and "rotation of C"
                    thx though.
                    → Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Where is the tutorial? Is it coming soon?
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can sombody explain Div2 Problem E-- "Vector"  more ?
Quite bad at vectors.... Thx : )
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anybody Explain algo for div2 E problem?
→ Reply
13 years ago, # |
  Vote: I like it -130 Vote: I do not like it
Горячие девачки ждут вас.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it
    Не везёт в контестах, повезёт в любви?
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It's a spam.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it
      Seriously?
      → Reply
      • 13 years ago, # ^ |
        ← Rev. 2   Vote: I like it +17 Vote: I do not like it


        I think so. Let me check again. 
        Yes, I'm 100% sure.  Why do you ask?

        A little bit more seriously (sorry):  My intention was to protect the poor twits who first click without understanding the text, and then think and use Google Tranlate.
        I wish we were able to flag posts as spam, in addition to negative votes.   Where is the right place to request the feature? :)


        → Reply
        • 13 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it
          The only thing we can do now is ignore such posts.
          I don't think there are much people on this site that click on every link they see without understanding it.
          → Reply