By BYN, 6 years ago,

• Bayan warm-up round will be held on Sunday, October 5th 2014, 13:00 (UTC) and as indicated before, it will be held on Codeforces. Warm-up round is not a required round but top 50 are going to win t-shirts and it is going to be rated for both divisions.

• Problems have been prepared by mruxim, mR.ilchi, havaliza . We have tried our best to make the problem-set interesting and competitive and we hope you enjoy it.

• It is necessary to have a complete profile on contest.bayan.ir before the warm-up round! And please do make sure you have selected the correct t-shirt size!

• We have upgraded our contest platform, and we've made sure everything is stable, tuned and robust now. Thanks to all those who helped us test the unstable version!

• The unofficial Shortcut! Round is now accessible to all, so you can check the standings and the problems.

• Qualification round which is the first official and required round of Bayan Programming Contest 2014-2015 will begin on October 9th so don’t forget to register right now at contest.bayan.ir if you haven’t already.

• We've created a twitter account to publish Bayan Programming Contest news. Now you can follow us @bayan.

Update 1: The scoring will be: 500 – 1000 – 1500 – 2000 – 2500 – 2500

Update 2: Warm up round is finished now. We have decided to randomly give 5 extra tshirts to 5 contestants ranked between 51 and 550. And as mentioned before, we are going to have 5 random tshirt winners in our Qualification round too.

Update 3: Congratulations to top 50, specially:

Update 4: Here are 5 lucky randomly selectes tshirt winners for this round:

Update 5: marat.snowbear has published a good editorial for this round.

Announcement of Bayan 2015 Contest Warm Up

• +282

 » 6 years ago, # |   +10 Should we expect this to be like regular codeforces rounds with respect to judging? i.e: Is there pretests during the contest and final tests at the end or solutions are judged only once when submitted? Thanks!
•  » » 6 years ago, # ^ |   0 Do you translate problems ?
•  » » » 6 years ago, # ^ |   0 no... I solve them(2 or 3 of them actually xD)
•  » » » 6 years ago, # ^ |   -8 no
 » 6 years ago, # | ← Rev. 2 →   -62 First long contest descriptions, now t-shirts. :)
•  » » 6 years ago, # ^ |   -36 What's wrong with that?..The more the better, I always say!
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -31 Yes, hope for math!!
 » 6 years ago, # |   +4 Should my id on Bayan be same to my Codeforces id?
•  » » 6 years ago, # ^ |   +6 No.
 » 6 years ago, # |   +7 How to solve "Lake" from shortcut round?
 » 6 years ago, # |   -7 Will the warm up round be a rated event on CodeForces?
•  » » 6 years ago, # ^ |   +20 "and it is going to be rated for both divisions"
•  » » 6 years ago, # ^ |   +2 Yeah, The warm up round will be a rated event on codeforces.
 » 6 years ago, # |   +6 Should be account on contest.bayan.ir somehow "connected" to one on CodeForces (i.e some form with both names filled or same name or same email etc)?
•  » » 6 years ago, # ^ |   +11 No. But later you would be asked to submit your Codeforces Handel in your Bayan profile.
•  » » » 6 years ago, # ^ |   +242 Oh, no problem, my Codeforces handle is tourist.
•  » » » » » 6 years ago, # ^ |   +85 wow, so secure.
•  » » » » » 6 years ago, # ^ |   +65 obviously no CF passwords are needed!
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +114 "Oh, no problem, my Codeforces handle is tourist."So you should be able to receive our privet message on your codeforces panel!
•  » » » » » 6 years ago, # ^ |   +29 И вам привет!
•  » » » » » 6 years ago, # ^ |   0 I think you shouldn't put exclamation mark there because it sounds like you're shouting. It's just a joke, keep calm :D
 » 6 years ago, # |   +19 Does the contest use Codeforces rules or ACM-ICPC rules or something else?
•  » » 6 years ago, # ^ |   +5 Usually warm-ups use ordinary Codeforces rules, if I'm not mistaken.
•  » » 6 years ago, # ^ |   +18 The rules will be announced in the contest's email which you are going to receive day before the contest.
•  » » » 6 years ago, # ^ |   +10 Please consider shifting the round by 30 minutes to 1330 UTC. There is another contest running on hackerrank.com from 1030 to 1330 UTC. It is the main elimination round of a special codesprint organised for the indian students and most of us will miss this contest as a result.This is the link for the hackerrank codesprint: https://www.hackerrank.com/csindia14-er2
 » 6 years ago, # |   -78 WTF? Sunday is an unlucky time for round. Normal people like me will get rest at that time.
