### Блог пользователя gen

Автор gen, 13 дней назад, перевод, ,

Привет всем!

Рад пригласить всех на Codeforces Round #599, который состоится в 06.11.2019 18:05 (Московское время)!

Меня зовут Евгений Вихров, это уже мой шестой контест на Codeforces. Немного обо мне: я дважды участвовал в финале ICPC (2012, 2014) и сейчас помогаю подготавливать команды Латвийского университета для участия в ICPC. Это мой первый соло раунд, и его подготовка заняла 3.5 лет! (Предыдущий раунд, #347, мы провели вместе с Alex_2oo8.)

В этом контесте вам предстоит помочь Уджану с его реновационными проблемами. Надеюсь, что каждый участник сможет найти задачу по своему вкусу!

Огромное спасибо arsijo за координацию раунда и терпение во время многочисленных задержек. :) Спасибо Xellos, Origenes, KAN и opukittpceno_hhr за щедрое тестирование задач. И, как всегда, спасибо MikeMirzayanov за хлеб и зрелища системы Codeforces и Polygon!

Желаю захватывающего раунда!

UPD1: McDic присоединяется как соавтор раунда (причины будут прояснены позже)!

UPD2: Scoring:

Div. 1: 500-1000-1500-2000-2500

Div. 2: 500-500-750-1500-2000-2500

UPD3: Спасибо за участие! Поздравляем победителей!!!

Div. 1:

Div. 2:

