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.
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!
Do you translate problems ?
no... I solve them(2 or 3 of them actually xD)
First long contest descriptions, now t-shirts. :)
What's wrong with that?..
The more the better, I always say!
Yes, hope for math!!
Should my id on Bayan be same to my Codeforces id?
No.
How to solve "Lake" from shortcut round?
А Всесиб?
Между всесибом и раундом целых два часа.
Will the warm up round be a rated event on CodeForces?
"and it is going to be rated for both divisions"
Yeah, The warm up round will be a rated event on codeforces.
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)?
No. But later you would be asked to submit your Codeforces Handel in your Bayan profile.
Oh, no problem, my Codeforces handle is tourist.
So you should also be asked to submit your Codeforces password. If the Bayan admin can log in to your account, what you say is true
wow, so secure.
obviously no CF passwords are needed!
"Oh, no problem, my Codeforces handle is tourist."
So you should be able to receive our privet message on your codeforces panel!
И вам привет!
I think you shouldn't put exclamation mark there because it sounds like you're shouting. It's just a joke, keep calm :D
Does the contest use Codeforces rules or ACM-ICPC rules or something else?
Usually warm-ups use ordinary Codeforces rules, if I'm not mistaken.
The rules will be announced in the contest's email which you are going to receive day before the contest.
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
WTF? Sunday is an unlucky time for round. Normal people like me will get rest at that time.
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).
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...
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!
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 ヽ༼ຈل͜ຈ༽ﾉ
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.
Yes, I focused on the 1PM and not on the weekday... and that your next reply contained "time zone" didn't help either :D
In 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
Don't try to find normal people among competitive programmers
you are a con and you are proud about it? it's nothing to add.
Can a Programmer be a normal person? :)
Rated?
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?
Sorry, I miss it! (That sentence must be added just now... XD... ... why I couldn't find it at the first glance?)
I can't see any high rated user to get downvoted (Xellos is an exception). Please remove her downvotes and give me instead.
Is the contest rated?
I dont think u r serious
Is it rated?
Come on, people. Read the post before asking or you could at least
ctrl+f"rated".thank you!
ctrl+freally helpful!Okaaaay, for once I'll be mainstream...
Rated?
UPD: And I get downvoted together with the other "mainstream" stupid questions :D
This contest is rated G, so you are OK.
Don't stop digging! We have to find the joke!
Or more like "oh look, once again people not reading through this properly / not using common sense".
That reminds me: Poe's law.
Cheers!
Are you sure about this?
Here comes the question: wajueji(excavator) technique which home is strong?
blue fly~:)
blue fly in Shandong China!
There is no doubt that blue fly in China.
blue fly blue fly ~
Find Blue Fly in China Shandong!
blue fly may blue fly bless us!
Keep The Blue Flag Flying High!
BLUE??????
~：）
lol, OMG you are so funny :)
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 ?
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.
Why do you ask ? are you planing to solve all the problems? :D
To make sure I don't miss any problem. My eyesight is slightly weak.
А будет перевод задач на русский?
Всегда был, с чего бы ему и сейчас не быть?
К слову про "всегда" — Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements). Там правда четко в названии указано, что перевода не ждать.
После вырвиглазных условий на русском всесибирской олимпиады имени Поттосина переводить нормальные задачи в гугл переводчике будет не так уж и плохо.
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
Thank you for the kind words, but Bayan Programming Contest is going to remain an annual event.
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 .
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.
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.
wow thats great :)
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
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.
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.
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.
what would happen, if you don't register at contest.bayan.ir?
the solution is not public after the contest since the 8.29
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?
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.
I do not found address in the profile. How do you send us the t-shirt?
Will it be rated for Div 2 too?
Of course.
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
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.
Aren't u doing the codesprint today?
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.
Scoring system?
According to email with announcement, it will be round with standard CF rules and 500-1000-1500-2000-2500-2500 scoring distribution.
Why I didn't receive the email? anyone else didn't receive it too ?
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
what about the difficulty of problems?
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?
We have disabled email change for good reasons. We are also logging the country change.
Надеюсь не слить опять :)
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.
there are two profiles: on bayan.ir and contest.bayan.ir and the latter has place for t-shirt size.
Thanks. Now I've understood.
Походу перевода не будет... Да прибудет со мной гугл переводчик!
Ювелирно, 4700. :)
Как решать D?
how to solve C ???
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.
I found this approach ... i got WA on pretest #5. Thank you for responding :)
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
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.me/contest/475/submission/8099559
8087526 — problem A, "why should I write code if there are only 35 answer cases?" :D
i think writing the code was faster and easier ;)
To not waste time
There are also those who forgot 0... most hacks were probably 0.
Каким тестом можно свалить решение задачи C за N^3?
Решение:
переберем за N^2 высоту и ширину кисти.
от левой верхней точки за O(N) пройдем dfs'ом по закрашеным точкам
если есть два варианта: пойти вниз или вправо, говорим, что закрасить такой кистью нельзя
при переходе вниз или вправо прибавляем к счетчику закрашенных точек ширину или высоту соответственно
если некуда идти — смотрим, все ли точки мы закрасили dfs'ом
перебрать можно только одну сторону, т.к. первый ход был либо вправо либо вниз, то другая стороня фиксирована.
Никаким. Это N^2. Для почти всех конфигурации невозможно будет делать даже первый ход.
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
Even dfs was overkill for B .
And what is better than dfs for B?
This
can you please explain what he has done ?
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.
Есть ачивмент "закончить писать код по задаче через 5 секунд после конца раунда"! Кстати, там Nozim в личке решения спрашивал. Вот не прочел бы его сообщение — как раз хватило бы.
How is E solved for a tree?
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.
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) :(
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.
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?!
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.
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
what do you feel when you lock any problem then you discover it will fail ?
i voted down by mistake :(
Still got 4 upvotes, so no biggie :P
Contest like a sh.t
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?
Hi, please see my comment: http://codeforces.me/blog/entry/14077#comment-190921. Let me know if anything is unclear.
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
I got Pretests passed with less than 0.3 seconds, and I've got an
algorithm...
Does not your solution rely on the number of prime divisors of the numbers from the array?
No. Starting from any fixed L, gcd(A[L..R]) over all R can only have
distinct values.
But how to prove it?
d | gcd(A[L..R]) = > d * 2 ≤ gcd(A[L..R])
Thanks!
No. I only use an O(Nlog^2N*(GCD complexity)) algorithm. But it stucks on pretest 11 :((
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.
How to solve D :(
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.
A was fun LOL
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
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.
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! :-)
Why did dreamoon_love_AA screw up his/her contest ?
bieng angry for not solving A ! :D
Testing how hard it is to be like worse
Seems like a lot of people got WA on problem C at #5 test.
Post Updated.
Бедный izban, чуть первым не стал.
For some reason no-one has asked, so... how to solve F ??
I didn't ask because I didn't understand it
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.
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)
Strange contest! Many strong people failed on easy problems such as A!
Damon
Yes... Look at dreamoon_love_AA here..
I think dreamoon_love_AA just wants to break worse's record :D :P
and see this code
and see this
Was that automatically generated ; D?
From this comment, I'd guess the language of the code to be Perl :D
Why i cant practise the tasks?
E is similar to http://main.edu.pl/en/archive/oi/20/pol...
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?
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.
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.
And D is similar to CERC 2013 Magical GCD. F shares the same idea with SGU 550. :P
Дорешивание будет?
One of my friends says it will be unrated. Is it true?
Hum, has anything changed? According to the post this contest is supposed to be rated.
I can hear sadness and despair in your question:)
I sure hope not :(
D — баян-бабаян. Идея решения один в один совпадает с оной у задачи C с CERC 2013.
Is there a tutorial for this round that is going to be published ??
May I submit solution after the contest?
Yes, of course
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
can U give me your T.shirt :D
За 3 секунды до конца написал D, но не успел нажать "Отослать", а на дорешивании она зашла(
Is the contest rated? WA on problem A :(
It is the worst contest that I ever seen...
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.
I only said my opinion. Maybe it's because I get WA on problem A.
A was a problem where you copy-pasted the picture into your code and did two trivial for-loops.
So ?
So the contest isn't at fault — the user is.
OK. I think I'm so sad when I'm writing this comment :D
Or as many did, not copy-paste some string and do non-trivial detail-oriented programming xD.
Thus making it so much hackable :)
When are the ratings going to be updated?
Best rating graph I've ever seen! 5 different colors in 5 rounds.
Unreal.. geniucos should teach us all
Why does this get TLE? http://codeforces.me/contest/475/submission/8089790
Maybe you have an infinite loop.
I tried this on my pc. It gets executed in 42s :O. But I don't know why!
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
ohh shit.. yes! such a silly mistake..
So no one that solved E actually proved that their solution is correct? This makes me kind of sad :(
Well, it doesn't matter that much whether we have a proof or not, the question is whether problem setters had it :-)
Some of the submissions are totally the same (several solutions for task C), i think it is better to deal with this problem. :)
Can anyone tell what is the worst case time complexity of my solution for F?
8097771
First, 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)
I think it is N^2...I made the same solution.It is even N^2logN but when you split, logN bacomes very small.
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)
I think this case will take O(N^2) time.
O..O..O..O..O...
Where 'O' is a planet.
This test case takes O(2NlogN) time.
We are done after the first time search() is run.
I think I'm going to be green from blue. But it is not so important :D
Finally I'm a Candidate Master :D
Congratulations :D
Me too :D Finally :D
Tfw I'm one of the few that get a t-shirt (finally on a CF-hosted contest, too):
(sauce: Sandra and Woo webcomic )
And we're waiting for the random T-shirts ....
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?
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:
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.
Yes, I have already found this bug( I'm so silly(
In BFS, you have to mark the node after pushing it to queue, not after popping! That's the reason of your TLE.
Классно
5 lucky randomly selected tshirt winners announced.
I like your T-shirt!!!:D
Правильного человека в топ10 добавили
Оказывается слабые тесты на 475C - Картина Камаль оль-Молька. Мое решение 8093677, которое прошло систест, падает на тесте:
When is the tutorial for this round going to be published?
Why does this solution passes? Oo 8087726
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.
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 ! :)
Can som1 plz xplain d soln for problem D?
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).
is there an editorial BYN ???!!!???
I'm afraid not in these days. We are so busy preparing our qualification and elimination round.
Warm Up Editorial
Hello! I have found cheater again! Read it!
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!
Hey can you take tutorial ?
If you give it, I'll take it!
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)
Same here, I didn't even think I would be able to win a t-shirt :)
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.me/contest/475/submission/8100455
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.me/contest/475/submission/8101816
This contest seems a little hard to me, I have to train my coding level.
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.
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.
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.
Thanks for your very nice explanation. Learning new thing is a gift to me. :)
cool, this is great explanation, thanks.
My solution to Problem 475B - Сильно связный город 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 ???
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
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.
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.
Here is an explanation for such short solution:
If outer streets (top, bottom, rightmost and leftmost) form a cycle (clockwise or counter-clockwise), then
If outer streets do not form a cycle, then
why the title of problem D is CGCDSSQ ??!:D
Count GCD SubSeQuences?
why there is not a low rated participant in the randomly t-shirt winners list?
3 purple :>
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
Could someone please tell me when the tutorial for this round is going to be published?
Today or tomorrow.
Here you go
Thank you very much :)