•  » » 6 years ago, # ^ |   0 So, is it better to organize rounds when everybody is busy with his duties or when many people have free time? I think the answer is obvious (and TopCoder should learn it and stop organizing round in the middle (1PM in Poland) of Tuesday for example).
•  » » » 6 years ago, # ^ |   +14 I suppose TC is trying to cater to all timezones this way. But a true competitive programmer would always find time for a contest! And yes, during free time is better. Better than when travelling by plane, for example...
•  » » » » 6 years ago, # ^ |   -7 But as far as I know, Tuesday 1 PM in Poland is not a reasonable time on Sunday in other time zone :P. 1 PM will be very good for me but on weekends, not when I'm at my university!
•  » » » » » 6 years ago, # ^ |   +8 Some parts of Russia? India (I think +6something from Central Europe)? China maybe? That's evening, and evening should be reasonable time.You've got a 6PM contest tomorrow, and you can also skip university things (I can talk, I've done some CF div2s partly during lectures :D).We can't always have perfect times, or China would ヽ༼ຈل͜ຈ༽ﾉ RIOT ヽ༼ຈل͜ຈ༽ﾉ
•  » » » » » » 6 years ago, # ^ |   +2 You missed key point of my reply. When there is a Tuesday in Poland in all other places on Earth there is a day from set {Monday, Tuesday, Wednesday} and that set does not contain any weekend days ({Saturday, Sunday}), so this is quite easy to pick better day.
•  » » » » » » » 6 years ago, # ^ |   0 Yes, I focused on the 1PM and not on the weekday... and that your next reply contained "time zone" didn't help either :DIn that case, I have no idea either. Weekend is a better choice generally. Anyway, dirty random weekday peasants vs glorious Codechef fixed weekend times' master race :D
•  » » 6 years ago, # ^ |   +44 Don't try to find normal people among competitive programmers
•  » » » 6 years ago, # ^ |   -13 you are a con and you are proud about it? it's nothing to add.
•  » » 6 years ago, # ^ |   +1 Can a Programmer be a normal person? :)
 » 6 years ago, # |   -43 Rated?
•  » » 6 years ago, # ^ | ← Rev. 3 →   +46 So people nowadays just read the announcement title and jump straight to comments to ask "Rated?" without bothering to read even a first few sentences?
•  » » » 6 years ago, # ^ |   +11 Sorry, I miss it! (That sentence must be added just now... XD... ... why I couldn't find it at the first glance?)
•  » » 6 years ago, # ^ | ← Rev. 3 →   +11 I can't see any high rated user to get downvoted (Xellos is an exception). Please remove her downvotes and give me instead.
 » 6 years ago, # |   -15 Is the contest rated?
•  » » 6 years ago, # ^ |   +23 I dont think u r serious
 » 6 years ago, # |   +97 Is it rated?Come on, people. Read the post before asking or you could at least ctrl+f "rated".
•  » » 6 years ago, # ^ |   +33 thank you! ctrl+f really helpful!
 » 6 years ago, # | ← Rev. 2 →   -62 Okaaaay, for once I'll be mainstream...Rated?UPD: And I get downvoted together with the other "mainstream" stupid questions :D
•  » » 6 years ago, # ^ |   +21 This contest is rated G, so you are OK.
•  » » 6 years ago, # ^ |   +36 Don't stop digging! We have to find the joke!
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -21 Or more like "oh look, once again people not reading through this properly / not using common sense".That reminds me: Poe's law.
•  » » » » 6 years ago, # ^ |   +8 Cheers!
•  » » » » 6 years ago, # ^ |   0 Are you sure about this?
•  » » » 6 years ago, # ^ |   +40 Here comes the question: wajueji(excavator) technique which home is strong?
•  » » » » 6 years ago, # ^ |   +32 blue fly~:)
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +29 blue fly in Shandong China!
•  » » » » 6 years ago, # ^ |   +21 There is no doubt that blue fly in China.
•  » » » » 6 years ago, # ^ |   +113
•  » » » » 6 years ago, # ^ |   +3 blue fly blue fly ~
•  » » » » 6 years ago, # ^ |   +9 Find Blue Fly in China Shandong!
•  » » » » 6 years ago, # ^ |   +12 blue fly may blue fly bless us!
•  » » » » 6 years ago, # ^ |   +12
•  » » » » » 6 years ago, # ^ |   0 BLUE??????
•  » » » » 6 years ago, # ^ |   +21
•  » » » » » 6 years ago, # ^ |   0 ~：）
•  » » 6 years ago, # ^ |   0 lol, OMG you are so funny :)
 » 6 years ago, # |   +6 100 people asked about whether the contest is rated, but no one asked the much more important question: How many problems will be in the contest ?
•  » » 6 years ago, # ^ |   0 Who cares how many problems you need to solve as soon as you get (loose?) rating for it? Back to topic, if you look back the introduction topic you will see that it says '6 problems' there.
•  » » 6 years ago, # ^ |   0 Why do you ask ? are you planing to solve all the problems? :D
•  » » » 6 years ago, # ^ |   +19 To make sure I don't miss any problem. My eyesight is slightly weak.
 » 6 years ago, # |   +9 We wish at least a Bayan Contest every month. The More Bayan Contest, the more competitiveness, the more preparation and finally the more chance to win a tshirts, at least in another contest .. :) :p