UPD4: Разбор будет опубликован завтра, извиняюсь за задержку. :((

UPD5: Причина тому, что McDic присоединился как соавтор, в том, одна задача оказалась идентичной одной задаче из одного раунда Codeforces. Мы узнали об этом за день до контеста, и McDic великодушно разрешил использовать свою задачу.

UPD6: Разбор опубликован (пока что только на английском).

UPD7: Опубликован разбор на русском.

• +613

 » 13 дней назад, # |   +60 С почином) Надеюсь ты сможешь найnи вдохновение для следующего контеста раньше, чем через 3.5 года)
 » 13 дней назад, # |   +76 Офигеть, когда это номер раунда уже подошел к 600! только вчера решал триста какой-то.
•  » » 13 дней назад, # ^ |   +89 Сам в шоке!
•  » » » 13 дней назад, # ^ |   +55 Почему минусят? Ради плюсов нужно быть красным? Рейтизм в действии...
 » 13 дней назад, # |   -60 I was the fifth person to register for the round.Hopefully a round that took 3.5 years to prepare is a good round :D
•  » » 13 дней назад, # ^ |   -42 good luck :)
•  » » 13 дней назад, # ^ |   +230 I was the fifth person to register for the round.I am wondering why the first four didn't comment.
•  » » » 13 дней назад, # ^ |   -27 The fifth cares enough.
•  » » 13 дней назад, # ^ |   +51 Congratulations man, you have achieved a lot at these young age. You can now join avengers
 » 13 дней назад, # |   -22 Евгений, правильнее будет сказать 3.5 года, а не 3.5 лет. А так, надеюсь, что раунд будет норм. А то обычно первые раунды у людей так себе. Удачи!
•  » » 11 дней назад, # ^ |   +8 Совершенно верно!
 » 13 дней назад, # |   0 Its too late for me...
•  » » 13 дней назад, # ^ |   +24 I decided to test rather than participate because it's too early for me...
•  » » » 12 дней назад, # ^ | ← Rev. 2 →   0 Who can test a round in codeforces?
 » 13 дней назад, # |   +169 Please add my handle as co-author in your announcement QAQ
•  » » 13 дней назад, # ^ |   +6 O_o
•  » » 13 дней назад, # ^ |   +16 O_o
•  » » 13 дней назад, # ^ |   +57 McDic orz
•  » » » 13 дней назад, # ^ |   -64 Mcdic antiorz
•  » » » » 13 дней назад, # ^ |   +60 For you he is Mr orz
•  » » » » » 11 дней назад, # ^ |   0 McDic orz
•  » » » » 13 дней назад, # ^ |   +41 Enjoy being blocked
•  » » 13 дней назад, # ^ |   +263 O_o
•  » » » 12 дней назад, # ^ |   0 And it's not even Div.1 E :D.
•  » » » » 12 дней назад, # ^ |   +10 it was 1D :)
•  » » » » » 11 дней назад, # ^ |   -10 UNoobAble orz
 » 13 дней назад, # |   +3 Auto comment: topic has been updated by gen (previous revision, new revision, compare).
 » 13 дней назад, # |   0 Автокомментарий: текст был обновлен пользователем gen (предыдущая версия, новая версия, сравнить).
 » 13 дней назад, # |   +40 UPD1: McDic is joining as a coauthor of the contest (reasons to be revealed later)!No chance of giving the round now! ;D
•  » » 13 дней назад, # ^ |   +52 Who do you want to give the round to and how is it possible to give a round to someone?
•  » » » 12 дней назад, # ^ |   +41 Lol, I know a lot of Indians who usually tell "giving the round" which means "participating in the round", which is kind of a literal translation from Hindi (The commonly spoken language in India).I hope this answers your question :))
•  » » » » 12 дней назад, # ^ |   +23 Yeah, I'm just making fun of that phrase because it doesn't make any sense in English, but good to know it comes from a literal translation.
•  » » 13 дней назад, # ^ |   +15 :(
•  » » 13 дней назад, # ^ |   +36 Ah, I see you are a man of culture as well.
•  » » » 11 дней назад, # ^ |   +1 You as well :)
 » 13 дней назад, # | ← Rev. 2 →   +58 I have already risen to master, fallen to candidate master, risen to master, fallen to candidate master, ...... for totally 11 times. And I just rised to master in last round, I hope I can stay in master in this round.
•  » » 12 дней назад, # ^ |   +91 Or maybe you failed and raised to International Master.
•  » » 11 дней назад, # ^ |   +1 You (barely) avoided! Congrats!
 » 13 дней назад, # |   +134 Ставлю бороду Снарка, что orz 300iq вылетит из топ-10 после раунда.
•  » » 11 дней назад, # ^ |   +18 Ха-ха!orz 300iq
 » 13 дней назад, # |   +2 How to become a tester for contests and contribute problems??
•  » » 13 дней назад, # ^ |   +5 tester Get asked. contribute Click "Propose a contest/problems".
•  » » » 13 дней назад, # ^ |   +1 Thank you..
•  » » » » 12 дней назад, # ^ |   +3 Codeforces problem-setter hien2k.hy
•  » » » » » 12 дней назад, # ^ |   +3 my idol <3
 » 13 дней назад, # | ← Rev. 16 →   +55 I think I know the reason why McDic added as co-author. In his last round he removed a problem from the contest beacuse of no one can solve it in testing. I thing that problem will be added this round
 » 13 дней назад, # |   +6 Slow work yields fine products,it mights be a good contest.Looking forward to my first div.1!
 » 13 дней назад, # |   +33 Надеюсь, функция качества раунда от времени примерно похожа на функцию коньяка.
•  » » 12 дней назад, # ^ |   -7 Кстати, так обычно и бывает, если идея нигде не появлялась, она наверняка крута. Единственная опасность в таком случае — что ты кому-то рассказал, что у тебя есть такой-то коньяк, и потом на дегустации оказывается, что куча народу уже его попробовали :)
 » 13 дней назад, # |   0 Hey, can someone tell me more about the sites which actively create contests and where I can use my knowledge of Data Structures and Algorithms?Apart from codeforces, I know about hackerearth, codechef, google competitions, atcoder, topcoder.Recently, I came to know about leetcode through Errichto's youtube video.Please, can someone suggest anything about it?
•  » » 13 дней назад, # ^ | ← Rev. 2 →   +17 I usually follow https://kontests.net/ which keeps me updated on running/future contests on most platforms.
 » 12 дней назад, # |   +49 Last round in Codeforces Round #5xx i hope it would be a great closing
 » 12 дней назад, # |   0 So much red color in div2 announcement makes feel worried :| . However, let's hope that this will be balanced.
 » 12 дней назад, # |   +4 In this contest you will have to help Ujan deal with his renovation issues.Hoping that the problem statements will be short and clear!
 » 12 дней назад, # |   0 А сколько задач??
 » 12 дней назад, # |   -31 Is it rated?do not rate me
•  » » 12 дней назад, # ^ |   -16 I want to ask it too.
•  » » 12 дней назад, # ^ | ← Rev. 3 →   0 Is it rated? Yes, It is RATED for all.
•  » » » 12 дней назад, # ^ |   0 So hard to read mehn
 » 12 дней назад, # |   0 Good luck everyone!
 » 12 дней назад, # |   +1 How many problems will be in the round?
 » 12 дней назад, # |   +3 Will be there multiple-task problems?
 » 12 дней назад, # |   0 How many problems? And what scoring?
•  » » 12 дней назад, # ^ |   +3 Yes, how many problems in round?
•  » » » 12 дней назад, # ^ | ← Rev. 2 →   +1 6; UPD2: Scoring: Div. 1: 500-1000-1500-2000-2500 Div. 2: 500-500-750-1500-2000-2500
•  » » 12 дней назад, # ^ |   0 oho!,where no update.
•  » » 11 дней назад, # ^ |   +32 Three problems in Div1.
 » 12 дней назад, # |   +1 I can already smell mathforces XD
 » 12 дней назад, # |   -10 I will come back whenever I will become pupil
 » 12 дней назад, # |   0 Expecting speedoforces after seeing the score distribution.
 » 12 дней назад, # |   -14 I missed this contest as I thought the contest will be started at 9:35 AM (usually CF contests will start at this time) in my time zone. However, unfortunately, the start time for contest was at 9:05 AM. I know it was my fault that I didn't double check the time. But just as a suggestion for MikeMirzayanov and Codeforces team, it would be great if they unify the time of the contests, which are close to each other, to a certain, fixed time.
•  » » 12 дней назад, # ^ |   +27 That wouldn't work all the time, just most of the time, which seems to be your problem. If a problemsetter can't be online the whole evening because there's something else planned before/after, choosing a slightly different time could be necessary.
 » 12 дней назад, # |   +20 That was a great contest!
 » 12 дней назад, # | ← Rev. 4 →   +5 Hopefully gonna be expert for the first time. Just an awesome contest
 » 12 дней назад, # |   +8 What hacks did you guys find and what were they about?
 » 12 дней назад, # | ← Rev. 2 →   +80 Fun fact, Div2D/Div1B's code is almost identical to the problem 920E, even though the thing they asked for is different. I've just done 920E in practice, so I recognized it and ctrl-CVed my code. I'm betting there are many who does this.
•  » » 11 дней назад, # ^ |   +2 How much are you betting?
•  » » 11 дней назад, # ^ |   +8 Yeah I did the same thing
 » 12 дней назад, # |   +11 How to solve div2 D? with 920E :))
•  » » 11 дней назад, # ^ |   +8 Or with 190E - Контрнаступление, if you are old enough :)
•  » » 11 дней назад, # ^ | ← Rev. 2 →   +7 I think it's also similar to 1228D - Complete Tripartite from McDic's last round xd.
 » 12 дней назад, # | ← Rev. 2 →   +44 There are k boxes numbered from 1 to k. The i-th box contains $n_i$ integer numbers. The integers can be negative. All of the integers are distinct. I understood this as "all integers in any single box are distinct" and wasted over an hour on C before realising that wasn't the case. This could have been stated much more clearly. For example, "no integer occurs twice, not even in two separate boxes".
•  » » 12 дней назад, # ^ |   0 rip
•  » » 12 дней назад, # ^ |   +7 All of the integers are all of the integers. If it was in each box, there would be an additional qualifier "in each box". Later, it's mentioned that "all $a_{i, j}$ are distinct" in a separate paragraph and there's no distinction made between $i$ and $j$.It took me a while to notice that they're distinct, but it's correct the way it's written.
•  » » » 12 дней назад, # ^ |   +8 The reason I misunderstood it was exactly because the qualifier exists: The i-th box contains $n_i$ integer numbers. The integers can be negative. All of the integers are distinct. These three sentences to me are talking about the integers in box $i$. Writing The integers can be negative. The integers are distinct. Sounds bad, so even if I only wanted to talk about the integers in a single box, I'd write the former version (with all). I guess the correct interpretation makes sense too, if you consider the sentences to be separate entities. Of course, I'm not a native English speaker, so maybe this sounds ridiculous to someone who understands it better than I do.
•  » » » » 12 дней назад, # ^ |   +18 I'm pretty sure sentences are separate in perkele too. When you string together too many sentences, context can't carry over between them forever, that would break language. Besides, the sentence about negativity in between applies to everything equally, the qualifier is meaningless there. You just missed it.
•  » » 11 дней назад, # ^ |   +32 Yeah, it could've been clearer, sorry.
 » 12 дней назад, # | ← Rev. 2 →   +11
 » 12 дней назад, # |   -22 Unbalanced round ;__;
 » 12 дней назад, # |   +16 How to solve Div1 C?
•  » » 12 дней назад, # ^ |   -48 If n has more than 1 prime factor ans is 1. Else ans is the only prime factor n has.
•  » » » 12 дней назад, # ^ |   +23 I think what you are saying is Div2 C not Div1 C
•  » » » » 12 дней назад, # ^ |   -18 Sorry my mistake, didn't read properly.
•  » » » 12 дней назад, # ^ |   0 what if n is 8?
•  » » » » 12 дней назад, # ^ |   +3 2
•  » » » » » 12 дней назад, # ^ | ← Rev. 2 →   0 im sorry I just see your comment like number of divisors instead of number of prime factor sorry!
•  » » 12 дней назад, # ^ |   +8 I was doing a dp on processed boxes: added to dp[mask] a number left "unused" if we perform non-cyclic reordering on the boxes in the mask (i.e. normal reordering without one transfer). But I was lost somewhere in building an answer from dp transitions :/
•  » » 11 дней назад, # ^ | ← Rev. 2 →   +31 If the sum of all numbers is not divisible by $k$, then the answer is No.Otherwise, let $S$ be the sum of all numbers. The sum of integers in each box must be $S/k$Suppose the first box sum is $S_i$. If we decide to take some integer $c$ out of it, then obviously its sum will be $S_i - c$, and we need to put the number $S/k - S_i + c$. Given that all $c_i$ will be distinct, then this required number should be in at most one box.Now, if the required number is $d$ and its taken from some other $j$ box, then we should find where $S/k - S_j + d$ is. We will take $d$ out of that box and solve the same problem. This will lead us to a cycle, until we reach the box $i$. Obviously, if some integer is not found within all the boxes, or we have to take an integer from a box that has already been modified, then it's not possible.Given that $1\leq k\leq15$, we can apply a bitmask dp. We will take any box that has not been modified and try to take every possible integer out of it and apply the process explained above. Once we obtain the cycle, we repeat the dp with the other boxes that have not been modified (i.e. don't belong to the cycle).
 » 12 дней назад, # | ← Rev. 7 →   +19 My D solution:Let's look at the index of the $i$-th sequence($0$-indexed) where a number is skipped because it appeared as a sum of some other sequence. Let's call this $f(i)$.There are $2$ cases:1) $k$ is even$f(i)=\frac{k}{2}+i*k$2) $k$ is odd$f(i)=\frac{k-1}{2}+i*k+g(i)$Let's write $i$ in base $k$. If there is no digit $\geq \frac{k+1}{2}$, then $g(i)$ is $0$. Else, let's say that the least significant digit which is $\geq \frac{k+1}{2}$ represents $k^x$. $g(i)=1$ if $x$ is even and all digits representing $k^y$ where $0 \leq y < x$ are equal to $\frac{k-1}{2}$ and $0$ otherwise.Using this the rest of the implementation shouldn't be too hard in an awful complexity(I'm not sure if it's ever actually achieved) but the average case is really good. You can feel free to hack this if the worst case really is too slow.How i figured this out:Just make a brute force and notice some patterns.Code: 64419936There are definitely better solutions though.Edit: my solution is in fact too slow, it will soon be hacked. There might be ways to use $f(i)$ which aren't too slow though. The reason the solution is so slow is because finding $g(i)$ takes $O(log n)$, I'm not sure if there's a better way.Edit 2: I realized $g(i)$ can be calculated in $O(log log n)$ but that's still too slow.Edit 3: Actually, the slowness doesn't have anything to do with $g(i)$; i actually call $f(i)$ $log(n)*log(n/k)$ times in the worst case, which is clearly too slow.
•  » » 12 дней назад, # ^ |   +6 My solution for D is different. It will be available on editorial.
•  » » 11 дней назад, # ^ | ← Rev. 4 →   +47 I managed to debug and simplify my solution and I think this problem is really beautiful: 64426704Let's call the set of $K+1$ numbers added in one step a block, and set of $K$ consecutive blocks a superblock. Each block contains $K$ low values (those are the $u_i$), and $1$ sum.Now comes the guesservation: the $i$-th superblock contains $K^2$ low values from interval $[i*(K^2+1)+1, (i+1)*(K^2+1)]$, e.g. there is exactly one number missing. When we find this missing number, we can easily find the sum of any block within this superblock (because it consists of at most two arithmetic sequences).As the sums are increasing, it is obvious that the number missing in the $i$-th superblock is the sum of the $i$-th block. The $i$-th block belongs to $i/K$-th superblock, so we can solve this recursively with the initial condition that the sum of $0$-th block is $K*(K+1)/2$.The algorithm is as follows: we find the superblock to which $N$ would belong if it was a low value (it's $\frac{N-1}{K^2+1}$), let's call this $x$. If sum of the $x$-th block is $N$, then the answer is $(x+1) * (K+1)$, otherwise we can find the answer because we know what is the missing number in our superblock.The complexity is $\mathcal O(\log N / \log K)$ per test case.
 » 12 дней назад, # |   0 The Idea for the DIV2 — C was somewhat similar to 1245A - Good ol' Numbers Coloring !!!
•  » » 11 дней назад, # ^ |   0 I AC'ed that one but failed this one. Was searching for minimum prime factor for one whole hour. Feels bad man
 » 12 дней назад, # | ← Rev. 3 →   +32 hakobdilif must have been practicing really hard since Monday!
 » 12 дней назад, # |   -8 Hi , Can anyone tell me why I got wrong on pretest 6 in Problem C ?My Code :long long n ; cin >> n ; bool chk=0; if(n%2==0) cout<<2 ; else { if(n==1) cout<<1; else { for (int i=2; i<=sqrt(n); i++) { if (n%i == 0) { cout<
•  » » 12 дней назад, # ^ |   0 check at n = 6 the answer should be 1
•  » » » 12 дней назад, # ^ |   0 I got it , Thank you so much :)
•  » » 12 дней назад, # ^ |   0 for 6 answer is 1. your solution prints 2.
•  » » » 12 дней назад, # ^ |   0 Thank you so much :)
•  » » 12 дней назад, # ^ |   +1 The answer isn't always the smallest prime divisor of n. Take the case n = 6, for example. If we paint tile 1 black, then tile 3 and tile 4 have to be black. Since tile 4 is black, tile 2 and tile 6 are black, and since tile 3 is black, tile 5 is also black. So all tiles have to be the same colour.The correct answer is finding the gcd of all non-unity divisors of n.
•  » » » 12 дней назад, # ^ |   0 Thank you so much :)
•  » » 12 дней назад, # ^ |   0 try n = 6.1,3,5 should be the same 2,4,6 should be the same 1,4 should be the sametherefore all should be equal.Your code says 2.
•  » » » 12 дней назад, # ^ |   0 I got it , Thank you so much :)
•  » » 11 дней назад, # ^ |   0 tryvalue of n->ans 1->1 2->2 3->3 4->2 5->5 6->1 7->7 8->2 9->3 10->1
 » 12 дней назад, # |   0 How to solve Div2 B2 ? got memory limit exceded
 » 12 дней назад, # |   +9 UPD1: McDic is joining as a coauthor of the contest (reasons to be revealed later)! What was the reason?
 » 12 дней назад, # |   +5 ...
 » 12 дней назад, # |   +105 My problem in this contest is Div1D. Thanks to all people who participated!
•  » » 12 дней назад, # ^ |   +36 It is really a wonderful problem! I did find the pattern but have no time to code — a sad story.
•  » » » 11 дней назад, # ^ |   +82 I couldn't find a pattern so I decided to try E instead :P
 » 12 дней назад, # | ← Rev. 2 →   0 My solution to Div-2-C is getting all prime factors of the number if the number have only 1 prime factor print it, otherwise(because it contains more than 1 prime so gcd will be equal to 1) print 1Is that Right?
•  » » 12 дней назад, # ^ |   0 Yeah
•  » » » 11 дней назад, # ^ |   0 But why? Can you please explain?
•  » » » » 11 дней назад, # ^ |   0 hopefully, reason :- actually answer is gcd of all the factors of nsince proof by contradiction, let's assume the answer is not equal to 1 in that case, the answer is greater than equal to 2 if so then while calculating let's suppose no be 2,6 but still, if 6 is its factor than 3 must be too if gcd(2,3,6) is calculated then it comes out to be one it will not be one if all the numbers are the power of same prime.
•  » » » » » 11 дней назад, # ^ |   0 Thanks
 » 12 дней назад, # |   0 Can anyone tell me if my code for prob B2 true or false plz. I completed it after the time had ended, just a minnute. I feel so bad but Im also feel nervous if it is true or not, help me plz, Im so so sad now T-T. My Code for prob B2
•  » » 11 дней назад, # ^ |   0 It passed and I feel so sad, but if it hadnt passed, I would have been sad also. Bad day T^T
 » 12 дней назад, # |   0 Hello, I found a sequence in OEIS for problem C div2. Can anyone say if it relates with the problem? https://oeis.org/A014963
•  » » 12 дней назад, # ^ |   0 It relates but I am not sure how.
•  » » 11 дней назад, # ^ |   0 Yes it does, when there are more than 1 factor, then they happen to meet at some number, which is not 0 modulo the first factor; hence a imbalance and causes a chaos which leads to everyone having same color.When 1 factor: No chaos. So number of colors same as the factor.
•  » » 11 дней назад, # ^ |   0 yes it relates
•  » » 11 дней назад, # ^ |   0 It is exactly the same thing.
 » 12 дней назад, # |   0 B1 and B2 should have been C and D. I did not even read B1 until the contest was about to end.
 » 12 дней назад, # |   +8 My approach to Div1E (I figured it out 10 minutes before the end, so couldn't implement):If there is only one face, the answer is obvious.If there are two faces, then there is an outside vertex (vertex of the whole polygon) $v$, which has an edge to the inside of the polygon. Notice that we can sometimes "glue" the two polygon edges adjacent to $v$. And this way we will decrease the perimeter by $2$. Thus, the perimeter is always $3$ or $4$. How to know is it $3$ or $4$? Well, take a look at $a_1 + a_2 + \ldots + a_n$. It's equal to $2 * insideedges + outsideedges$, so the parity of the number of outside edges is known, so we can figure out the perimeter.Now the only implementation that came in my mind is to implement the process: build a chain of faces, where two adjacent have one common edge, and then reduce it to $3$ or $4$. Is there a better way of writing the code for it?
•  » » 11 дней назад, # ^ |   +8 okay, im wrong
 » 12 дней назад, # |   -36 MikeMirzayanov I got Idleness limit exceeded on 64385470 I submitted the same code again but i changed the code so I Can submit it again and I got pretest passed on 64387902, I only removed the all the #define at the beginning of the code.
•  » » 11 дней назад, # ^ |   +41 You have many changes. Just use the compare feature.
 » 12 дней назад, # |   +16 Wow, great Div1C! I especially liked the part with restoring the answer in such an elegant form. orz=3
•  » » 11 дней назад, # ^ |   +10 I think that restoring the answer is very easy to implement in this problem. Also, here it's much better for the checker: if somehow participant finds the answer while author's solution has bug and doesn't, there is way to find this out only if we return answer, too.Btw, never saw you posting a comment with positive feedback about problems on CF, but saw a lot of negative. Are all problems on CF so bad?
•  » » » 11 дней назад, # ^ |   +31 Hm, no, problems from 572 (Div. 1) were ok :) But I will try to write more positive comments in order to increase contribution!
 » 12 дней назад, # |   0 А правда ли что в самом начале контеста фраза "Все данные числа различны." не была жирной?
 » 11 дней назад, # |   +9 contests like a wine..........
 » 11 дней назад, # |   -15 What is test case 35 for Div 2 C.
•  » » 8 дней назад, # ^ |   0 A number n with a prime factor around 10^9 but this prime factor is not n itself.
 » 11 дней назад, # |   0 0-1 MST is just a version of the first problem of kickstart round E(Cherries Mesh). Just replace the( 1 and 2 cost) with (0 and 1 cost). Problem link
•  » » 11 дней назад, # ^ |   +14 It was in cf round 120
•  » » » 11 дней назад, # ^ |   +30 Its remix of an old song of the beatles.
•  » » 11 дней назад, # ^ | ← Rev. 2 →   0 I think there's an (important) difference — there you have all the light edges, here you have all the heavy edges. Since counting connected components over the light-edge graph is relevant, there you can just DFS the graph itself, here you have to DFS the anti-graph formed (which is a harder problem because the antigraph may have upto n(n-1)/2 edges so you need some tricks).
•  » » » 11 дней назад, # ^ | ← Rev. 2 →   +7 I still did BFS on the graph with some tricks, as you said. You can do this by keeping the set of vertices not yet in the queue and checking for each whether it's 0 or 1 edge. This has complexity of $O(n^2 \log{n})$.However, you can make an observation that if $n$ is small, you're fine with this. If $n$ is large, then because of requirement on total 1-edges, there will be one very large component, and if you immediately eliminate it, you're left with very small $n$ again, so you're fine with BFS.One vertex of such component is the vertex with the least amount of 1-edges out of it. So as long as you begin your BFS with that vertex, your BFS will pass.
•  » » » » 11 дней назад, # ^ |   0 That's a cool idea — I did think of optimizing the antigraph traversal, but then convinced myself that that idea was wrong :( It was anyway not a trivial insight for me. Thanks for the comment :)
•  » » » » 10 дней назад, # ^ |   0 You actually don't even have to start your BFS at the least degree vertex to get an AC for this problem. You can start from any vertex, and your solution will pass. Is it because of weak test cases?
•  » » » » » 9 дней назад, # ^ |   +3 Interesting. Just tried submitting the solution with the start of the queue at vertex with the biggest degree vertex and the solution still passed with roughly the same time.I guess because you can only remove so many vertices from the main component (let's call the amount of them $k$) that perhaps it just doesn't matter indeed no matter the test cases, in which case writing BFS with only considering vertices not yet in the queue was enough.Roughly speaking, the asymptotic of this solution is $O(k n \log{n})$ (until you reach your main component you'll process $k$ vertices while considering $n$ edges for each, and after you reach it, you'll process $< n$ vertices while considering $< k$ edges for each). but since $k * (n - k) <= 100000$, $k$ is realistically small for large $n$ ($k <= 112$ for $n = 1000$ and $k <= 1$ for $n = 100000$), and it's still enough. Wouldn't bet on it though during the contest.
•  » » 11 дней назад, # ^ |   0 No this is question opposite of Div2D
 » 11 дней назад, # |   0 Can anyone please explain how to solve Div2 B2?
•  » » 11 дней назад, # ^ |   +1 If each letter occurs even number of times in total the answer is possible.Now, iterate over string. If $s1_i$ is not equal to $s2_i$, you find an element in either string that is equal to $s1_i$ ( and by the first condition you are guaranteed that such an element exists), and bring it to $s2_i$, either by swapping directly if it is in $s_1$, or by swapping using an intermediary element (if it is in $s_2$). Submission: 64389826
•  » » » 11 дней назад, # ^ |   0 barun511 please can you tell me why my Solution for 1243B2 - Character Swap (Hard Version) didnt work ! Checker comment told me : wrong answer Solution not found but exists [test=371] what did that mean !! this my code ! 64414329****
•  » » » » 11 дней назад, # ^ | ← Rev. 2 →   0 You output NO for 1 23 hsezxzwzvnjxvvozhofzvsm czdcdnwvcdfxerzvxdcjrmz Whereas solution is possible
 » 11 дней назад, # |   +14 orz isaf27
 » 11 дней назад, # |   +3 can anyone help me prove my solution in Div2.D 64389079 I just guess if n >= 1e3 I calculate all of the Unicom blocks with a point with a value of 0 with a margin of less than 200, and points greater than 200 as a Unicom block.
 » 11 дней назад, # |   +6 Please explain solution of Div2 C with a proof.
 » 11 дней назад, # |   +40 I'm so sad :(
•  » » 11 дней назад, # ^ |   +33 I performed worser but I’m not sad
•  » » » 11 дней назад, # ^ |   +56 Poor baby koosaga...
 » 11 дней назад, # |   0 thank you .. but please can any one tell me why my Solution for 1243B2 - Character Swap (Hard Version) didnt work ! Checker comment told me : wrong answer Solution not found but exists [test=371] what did that mean !! this my code ! 64414329
 » 11 дней назад, # |   +5 Why does it work: 64384395? Weak tests or it can be proved?
•  » » 11 дней назад, # ^ | ← Rev. 2 →   +29 I came up with a similiar idea to a similiar problem before XD 34872588Its worst case time complexity is $O((N+M) \log N)$. ( $O(N+M)$ data structure (set,vector access) operations, to be precise).I have claimed it here, but I didn't wrote the proof down QAQ.This inner loop from your code is the only nontrivial part in time complexity analysis because all other parts are obviosly $O((N+M)\log N)$. To know its time complexity, we just need to count how many times we access $cur$. for (int w : cur) if (!g[u].count(w)) { to_del.push_back(w); } Case 1. When g[u].count(w) == 0, $w$ is then removed from $cur$. The number of accesses from this case is $O(N)$.Case 2. When g[u].count(w) == 1, an edge $(u,w)$ exists. Since each $u$ is taken out exactly once from the queue and we loop through $cur$ exactly once for each $u$. We have an injection from an access to an edge. Therefore, the number of accesses from this case is bounded by the number of edges $O(M)$.So the total number of accesses to $cur$ is $O(N+M)$.Correct me if I am wrong :)
 » 11 дней назад, # |   +127 OH Benq just had been broken rank 1
 » 11 дней назад, # |   +3 For Problem D, I had tried to create a DSU of components connected by 0-edges only. I felt no of components -1 will be the answer. Since this might TLE, I had a visit array so that once I see a node i, I perform union_set(i,j) such that (i-j) is a 0-edge and also mark visit[j]=visit[i]=1. So this may not TLE. But it gave me a WA on TC 13? any idea whats going wrong :(
•  » » 11 дней назад, # ^ |   +3 Even I am facing the same problem.
•  » » 11 дней назад, # ^ | ← Rev. 12 →   +14 You cannot mark j as visited before checking all edges of j. For example, imagine a graph of size 4 with the following 0-edges (not 1, it is easier to write only the 0-edges): 1 3 2 4 3 4 When visiting 1 you set 3 as visited, when visiting 2 you set 4 as visited, then you will never consider the edge 3-4.Your algorithm answers 2 instead of 1.Instead of looping through every possible edge, I did a BFS checking only the edges reaching unvisited vertices, this way you can avoid trying all the edges. When you try the edge (a,b) you will have 2 cases.Case 1: it is of weight 0, therefore you add b to the queue and never try any edge reaching b, in this case number of unvisited vertices decreases by 1.Case 2: it is of weight 1 and you will do nothing and try b again later, in this case the number of remaining edges of weight 1 decreases by 1.Therefore you either decrease the number of unvisited vertices or the number of remaining edges of weight 1, so it is in the order of 2*10^5 operations.
•  » » » 11 дней назад, # ^ |   +11 Thanks a lot!!! It's all clear now :)
 » 11 дней назад, # |   +19 Congrats @Benq for #1
 » 11 дней назад, # | ← Rev. 6 →   -7 Congratulations @Benq and all hard workers :D
 » 11 дней назад, # |   0 Damn, I solved ABCD, which in theory could give me very good place for me, but I got TLE in D (I think it's just constant factor since if I'm not mistaken I have O(log n / log k) with hashmap per query) and small but in C (removing one line fixed it) and in the result I have >200 place and -145 to rating... I hate it so much >_>But at least I enjoyed D even though I struggled with +-1s for literally >0.5h. E seems really nice as well
•  » » 11 дней назад, # ^ |   +14 The same thing in C and AC in D, -157. Love CF scoring distribution.
•  » » » 11 дней назад, # ^ |   +11 We will rebuild!
•  » » 11 дней назад, # ^ | ← Rev. 2 →   0 I ran your code for $K=2$ and $T=100000$ random values of $N$. You store values of 24 million states in the hashmap and call your "solve()" function one hundred million times. I've experienced some problems where the number of tests was unnecessarily high (232C - Doe Graphs in particular), but this sounds too inefficient. In comparison, my solution has a clean non-branching recursion with no memoisation required.
•  » » » 11 дней назад, # ^ |   0 Hmmm, that sounds suspicious, maybe I did some mistake in the complexity analysis, I will check than when I have time. Thanks.
•  » » » 11 дней назад, # ^ |   +3 FUUUUU, I adjusted my code a little bit so it is more careful and it passed within 1s out of 2s. Basically everything was asymptotically fine with my code, but I sometimes did some unnecessary calls which caused me to store 7 log n states instead of 3 log n states.
•  » » » » 10 дней назад, # ^ | ← Rev. 2 →   +10 11 hackedJust generate 100000 random tests with $K=2$. It still takes 10 seconds locally, my solution takes < 150 ms. Function call overhead and hashmap lookup overhead are probably the worst offenders.UPD: And it's down to 4 seconds when I wipe the hashmap as soon as it gets too large and do lookup before function calls.
 » 11 дней назад, # |   -23 Benq dethroned tourist after years!!! Congrats Benq ! tourist no matter what is your rank we will always love you!
•  » » 11 дней назад, # ^ |   +104 "after years" This has happened before, I remember Radewoosh and Um_nik at the top. But it's never lasted long ;)
•  » » 11 дней назад, # ^ | ← Rev. 2 →   +6 Don't worry — he'l be coming back for as long as he lives.
 » 11 дней назад, # | ← Rev. 4 →   +14 Exactly 1600.
•  » » 11 дней назад, # ^ |   +15 Exactly 2000
•  » » » 11 дней назад, # ^ |   +43 Exactly 2257
•  » » » 11 дней назад, # ^ |   +19 Exactly no change
•  » » » » 11 дней назад, # ^ | ← Rev. 4 →   +15 I did exactly no change twice along with exactly 1400, 1600, 2100 and 2257.And not to forget that unrated aryanc403 was 1500.
•  » » 11 дней назад, # ^ |   +31 Waiting for that since eternity :(
 » 11 дней назад, # | ← Rev. 2 →   -10 Решение D(div2) 64423223 Очень жаль, у вас слабые тесты.
 » 11 дней назад, # |   +21 Div1 B can be solved almost directly using Borůvka's algorithm, but on the contest i found more convenient using a mix of bfs and Borůvka idea 64380663
 » 11 дней назад, # |   -17 Thank you for the interesting problems! In particular, I quite liked Div1B and Div1C.
•  » » 11 дней назад, # ^ |   0 Div1 B is somehow the same as 190E and 920E , well, the code is the same at least.
•  » » » 11 дней назад, # ^ |   +55 It's funny how each time this problem occurs it requires less and less data in the output (I mean: first all the components, then sizes of comonents and now only the number of them)
•  » » » » 11 дней назад, # ^ |   +13 That's a good thing, it means this problem probably won't occur again :D
•  » » » » » 11 дней назад, # ^ |   +83 there's still "check if it is connected" variation.
•  » » » » » » 11 дней назад, # ^ |   +15 Validate the input.
•  » » » » » » » 11 дней назад, # ^ |   +25 Stand and dance at your desk for AC.
 » 11 дней назад, # |   +11 Can someone explain the exact proof for Div1-A
•  » » 11 дней назад, # ^ |   +5 If n has at least two prime factors, let's say p and q, you can use Bezout's lemma to find that there exists a and b such that a*p+b*q = 1. Therefore you can achieve a net displacement of 1 after many steps of moving forwards and backwards. Thus, the answer is 1.If it has only one prime factor p, then every position with the same remainder mod p has the same color, therefore the answer is p.
•  » » » 11 дней назад, # ^ |   0 But won't there be condition on a*p <= n. Or is it always possible to do some +p and -q operations such that the current value is always less/equal to n.
•  » » » » 11 дней назад, # ^ |   +24 Yes, it is possible that a*p > n. However, when you get near n and cannot move forward by p, you can just move back by q as many times as necessary. As when you have two prime factors both are at most n/2, you can always do this.
•  » » » » » 11 дней назад, # ^ |   +8 Got it.Thanks
 » 11 дней назад, # |   0 [Problem D] I'm looking forward to find a bug in my submission 64417332. Glad if somebody catches it. The approach i quite straight forward. I take vertices with largest degrees and connect them with everything, that's possible. (Keeping track on already picked and connected vertices.) This way I decrease the number of components and the answer is just components_no — 1.
•  » » 11 дней назад, # ^ |   +9 You cannot set i as done before considering all edges of i. Think about the case of the following 0-edges (not 1-edges): 1 10 1 11 1 12 2 13 2 14 2 15 12 13 When you process 1 you set 12 as done, when you process 2 you set 13 as done, then you never consider the edge 12-13
 » 11 дней назад, # | ← Rev. 2 →   0 I am getting this message for DIV2-B2 in testcase3 64427963wrong answer Integer parameter [name=m] equals to 10, violates the range [1, 8]
•  » » 11 дней назад, # ^ | ← Rev. 2 →   +8 Your algorithm is probably outputing m=10 to a string of size 4.
•  » » » 11 дней назад, # ^ |   0 yes bug in my code thanks BTW
 » 11 дней назад, # |   +26 Problem Div 1 D strongly resembles a problem from the 2015 Putnam competition, which we can see here: https://artofproblemsolving.com/community/c7h1171035p5624365
•  » » 11 дней назад, # ^ |   0 Damn, this problem was such a fking pain. Hardest A\B<=2 problem I've seen on Putnam. I decided to write down its elements not larder than something like 60-80 and noticed nothing and decided to abandon it. After the contest I asked some people that solved this problem and they all replied that they generated this sequence up to something like 150 and then noticed some pattern xD
 » 11 дней назад, # |   +1 It will be better competition if round-600 will be a global round
 » 11 дней назад, # | ← Rev. 2 →   0 My randomized solution in Div1 B: 64405219. I have no idea what its probability of success is, does anyone have a clue, even for an approximate value or some bounds?
•  » » 11 дней назад, # ^ |   0 Can you explain how this works on a high-level? There are some things that aren't immediately obvious to me from a quick scan, like what relevance 170 has.
•  » » » 11 дней назад, # ^ | ← Rev. 2 →   +8 170 is the $MAGIC$ number :D Increasing it increases the probability of success and also the running time.My solution works as follows: for each node, if the number of adjacent nodes to it is larger than $n/MAGIC$, then join this node with all non-adjacent nodes. Else, choose $MAGIC$ nodes randomly, and join this node with non-adjacent nodes among these nodes. The time complexity will be $O(max(n,m) * MAGIC * O(DSU Operation))$.My intuition about it is that if some node has so many non-adjacent nodes, then most probably I won't need to join it with every single one of them, because many of them may be already joined or will be joined later. However if I just do this for every node, it may be the case that some node has only a few non-adjacent nodes, and it must be joined with each one of them, that's why when the number of non-adjacent nodes is few, I iterate on all of them.
•  » » » » 10 дней назад, # ^ |   0 Update: even when I set $MAGIC$ to just $5$, it passes! 64519426
 » 11 дней назад, # |   +18 My solution for D, upsolved shortly before the contest, is based on one main observation (which I can't prove): the difference between the $iK$-th and $(i+1)K$-th sum for each $i \ge 0$, i.e. $s_{(iK+K+1)(K+1)} - s_{(iK+1)(K+1)}$, is always $K(1+K^2)$. Another observation is that $s_{(iK+1)(K+1)-1} = i(1+K^2)+K$, also unproven.Clearly, the $i+1$-th sum is always at least $K^2$ larger than the $i$-th sum, so this means the difference between each two consecutive sums is at most $K^2+K$. In addition, when we want to find the $aK+b$-th sum, we know that the $aK$-th sum is exactly $\frac{K(K+1)}{2} + a(1+K^2)$ and the $aK+b$-th is at least $\frac{K(K+1)}{2} + a(1+K^2) + bK^2$ and at most $\frac{K(K+1)}{2} + a(1+K^2) + bK^2 + K$. The most important property is that for all $b$, these ranges are disjoint.Next, we need to realise that we only need to find the first sum $\ge N$ (both index and value). If it's equal to $N$, we have the right index, and if it's greater, then before the answer — index $id$, there are all numbers $\le N$ and a few sums $\gt N$. Since we know how many sums are $\le N$ and that there are $id/(K+1)$ sums before $id$ in total, $id$ is the result of a simple equation.How to find this sum? We can easily find the greatest $a$ such that the $aK$-th sum is $\le N$, and we only need to find the smallest $b \le K$ such that the $aK+b$-th sum is $\ge N$. The "maximum value of the sum" expression above gives us an easy lower bound on $b$ — the greatest $b \ge 1$ such that the maximum possible value of the $aK+b-1$-th sum is $\lt N$. Then, the first sum greater than $N$ must be the $aK+b$-th or $aK+b+1$-th, depending on the exact value of the $aK+b$-th sum, since the minimum value of the $aK+b+1$-th sum is automatically $\ge N$. We just need to find a sum with a given index.Finding the $aK+b$-th sum uses the same idea, but applied on sums that are low enough that they can interfere with the summands used to create this sum. Specifically, this sum is $m + (m+1) + \ldots + (M-1) + M$, where either $m = M$ and there's no sum between $m$ and $M$, or $M = m+1$ and there's a sum between them. From the other observation above, $M \ge a(1+K^2)+K+bK$ and $m \ge a(1+K^2)+1+bK$. Let's start with this estimate and consider sums that are $\ge a(1+K^2)+1+bK$; with some calculations, we get that this corresponds to the $a$-th, $a+1$-th etc. sums. For each of these sums, if it's smaller than the current estimate for $m$, then our estimates for $M$ and $m$ should increase by $1$. If it's between our current estimates for $m$ and $M$, we increase just $M$ (the last $M-sum+1$ summands, to be precise), but the next sum will be much larger — greater than $M$, so we've got the summands and can compute the sum. It also turns out that we only need to compute this last sum and use the upper bound estimated above for the rest.Implementation: 64426937. The while-loop should be $O(1)$ and we're computing recursively the $i$-th sum from the approx. $i/K$-th sum, so the total complexity is $O(\log N / \log K)$.
 » 11 дней назад, # |   0 It seems that the data is so weak.I used std::map in Div1. C but passed the system test.
•  » » 11 дней назад, # ^ |   +6 Umm what's weak about that? All numbers are distinct.
•  » » » 10 дней назад, # ^ |   0 Hack #596829.I used map.find(x) to find the id of x or x isn't appeared,but x can be larger than INT_MAX so that my code can be hacked by: 2 2 1 2 10 0 1000000000 999999999 999999998 999999997 999999996 999999995 999999994 999999993 589934621 
 » 11 дней назад, # |   0 How come the English version of the post has "bread and circuses" in original Latin while in the Russian version it is translated into Russian? Can't Russians learn Latin? :P
 » 11 дней назад, # |   +8 Yet another FST round
 » 11 дней назад, # |   +5
 » 11 дней назад, # | ← Rev. 2 →   +11 Hi, is it ok to submit in the contest code written by somebody else in another contest? For example, submit D2 D using this?
•  » » 11 дней назад, # ^ |   0 Yes
•  » » » 10 дней назад, # ^ |   0 Thanks for the reply. Should we include any information about the author and the source or just copy-paste is ok?
•  » » » » 10 дней назад, # ^ |   0 As far as I know, it depends on the source of the code. You can read about it here
 » 11 дней назад, # |   +29 a c c e p t e d
 » 11 дней назад, # | ← Rev. 2 →   +5 It's too strange that half of people have been hacked by sysjuruo test case after contest. I think that test case should be added in problem test cases !
 » 11 дней назад, # |   0 Hey can anybody help me in finding the difference in these 2 submissions ? One is accepted while the other gets TLE. 64425892 and 64387961. Thank you very much
•  » » 11 дней назад, # ^ |   0 change array size to 10000 instead of 1000
 » 11 дней назад, # |   0 I feel a little stupid, Div 2C. I had the right algorithm and everything. It's just test case 3 is N=1 and I didn't account for that(bc when I search for factors I just assumed the value would have factors that aren't just 1, something to learn out of this).
 » 10 дней назад, # | ← Rev. 3 →   +8 Пробую писать решения на Python3. Подскажите, какие именно там настройки по умолчанию. Так, например, у меня на компе для ввода 3-х целочисленных аргументов нужно сделать вот так: a,b,c=raw_input().split() В то время как на сервере нужно использовать вместо этого input()`И вообще пока работоспособности решений не получается добиться (хотя у меня они запускаются). Вот ссылка на неудачную попытку, которая запускается на моей машине (громоздко, знаю, но я пока экспериментирую).Подскажите, что там не так? Где взять параметры запуска python3? Искал вот здесь: О языках программирования и технических аспектах. Но там для python3 именно та команда, которую я использую у себя на компе.Мой комп: Mac Book Pro, MacOS 10.13.6.
•  » » 10 дней назад, # ^ |   0 raw_input -> input
•  » » » 10 дней назад, # ^ |   0 Странно. Обновил python через brew upgrade, все заработало нормально. Что еще страннее, так это то, что версия у меня как была 3.7.0 так и осталась. Теперь у меня на компьютере он тоже дружит с input().
 » 6 дней назад, # |   0 All the best