### Sammarize's blog

By Sammarize, 11 years ago, translation, 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:

2. xiaowuc1

Editoral a appeared. Announcement of Codeforces Beta Round #79 (Div. 1 Only) Announcement of Codeforces Beta Round #79 (Div. 2 Only)  Comments (61)
 Everybody will show his best performance in this contest.... Best of luck ..:)
•  I'll never say "Best of luck" in any contest of codeforces ... :(I think coders don't like this sentence or wish ....   :)
 Easy problems even the E was easy :) Nice contest.
 11 years ago, # | ← Rev. 2 →   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!
•  There is O(m*log(m)) algorithm.The main idea is:If n is small, we can use DP - just calculate answer for each pointThen, we understood that we are interested only in points, which are end point of some bus and our start pointThe 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
•  11 years ago, # ^ | ← Rev. 2 →   Thanks for the quick reply.  Indeed each update of step 3. can be done in O(log m).
•  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.
•  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))...
•  I guess you are right .. I checked my solution again and I'm doing O(m^2) ..
•  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...
•  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.
•  Or just scale n to O(m) and run dp.
•  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.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+1with 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.
•  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 = 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!
•  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).
•  There is O(m^3/2) solution that can get accept toidea is seperate array in to  m^1/2 array
 Pretty fast system test it was :)
 Can some one explain div2 E? I am bad at vector calculation.
•  11 years ago, # ^ | ← Rev. 2 →   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.
•  quite nicely written.I understood everything.I want to study this topic thoroughly . suggest me appropriate material if u can
•  A handbook on linear algebra would do.
•  thx ,I will read 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.
•  They are disabled in the contest time .. it should be updated now ..
•  In the contest, it will temporarily stop some of the features. This will make the system faster.
 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 : (
•  %lld is for linux, %I64d for windows.. and codeforces sytem runs in windows..
•  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
•  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.
•  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.
•  Yes, you can read it in FAQ and btw it's often written in problem description.
•  yeah but no task in this contest which expected to use %I64d..
•  therefore it wasn't written in this contest)
•  11 years ago, # ^ | ← Rev. 2 →   Normally when you need them it is specified on the statement.
•  Firstly, I wrote this round in Java, and, btw, I didn't need any long variable ( c++ long long equivalent).
•  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?
•  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)
 11 years ago, # | ← Rev. 4 →   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!
•  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).
•  11 years ago, # ^ | ← Rev. 2 →   Why should I check if |B-A|sin(zeta)%|C|==0 and |B-A|cos(zeta)%|C|==0?What's the intuitional meaning?
•  |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?
•  11 years ago, # ^ | ← Rev. 5 →   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.
•  11 years ago, # ^ | ← Rev. 2 →   Thanks！I'm suddenly enlightend.
•  Can you explain why this condition sufficient ?
•  (A rotate90) + C  is not equal to (A + C) rotate 90so 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.
•  11 years ago, # ^ | ← Rev. 2 →   :)
•  11 years ago, # ^ | ← Rev. 2 →   ((((A + C) rotate90) + C) rotate90)  +C    ?you have C that rotate 2 two time so it become -C so we consider only C and Crotate90so we checkB-A+ tC + rCrotate 90\B-Arot90 + tC + rCrotate 90B-Arot180+ tC + rCrotate 90B-Arot270+ tC + rCrotate 90
•  isn't (A+C)rotate90   != A+(C rotate90) ?suppose A = (0 , 1) C = (1 , 0)((A+C) rotate90 + C)rotate90 != ( A+ - C )
•  you rightbut((A+C) rotate90 )rotate90 = -A-C(((A) rotate90 )rotate90+C)rotate90rotate90 =A-C
•  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.
 Where is the tutorial? Is it coming soon?
 11 years ago, # | ← Rev. 2 →
 Can sombody explain Div2 Problem E-- "Vector"  more ?Quite bad at vectors.... Thx : )
•  look upstairs guys:)
 Can anybody Explain algo for div2 E problem?
•  Не везёт в контестах, повезёт в любви?
•  It's a spam.
•  Seriously?
•  11 years ago, # ^ | ← Rev. 2 →   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? :)
•  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.