•  » » 6 years ago, # ^ |   +9 Thank you for the kind words, but Bayan Programming Contest is going to remain an annual event.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 why always top 50 will get t shirt ? I always wonder if there is an announcement that last 10 will also get a t-shit how people will react and are they ready to lose rating only for that :D but I think give some T-shirt to random coder ( like me :p below average level coder to motivate him to do well ) like some TC round ( SRM 600 I remember ) will be more interesting .
•  » » » » 6 years ago, # ^ |   +1 T-Shirts for last 10 is a horrible idea. There will suddenly be some newly registered accounts with pretests passed in problem A and 500 unsuccesful hacks.Random T-Shirts are cool, but that's Bayan's decision afterall.
•  » » » » » 6 years ago, # ^ |   0 Good news then! As mentioned in our first announcement, we are going to have random tshirt winners in our Qualification round which is a 72 hour event and starts from 9 October. More details is available in the announcement.
•  » » » » » » 6 years ago, # ^ |   0 wow thats great :)
•  » » » » » 6 years ago, # ^ | ← Rev. 3 →   -9 then only 30/40 rated account will be eligible for that :D main point is that am i ready to lose 250/300 rating only for a t-shirt :D another interesting idea can be like t-shirt for random place ( pre announce of course ) like t-shirt will go to 255 , 385 , 512 , 1012 placed people . how one will react then :D to get those position may be last minutes unsuccesful hacks :D
•  » » » » 6 years ago, # ^ |   +19 How is giving T-shirts at random supposed to motivate people to do well in a contest? I can see how it helps to increase participation but not participants' effort.
•  » » » » » 6 years ago, # ^ |   +7 And how is not giving t-shirts at random going to motivate many people to (never mind doing well) compete at all? Most don't have a chance of getting into top 50, but they still compete anyway.
•  » » » » » » 6 years ago, # ^ |   +1 This is really true for most participants. To be honest, there's absolutely no way I'll be in top 10 or 20 in a contest with bunch of red/yellow coders.I will be motivated if they choose 10 participants randomly out of, say, top 300, because it's not impossible to make it top 300.
 » 6 years ago, # |   +20 what would happen, if you don't register at contest.bayan.ir?
 » 6 years ago, # |   0 the solution is not public after the contest since the 8.29
 » 6 years ago, # |   0 In case some user do not register for this contest on contest.bayan.ir and his place is in top-50 — his t-shirt will be given to person who ranked #51, or you'll just decrease number of prizes?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +4 We believe this would not happen, but in such case, we will save that tshirt.There has been more than 7000 registered users at contest.bayan.ir right now.
•  » » » 6 years ago, # ^ |   +8 I do not found address in the profile. How do you send us the t-shirt?
 » 6 years ago, # |   -31 Will it be rated for Div 2 too?
•  » » 6 years ago, # ^ |   +1 Of course.
 » 6 years ago, # | ← Rev. 2 →   +9 Please consider shifting the round by 30 minutes to 1330 UTC. There is another contest running on hackerrank.com from 1030 to 1330 UTC. It is the main elimination round of a special codesprint organised for the indian students and most of us will miss this contest as a result. This is the link for the hackerrank codesprint: https://www.hackerrank.com/csindia14-er2
•  » » 6 years ago, # ^ |   0 It is a both Div 1 + 2 contest, so half hour would affect a lot in ratings. In normal contest, half hour would not have that adverse affect.
•  » » » 6 years ago, # ^ |   0 Aren't u doing the codesprint today?
•  » » » » 6 years ago, # ^ |   0 Yes, I am doing. I won't do codeforces today. I had done it if it would have been a 2 Div 1 only round.
 » 6 years ago, # |   0 Scoring system?
•  » » 6 years ago, # ^ |   +1 According to email with announcement, it will be round with standard CF rules and 500-1000-1500-2000-2500-2500 scoring distribution.
•  » » » 6 years ago, # ^ |   0 Why I didn't receive the email? anyone else didn't receive it too ?
•  » » » » 6 years ago, # ^ |   +15 Here is the email content. We will also update the post.Attention 1: The round starts on Sunday, October, 5, 2014 13:00 (UTC).Attention 2: The qualification round will be held on 9-11 October for 72 hours on http://contest.bayan.ir/en/.Attention 3: Top 50 will win tshirts.Hello, **** . Welcome to Bayan Programming Contest 2015 – Warm Up Round.We are glad to invite you to take part in Bayan 2015 Contest Warm Up (Div. 1 and Div. 2). It starts on Sunday, October, 5, 2014 13:00 (UTC). The contest duration is 3 hours for 6 problems. The allowed programming languages are C/C++, Pascal, Java, C#, Python, Ruby, PHP, Haskell, Scala, OCaml, Go, D and JavaScript.The round writers are mruxim, mR.ilchi and havaliza. Do not miss the round!Bayan 2015 Contest Warm Up (Div. 1 and Div. 2) will be held on Codeforces using regular Codeforces rules and it will be rated for both Div1 and Div2. The scoring will be: 500 – 1000 – 1500 – 2000 – 2500 – 2500. The round will be held on the rules of Codeforces, so read the rules (here and here) beforehand.The round will be for newcomers and participants from the both divisions. Want to compete? Do not forget to register for the contest and check your handle on the registrants page. The registration will be closed 5 minutes before the contest.Although this is a warm up round but top 50 will win tshirts. BTW, there will be another 100 tshirts for the official rounds which will be held on Bayan Contest platform (contest.bayan.ir)IMPORTANT: Make sure you have registered on contest.bayan.ir/en before the warm up round.If you want the breaking news, updates and rankings as fast as possible you can follow us @bayan on twitter now.We would like to thank MikeMirzayanov and Codeforces team for this great platform and this talented community.If you have any questions, please feel free to ask us on codeforces.com/bayan2015.Wish you high ratings and lots of geek tshirts!Bayan Team
 » 6 years ago, # |   +2 what about the difficulty of problems?
 » 6 years ago, # | ← Rev. 2 →   +16 Hey, I was trying to change e-mail of Bayan account for 2 hours. Finally I have no idea. Can you give me a hint?
•  » » 6 years ago, # ^ |   +3 We have disabled email change for good reasons. We are also logging the country change.
 » 6 years ago, # |   +5 Have not found the reason to register before contest, there is no connection to CF accounts. Is the registration for those who want to win t-shirts? So, I havn't any hope, but there was no place in profile to put t-shirt size.
•  » » 6 years ago, # ^ |   0 there are two profiles: on bayan.ir and contest.bayan.ir and the latter has place for t-shirt size.
•  » » » 6 years ago, # ^ |   0 Thanks. Now I've understood.
 » 6 years ago, # |   +2 how to solve C ???
•  » » 6 years ago, # ^ |   +9 Hi.I think I solved C.This is how I done: first, you remove the -1 case.For that you can see if you have 2 conex components or you can look at he 2x2 squares.After this you take the first X, Y where you have matrix[X][Y]=='X', you look how far can you go from that position down and right and you will obtain l1 and l2.Now either, l1 is the high of the brush, wither l2 is the length.You fix which of afirmation is true and, than you can compute pretty easy the other(you know the number of columns of the brush and compute the number of rows).You make sure that it works and that's all.Take care at the second case which is a particualr one because you have just a simple ractangle, and in that case you have min(n, m) where n and m are the lengths of the rectangle.
•  » » » 6 years ago, # ^ |   +3 I found this approach ... i got WA on pretest #5. Thank you for responding :)
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Maybe you forgot one of the cases with -1.It is possible, at the end of the algorithm, that you don't find any solution. Here is a test which may fail on your solution, I think 7 5 XXX.. XXX.. XXXX. ..XX. ..XXX ..XXX ..XXX
•  » » 6 years ago, # ^ | ← Rev. 2 →   +6 I'm not sure if this was the intended solution, but here was my approach:Let S be the leftmost 'X' cell in the first row containing an 'X', and let E be the rightmost 'X' cell in the last row containing an 'X'.First, fix a width w. We'll call a length l valid if we can start the top left of our brush at S and make a sequence of moves such that the bottom right of our brush ends up at E without our brush ever visiting a '.' cell.The important observation here is that once the width is fixed, the sequence of moves in a valid sequence does not depend on l. If there is a 'X' to the right of the top row of our brush, we must move right. Otherwise, we move down.What this means is that for all valid lengths, the number of squares we visit is decreasing as length decreases. And all invalid lengths are greater than valid lengths. So we can binary search for the first valid length that visits all 'X'-ed squares.The runtime is N (all widths) * log N (lengths) * 2*N (simluation).An implementation: http://codeforces.com/contest/475/submission/8099559
 » 6 years ago, # |   +49 8087526 — problem A, "why should I write code if there are only 35 answer cases?" :D
•  » » 6 years ago, # ^ |   +7 i think writing the code was faster and easier ;)
•  » » 6 years ago, # ^ |   +28 To not waste time
•  » » 6 years ago, # ^ | ← Rev. 2 →   +9
 » 6 years ago, # |   +16 some people solved B with targan algorithm and some other people solved it with floyd warshall XD :D come on guys! take it easy!! :D
•  » » 6 years ago, # ^ |   +10 Even dfs was overkill for B .
•  » » » 6 years ago, # ^ |   0 And what is better than dfs for B?
•  » » » » 6 years ago, # ^ |   +5
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +3 can you please explain what he has done ?
•  » » » » » » 6 years ago, # ^ |   0 You only stuck on corners, then if and only if there is any corner that has two incoming ways(thus no outgoing), moving from that point to other intersections will be impossible.
 » 6 years ago, # |   +26 How is E solved for a tree?
•  » » 6 years ago, # ^ | ← Rev. 2 →   -8 I assumed that for optimal solution the following statement will be true for at least one node (let's call it Root): "Every other node can reach the Root or can be reached from the Root". Then make a rooted tree from every node and you need to decide for each child whether it's direction should be from the root or to the root. The result in the children subtrees doesn't depend on the direction you choose. Now let's say you've chosen the direction in such a way that X1 nodes can reach the root (in other words they are directed to the root) and X2 nodes will be reachable from the root. Then in this case you will add to the result the number of pairs equal to: P = (X1 + size[root]) * X2 + X1 * size[root] So I calculated the weights of the each child subtree and then was checking which sums for X1 and X2 we can achieve (in a way similar to knapsack). For each achievable sum I was checking the formulae above. This has passed the pretests.
•  » » » 6 years ago, # ^ |   0 I've found this approach... But how could we do the "similar to knapsack" part? I couldn't make that knapsack faster than O(N3) :(
•  » » » » 6 years ago, # ^ |   0 The knapsack on it's own will be O(MaxSum·Nsum) so given that you put it into a loop over all vertices it might seem to be O(N3) but it won't be that bad. The reason is that your Nsum is basically a number of children of some given node but if you sum all these values across all roots it won't be N2, it will be 2M = 2(N - 1). So it's O(N2) in total.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Didn't you assumed for every vertex, every node in it's subtree can reach it or can be reached from it? In this line from your code : int rem = full_sum - x; It's amazing! Why it's always true?!
•  » » » » » » 6 years ago, # ^ |   +8 Well, yeah, in order to calculate the answer the assumption should be like you stated it. But in order to prove that overall this strategy will give you the optimal result you need to use my original assumption :-) In this line x — a number of nodes from which you can reach the root. By our assumption for this particular root every node will be either reachable from it or you will be able to reach the root from it. So, given that fullsum is a number off all nodes in the tree except for the root, then it's clear that number of nodes reachable from the root will be like that.
•  » » » » » » » 6 years ago, # ^ |   0 Thank for clear explanation! I didn't found that assumption... I was trying to use convex hull optimization to make it faster! You saved me! :P
 » 6 years ago, # | ← Rev. 2 →   +14 what do you feel when you lock any problem then you discover it will fail ?
•  » » 6 years ago, # ^ |   +71
•  » » » 6 years ago, # ^ |   -6 i voted down by mistake :(
•  » » » » 6 years ago, # ^ |   0 Still got 4 upvotes, so no biggie :P
 » 6 years ago, # |   -78 Contest like a sh.t
 » 6 years ago, # |   0 What is idea of solving of Problem C? I tried to figure out height and width of brush by defining the most left and top part of paint, then move it right or down one cell per time. Is it right idea?
•  » » 6 years ago, # ^ |   0 Hi, please see my comment: http://codeforces.com/blog/entry/14077#comment-190921. Let me know if anything is unclear.
 » 6 years ago, # | ← Rev. 2 →   +5 After getting RE, I got WA. After getting WA, I got TLE.Problem D hates me :((P/s: I think the time limit is a bit strict
•  » » 6 years ago, # ^ | ← Rev. 2 →   +9 I got Pretests passed with less than 0.3 seconds, and I've got an algorithm...
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +3 Does not your solution rely on the number of prime divisors of the numbers from the array?
•  » » » » 6 years ago, # ^ |   +24 No. Starting from any fixed L, gcd(A[L..R]) over all R can only have distinct values.
•  » » » » » 6 years ago, # ^ |   0 But how to prove it?
•  » » » » » » 6 years ago, # ^ | ← Rev. 3 →   +4 gcd(A[L..R]) = gcd(A[L..R + 1]) gcd(A[L..R]) ≠ gcd(A[L..R + 1]) = gcd(gcd(A[L..R]), A[R + 1]) = d, d | gcd(A[L..R]) =  > d * 2 ≤ gcd(A[L..R])
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Thanks!
•  » » » » 6 years ago, # ^ |   +10 No. I only use an O(Nlog^2N*(GCD complexity)) algorithm. But it stucks on pretest 11 :((
•  » » » » » 6 years ago, # ^ | ← Rev. 4 →   0 I believe that the GCDs amortize out, so that overall complexity is still O(nlognlog(maxA)). This is because you should you should have O(n) values in total and each of them will only go through log(maxA) GCD steps in total over the course of running. Also I believe that you can get O(nlog(maxA)) overall but it really shouldn't be necessary.
 » 6 years ago, # |   0 How to solve D :(
•  » » 6 years ago, # ^ | ← Rev. 2 →   +31 You always hope for math! why are you sad?anyway I'll give a hint: note that all intervals that start with the same index have at most O(log n) different values for GCD and they are sorted in non-increasing order.
 » 6 years ago, # |   +17 A was fun LOL
 » 6 years ago, # |   0 This is my solution of E (I can't decide if it's correct from the samples, but intuition tells me it is): all 2-connected components can be made into SCC; we're left with a weighted tree (vertex = SCC, weight = number of vertices in it) which we want to direct consider a star with weights W[i] of sons of the central vertex c; we can see that if subset S of these sons has edges from them directed in the central vertex, then the answer is , which is maximum for as close to as possible therefore, I guess that the optimal solution for a general tree is to make c the centroid, direct all subtrees towards it or away from it and decide on the subset of subtrees to be directed away from it so that the sum of weights of all vertices in them would be as close to as possible, which is O(N2) knapsack
•  » » 6 years ago, # ^ |   0 Yeah, while I didn't actually compete I did come up with that exact same solution. Seems pretty legit. Looking at any subtree, anything else you do in that subtree is only going to decrease the total number of connections from nodes in that subtree.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Yeah, written the same thing, the system testing will show whether this centroid idea is correct, seems natural but I have no clue how to prove it. Success! :-)
 » 6 years ago, # | ← Rev. 2 →   +30 Why did Dreamoon screw up his/her contest ?
•  » » 6 years ago, # ^ |   +5 bieng angry for not solving A ! :D
•  » » 6 years ago, # ^ |   +21 Testing how hard it is to be like worse
 » 6 years ago, # |   +3 Seems like a lot of people got WA on problem C at #5 test.
 » 6 years ago, # |   +5 Post Updated.
 » 6 years ago, # |   0 For some reason no-one has asked, so... how to solve F ??
•  » » 6 years ago, # ^ |   +1 I didn't ask because I didn't understand it
•  » » » 6 years ago, # ^ |   0 Statement was really bad. I understood after asking a question during the contest. The problem is that you can split a grid into two parts by removing rows or columns with zero planets. Do this until you cannot make further moves. The number of remaining subgrids is your answer.
 » 6 years ago, # |   0 E can be done in O(n3 / 2 + m) if we group numbers of the same value (8096244) and in O(nlog2 + m) if we solve this knapsack by some FFT on base intervals (like binary tree somehow)
 » 6 years ago, # |   0 Strange contest! Many strong people failed on easy problems such as A!
•  » » 6 years ago, # ^ |   -11
•  » » 6 years ago, # ^ |   +5 Yes... Look at dreamoon here..
•  » » » 6 years ago, # ^ |   +4 I think dreamoon just wants to break worse's record :D :P
•  » » 6 years ago, # ^ |   0 and see this code
•  » » » 6 years ago, # ^ |   +3
•  » » » » 6 years ago, # ^ |   0 and see this
•  » » » 6 years ago, # ^ |   +5 Was that automatically generated ; D?
•  » » » » 6 years ago, # ^ |   0 From this comment, I'd guess the language of the code to be Perl :D
 » 6 years ago, # |   +9 Why i cant practise the tasks?
 » 6 years ago, # | ← Rev. 2 →   +26 E is similar to http://main.edu.pl/en/archive/oi/20/pol...
•  » » 6 years ago, # ^ |   0 Exactly, it is. I copy-pasted my old code from this problem and thank to that I got E accepted :P. But I'm from Poland, so that is not that weird that I knew that problem. But why do you know that? Do you consider Polish problems as really nice ones :)? Or have you simply done half of the problems in the world :P?
•  » » » 6 years ago, # ^ |   +55 Polish problems are like The Simpsons. For any nice problem there is similar Polish problem as well as for any nice film there is The Simpsons episode with similar plot.
•  » » » 6 years ago, # ^ |   +16 I think many Chinese competitors are familiar with Polish problems like POI, PA and ONTAK. Many people translated these problem to Chinese voluntarily, even from Polish, and shared them with us. And some problems from PA are extremely hard, and interesting in my mind. I enjoy these Polish problems.
•  » » 6 years ago, # ^ |   +29 And D is similar to CERC 2013 Magical GCD. F shares the same idea with SGU 550. :P
 » 6 years ago, # |   -14 One of my friends says it will be unrated. Is it true?
•  » » 6 years ago, # ^ |   +3 Hum, has anything changed? According to the post this contest is supposed to be rated.
•  » » 6 years ago, # ^ |   +106 I can hear sadness and despair in your question:)
•  » » 6 years ago, # ^ |   +6 I sure hope not :(
 » 6 years ago, # |   0 Is there a tutorial for this round that is going to be published ??
 » 6 years ago, # |   +8 May I submit solution after the contest?
•  » » 6 years ago, # ^ |   0 Yes, of course
 » 6 years ago, # |   +8 Hello BYN, I have completed my profile on contest.bayan.ir before the warm-up round, but I did choose the size of the t-shirt is Large, could I change it to Medium now? I taking place 50 in this round, that's really close :P Btw, thanks for the greate contest
•  » » 6 years ago, # ^ |   -8 can U give me your T.shirt :D
 » 6 years ago, # |   -37 Is the contest rated? WA on problem A :( It is the worst contest that I ever seen...
•  » » 6 years ago, # ^ |   +10 Of course it's rated. And why is it the worst contest ever? All problems except A were very good. A was just a tricky simulation problem.
•  » » » 6 years ago, # ^ |   -7 I only said my opinion. Maybe it's because I get WA on problem A.
•  » » 6 years ago, # ^ |   +21 A was a problem where you copy-pasted the picture into your code and did two trivial for-loops.
•  » » » 6 years ago, # ^ |   0 So ?
•  » » » » 6 years ago, # ^ |   +10 So the contest isn't at fault — the user is.
•  » » » » » 6 years ago, # ^ |   +1 OK. I think I'm so sad when I'm writing this comment :D
•  » » » 6 years ago, # ^ |   +11 Or as many did, not copy-paste some string and do non-trivial detail-oriented programming xD.
•  » » » » 6 years ago, # ^ |   0 Thus making it so much hackable :)
 » 6 years ago, # |   +49 When are the ratings going to be updated?
•  » » 6 years ago, # ^ |   +42 Best rating graph I've ever seen! 5 different colors in 5 rounds.
•  » » » 6 years ago, # ^ |   +6 Unreal.. geniucos should teach us all
 » 6 years ago, # |   +1 Why does this get TLE? http://codeforces.com/contest/475/submission/8089790
•  » » 6 years ago, # ^ |   0 Maybe you have an infinite loop.
•  » » » 6 years ago, # ^ |   0 I tried this on my pc. It gets executed in 42s :O. But I don't know why!
•  » » » » 6 years ago, # ^ |   0 The problem is that you have to mark visited once you push it in the queue.Like if I can go there and visited[there] == 0: queue.push(there), visited[there]=1
•  » » » » » 6 years ago, # ^ |   0 ohh shit.. yes! such a silly mistake..
 » 6 years ago, # |   +27 So no one that solved E actually proved that their solution is correct? This makes me kind of sad :(
•  » » 6 years ago, # ^ |   +6 Well, it doesn't matter that much whether we have a proof or not, the question is whether problem setters had it :-)
 » 6 years ago, # |   +10 Some of the submissions are totally the same (several solutions for task C), i think it is better to deal with this problem. :)
 » 6 years ago, # | ← Rev. 2 →   0 Can anyone tell what is the worst case time complexity of my solution for F?8097771First, I sort points by Y and I split into meta-universes in basis of Y coordinate.Then, for each galaxy, I sort by X now and then again find meta-universes. Then for each new galaxy, I repeat this process. (alternate sorting by X and Y)Or what is a case which would make this fail? (can't see cases fully on CF)
•  » » 6 years ago, # ^ |   +1 I think it is N^2...I made the same solution.It is even N^2logN but when you split, logN bacomes very small.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 Well, the counter-test for that code seems to be a list of universes where in order to split the meta-universe you need to remove the last (by X or by Y) universe from it. Then every time you will sort and scan the entire sequence only in order to remove one element. O(N2·logN)
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I think this case will take O(N^2) time.O..O..O..O..O...Where 'O' is a planet.
•  » » » 6 years ago, # ^ |   0 This test case takes O(2NlogN) time.We are done after the first time search() is run.
 » 6 years ago, # |   0 I think I'm going to be green from blue. But it is not so important :D
 » 6 years ago, # |   +5 Finally I'm a Candidate Master :D
•  » » 6 years ago, # ^ |   0 Congratulations :D
•  » » 6 years ago, # ^ |   0 Me too :D Finally :D
•  » » 6 years ago, # ^ |   0 Congratulations. :)
 » 6 years ago, # | ← Rev. 3 →   +22 Tfw I'm one of the few that get a t-shirt (finally on a CF-hosted contest, too):(sauce: Sandra and Woo webcomic )
•  » » 6 years ago, # ^ |   +45 And we're waiting for the random T-shirts ....
 » 6 years ago, # |   0 I have a question — I solved B by BFS from each point and passed pre-tests, but after system testing I have got TL#45. Then I rewrite my solution with using of DFS — I have got AC — so, why BFS is slower then DFS? I am writing in C++, for BFS I use STL queue?
•  » » 6 years ago, # ^ | ← Rev. 3 →   +4 You mark vertex as visited when you look at edges coming from it (right way is to do it when you add it in queue). I am pretty sure that it leads to exponential complexity. AC : 8098146.Upd. Yes, it leads to exponential complexity. Imagine such graph: 1 -> 2 1 -> 3 2 -> 4 3 -> 4 4 -> 5 4 -> 6 5 -> 7 6 -> 7 ... 3n + 1 -> 3n + 2 3n + 1 -> 3n + 3 3n + 2 -> 3n + 4 3n + 3 -> 3n + 4 You add vertex 1 to queue, then vertexes 2 and 3, then add 4 two times. So, you add 5 and 6 two times each, than add 7 four times and so on. Of course, exact this type of graph is impossible in problem's conditions, but I think you get it.Was glad to help.
•  » » » 6 years ago, # ^ |   0 Yes, I have already found this bug( I'm so silly(
•  » » 6 years ago, # ^ |   0 In BFS, you have to mark the node after pushing it to queue, not after popping! That's the reason of your TLE.
 » 6 years ago, # |   +7 5 lucky randomly selected tshirt winners announced.
•  » » 6 years ago, # ^ |   -6 I like your T-shirt!!!:D
 » 6 years ago, # |   +14 When is the tutorial for this round going to be published?
 » 6 years ago, # |   0 Why does this solution passes? Oo 8087726
•  » » 6 years ago, # ^ | ← Rev. 3 →   +27 Because it's correct? :)Imagine the string is neither ok1 nor ok2. Then the graph is clearly not strongly connected because you won't be able to get out from one of the corners.Now suppose the string is ok1 or ok2. Suppose you want to go from A to B. First use whatever road you're on to go to the border, then rotate along the border until you're on the start of B's horizontal road and take it. This proves that all intersections are reachable from all other intersections.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Thanks ffao ! I was also wondered why my code got accepted :p even i wrote that in this blog before seeing your post :p here is that comment . I understood it from your explanation . thanks again ! :)
 » 6 years ago, # |   0 Can som1 plz xplain d soln for problem D?
•  » » 6 years ago, # ^ |   0 Hint: this comment. You can also read my solution, it's pretty simple (a table of gcds of intervals of length 2k and binsearch on them).
•  » » » 6 years ago, # ^ |   0 I tried understanding your solution. I don't get the logic of the 2 while loops. Can you explain the binsearch part.
 » 6 years ago, # |   +2 is there an editorial BYN ???!!!???
•  » » 6 years ago, # ^ |   +3 I'm afraid not in these days. We are so busy preparing our qualification and elimination round.
•  » » » 6 years ago, # ^ |   0 please , prepare one after final round
•  » » 6 years ago, # ^ |   0
•  » » » 6 years ago, # ^ |   0 Thanks very much :)
 » 6 years ago, # |   +12 Hello! I have found cheater again! Read it!
•  » » 6 years ago, # ^ |   0 Thank you.I really cannot understand why they cheat! Well, I think that Codeforces is a place to test myself and improve my programming skills; I absolutely want to know how they think or what they think Codeforces is!
 » 6 years ago, # |   0 Hey can you take tutorial ?
•  » » 6 years ago, # ^ |   +18 If you give it, I'll take it!
 » 6 years ago, # | ← Rev. 3 →   +54 Wow, unexpected excellent result for me. I rarely appeared in the top of the scoreboard(8th place once in CF & 8th place once in SRM), so it's first time to see my handle on the announce post :)Well, the next aim is to get the first place, I wonder(of course I know it's far more difficult)
•  » » 6 years ago, # ^ |   +22 Same here, I didn't even think I would be able to win a t-shirt :)
 » 6 years ago, # | ← Rev. 3 →   0 Here is my solution for Prob F, but it got WA at test 8, and I haven't found mistake. I use D&C and binary search. The complexity is O(nlogn) http://codeforces.com/contest/475/submission/8100455
•  » » 6 years ago, # ^ |   0 I found my mistake and make my code more clean, and then got TLE at test 22. The time complexity isn't O(nlogn) ? http://codeforces.com/contest/475/submission/8101816
 » 6 years ago, # |   +4 This contest seems a little hard to me, I have to train my coding level.
 » 6 years ago, # |   0 For Problem D, I found a hint in a previous comment, "all intervals that start with the same index have at most O(log n) different values". I have checked it writing some integers on paper, this is absolutely true statement. But can anyone please prove this statement or explain elaborately how to solve problem D.Thanks in advance.
•  » » 6 years ago, # ^ |   +5 gcd(x,y) > gcd(x,y+1);gcd(x,y) = gcd(x,y+1)*k; {k > 1}this situation can repeat at most log(10^9). Because k's minimum value is 2.
•  » » 6 years ago, # ^ | ← Rev. 5 →   +7 Let our sequence be a1, a2, ..., an. Let us fix left end of substring (l). We have: gl = gcd(al) = al, gl + 1 = gcd(al, al + 1), ..., gr = gcd(al, al + 1, ..., ar). We can see that gx is divisible by gx + 1 for all . Why? Well, gx is greatest common divisor of al, ..., ax, so all other al, ..., ax common divisors, including gx + 1 are divisors of gx.So gx + 1 is divisor of gx. There are two cases: 1) gx + 1 = gx. So they are equal, and gx + 1 adds nothing to amount of different values. 2) gx + 1·k = gx for some k ≥ 2 and . So . This way gx + 1 is at least two times smaller than gx. So, every time new distinct value appears in row, it is at least two times less than previous distinct value. It means there are not more than of them.
•  » » » 6 years ago, # ^ |   0 Thanks for your very nice explanation. Learning new thing is a gift to me. :)
•  » » » 6 years ago, # ^ |   0 cool, this is great explanation, thanks.
 » 6 years ago, # | ← Rev. 2 →   0 My solution to Problem 475B - Strongly Connected City is here -> 8101961 . I got it accepted but I seriously doubt if it is wrong . I'm doubting because I've seen almost 20 codes and no one solved this in this way . Everyone implemented BFS or DFS or some other graph algorithms. Will you please have a look mruxim,mR.ilchi & havaliza ?? Where is the tutorial ???
•  » » 6 years ago, # ^ |   0 I think, there is no doubt of this solution. Many of the coders have solved this problem with almost same code as you. When you will search STATUS according to SOLUTION SIZE, then you will find many of solutions resembles with your code,You can find here
•  » » 6 years ago, # ^ |   0 Since the grid is too small(20*20), so I think ,using DFS needs a little thinking and some code like you, needs more thinking.And when running contest , this is an important issue.
•  » » » 6 years ago, # ^ |   0 I actually think the same way, Although the solution can be written in a very faster manner, I did the DFS because it was OK for a 20x20 board and I was thinking about DFS as I was reading the statement.For me, finding a better solution might have taken much longer than coding a DFS function.
•  » » 6 years ago, # ^ |   +6 Here is an explanation for such short solution:If outer streets (top, bottom, rightmost and leftmost) form a cycle (clockwise or counter-clockwise), then by following that cycle, one can reach any junction on that cycle from any other junction on the same cycle. moreover, independent of the directions of inner streets you can also reach all "inner" junctions from any "outer" junction. Therefore, if the outer streets form a cycle, then the answer is "YES". If outer streets do not form a cycle, then there is at least one "corner" junction, for which both horizontal and vertical streets have directions towards that junction (otherwise, there it would be a cycle). Since one can not move out from such "corner" junction to anywhere else, the answer is "NO".
•  » » » 4 years ago, # ^ |   0 Hi, could you elaborate a bit more on how you can reach any inner junctions from the outer perimeter? I don't understand.
•  » » » » 3 years ago, # ^ |   -10 Suppose you want to go from point A to B. first go from A to outer cycle. Now follow that cycle until you get a point which lies on the line on which point B lies and points towards the direction of point B. So just follow that line and reach B.
 » 6 years ago, # | ← Rev. 2 →   +16 why the title of problem D is CGCDSSQ ??!:D
•  » » 6 years ago, # ^ |   +13 Count GCD SubSeQuences?
 » 6 years ago, # |   -17 why there is not a low rated participant in the randomly t-shirt winners list?
•  » » 6 years ago, # ^ |   0 3 purple :>
•  » » 6 years ago, # ^ |   0 Because it was chosen between participants who got 50-550th place, so high rated participants are more frequent than low rated participants in these places, so its normal
•  » » » 6 years ago, # ^ |   0 Thanks for answering
 » 6 years ago, # |   0 Could someone please tell me when the tutorial for this round is going to be published?
•  » » 6 years ago, # ^ |   0 Today or tomorrow.
•  » » 6 years ago, # ^ |   0
•  » » » 6 years ago, # ^ |   0 Thank you very much :)