Hi guys!
Glad to invite you to Codeforces Round #599 to be held this Nov/06/2019 18:05 (Moscow time)!
My name is Evgeny Vihrov, this is already my 6th Codeforces contest as an author. To introduce myself, I have participated twice in the ACM ICPC Finals (2012, 2014) and currently I am co-coaching teams for the ICPC at the University of Latvia. This is my first solo round, and it took 3.5 years to make! (the last one was #347 with Alex_2oo8).
In this contest you will have to help Ujan deal with his renovation issues. Hopefully, everyone will find a problem matching their taste!
Huge thanks to arsijo for coordinating the preparation of the contest and for the patience with the frequent delays. :) Thanks to Xellos, Origenes, KAN and _overrated_ for generously testing the round. And as always, thanks to MikeMirzayanov for the panem et circenses Codeforces and Polygon systems!
Wish you an exciting round!
UPD1: McDic is joining as a coauthor of the contest (reasons to be revealed later)!
UPD2: Scoring:
Div. 1: 500-1000-1500-2000-2500
Div. 2: 500-500-750-1500-2000-2500
UPD3: Thanks for participating! Congratulations to the winners!!!
Div. 1:
Div. 2:
UPD4: The editorial will be available tomorrow, sorry for the delay. :((
UPD5: The reason behind McDic entering as a coauthor is that one problem was exactly identical to some problem from some Codeforces round. We found out about it only at the last day before the contest, and McDic generously allowed to use his problem.
UPD6: Editorial is posted.
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
good luck :)
I was the fifth person to register for the round.
I am wondering why the first four didn't comment.
The fifth cares enough.
Congratulations man, you have achieved a lot at these young age. You can now join avengers
Its too late for me...
I decided to test rather than participate because it's too early for me...
Please add my handle as co-author in your announcement QAQ
O_o
O_o
McDic orz
Mcdic antiorz
For you he is Mr orz
McDic orz
Enjoy being blocked
O_o
And it's not even Div.1 E :D.
it was 1D :)
qmk orz
Auto comment: topic has been updated by gen (previous revision, new revision, compare).
UPD1: McDic is joining as a coauthor of the contest (reasons to be revealed later)!
No chance of giving the round now! ;D
Who do you want to give the round to and how is it possible to give a round to someone?
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 :))
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.
:(
Ah, I see you are a man of culture as well.
You as well :)
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.
Or maybe you failed and raised to International Master.
You (barely) avoided! Congrats!
How to become a tester for contests and contribute problems??
Get asked.
Click "Propose a contest/problems".
Thank you..
Codeforces problem-setter NeiH
my idol <3
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
Slow work yields fine products,it mights be a good contest.
Looking forward to my first div.1!
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?
I usually follow https://kontests.net/ which keeps me updated on running/future contests on most platforms.
Last round in Codeforces Round #5xx i hope it would be a great closing
So much red color in div2 announcement makes feel worried :| . However, let's hope that this will be balanced.
In this contest you will have to help Ujan deal with his renovation issues.
Hoping that the problem statements will be short and clear!
Is it rated?do not rate me
I want to ask it too.
Is it rated? Yes, It is RATED for all.
So hard to read mehn
How many problems will be in the round?
Will be there multiple-task problems?
How many problems? And what scoring?
Yes, how many problems in round?
6; UPD2: Scoring: Div. 1: 500-1000-1500-2000-2500 Div. 2: 500-500-750-1500-2000-2500
oho!,where no update.
Three problems in Div1.
I can already smell mathforces XD
I will come back whenever I will become pupil
I am back...
Expecting speedoforces after seeing the score distribution.
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.
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.
That was a great contest!
Hopefully gonna be expert for the first time. Just an awesome contest
What hacks did you guys find and what were they about?
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.
How much are you betting?
Yeah I did the same thing
How to solve div2 D? with 920E :))
Or with 190E - Counter Attack, if you are old enough :)
I think it's also similar to 1228D - Complete Tripartite from McDic's last round xd.
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".
rip
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.
The reason I misunderstood it was exactly because the qualifier exists:
These three sentences to me are talking about the integers in box $$$i$$$. Writing
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.
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.
Yeah, it could've been clearer, sorry.
Div2 D Spoiler
Unbalanced round ;__;
How to solve Div1 C?
If n has more than 1 prime factor ans is 1. Else ans is the only prime factor n has.
I think what you are saying is Div2 C not Div1 C
Sorry my mistake, didn't read properly.
what if n is 8?
2
im sorry I just see your comment like number of divisors instead of number of prime factor sorry!
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 :/
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).
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: 64419936
There 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.
My solution for D is different. It will be available on editorial.
I managed to debug and simplify my solution and I think this problem is really beautiful: 64426704
Let'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.
The Idea for the DIV2 — C was somewhat similar to 1245A - Good ol' Numbers Coloring !!!
hakobdilif must have been practicing really hard since Monday!
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;
check at n = 6 the answer should be 1
for 6 answer is 1. your solution prints 2.
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.
try n = 6.
1,3,5 should be the same 2,4,6 should be the same 1,4 should be the same
therefore all should be equal.
Your code says 2.
What was the reason?
...
My problem in this contest is Div1D. Thanks to all people who participated!
It is really a wonderful problem! I did find the pattern but have no time to code — a sad story.
I couldn't find a pattern so I decided to try E instead :P
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 1
Is that Right?
Yeah
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
It passed and I feel so sad, but if it hadnt passed, I would have been sad also. Bad day T^T
Hello, I found a sequence in OEIS for problem C div2. Can anyone say if it relates with the problem? https://oeis.org/A014963
It relates but I am not sure how.
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.
It is exactly the same thing.
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?
okay, im wrong
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.
You have many changes. Just use the compare feature.
Wow, great Div1C! I especially liked the part with restoring the answer in such an elegant form. orz=3
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?
Hm, no, problems from 572 (Div. 1) were ok :) But I will try to write more positive comments in order to increase contribution!
contests like a wine..........
What is test case 35 for Div 2 C.
A number n with a prime factor around 10^9 but this prime factor is not n itself.
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
It was in cf round 120
Its remix of an old song of the beatles.
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).
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.
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 :)
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?
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.
No this is question opposite of Div2D
Can anyone please explain how to solve Div2 B2?
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
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****
You output NO for
1
23
hsezxzwzvnjxvvozhofzvsm
czdcdnwvcdfxerzvxdcjrmz
Whereas solution is possible
orz isaf27
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.
Please explain solution of Div2 C with a proof.
I'm so sad :(
I performed worser but I’m not sad
Poor baby koosaga...
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
Why does it work: 64384395? Weak tests or it can be proved?
I came up with a similiar idea to a similiar problem before XD 34872588
Its 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$$$.
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 :)
OH Benq just had been broken rank 1
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 :(
Even I am facing the same problem.
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):
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.
Thanks a lot!!! It's all clear now :)
Congrats @Benq for #1
Congratulations @Benq and all hard workers :D
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
The same thing in C and AC in D, -157. Love CF scoring distribution.
We will rebuild!
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.
Hmmm, that sounds suspicious, maybe I did some mistake in the complexity analysis, I will check than when I have time. Thanks.
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.
11 hacked
Just 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.
Benq dethroned tourist after years!!! Congrats Benq ! tourist no matter what is your rank we will always love you!
This has happened before, I remember Radewoosh and Um_nik at the top. But it's never lasted long ;)
Don't worry — he'l be coming back for as long as he lives.
Exactly nilesh8757.
Exactly 2000
Exactly 2257
Exactly no change
I did exactly no change twice along with exactly 1400, 1600, 2100 and 2257.
And not to forget that unrated aryanc403 was 1500.
Waiting for that since eternity :(
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
Thank you for the interesting problems! In particular, I quite liked Div1B and Div1C.
Div1 B is somehow the same as 190E and 920E , well, the code is the same at least.
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)
That's a good thing, it means this problem probably won't occur again :D
there's still "check if it is connected" variation.
Validate the input.
Stand and dance at your desk for AC.
Can someone explain the exact proof for Div1-A
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.
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.
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.
Got it.Thanks
[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.
You cannot set i as done before considering all edges of i. Think about the case of the following 0-edges (not 1-edges):
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
I am getting this message for DIV2-B2 in testcase3 64427963
wrong answer Integer parameter [name=m] equals to 10, violates the range [1, 8]
Your algorithm is probably outputing m=10 to a string of size 4.
yes bug in my code thanks BTW
Problem Div 1 D strongly resembles a problem from the 2015 Putnam competition, which we can see here:
https://artofproblemsolving.com/community/c7h1171035p5624365
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
It will be better competition if round-600 will be a global round
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?
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.
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.
Update: even when I set $$$MAGIC$$$ to just $$$5$$$, it passes! 64519426
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)$$$.
It seems that the data is so weak.
I used
std::map<int,int>
in Div1. C but passed the system test.Umm what's weak about that? All numbers are distinct.
Hack #596829.
I used
map.find(x)
to find the id ofx
orx
isn't appeared,but
x
can be larger thanINT_MAX
so that my code can be hacked by:Yet another FST round
Hack Method About div.1C/div.2E
Hi, is it ok to submit in the contest code written by somebody else in another contest? For example, submit D2 D using this?
Yes
Thanks for the reply. Should we include any information about the author and the source or just copy-paste is ok?
As far as I know, it depends on the source of the code. You can read about it here
a c c e p t e d
It's too strange that half of people have been hacked by sys. test case after contest. I think that test case should be added in problem test cases !
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
change array size to 10000 instead of 1000
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).
Пробую писать решения на Python3. Подскажите, какие именно там настройки по умолчанию. Так, например, у меня на компе для ввода 3-х целочисленных аргументов нужно сделать вот так:
В то время как на сервере нужно использовать вместо этого
input()
И вообще пока работоспособности решений не получается добиться (хотя у меня они запускаются). Вот ссылка на неудачную попытку, которая запускается на моей машине (громоздко, знаю, но я пока экспериментирую).
Подскажите, что там не так? Где взять параметры запуска python3? Искал вот здесь: О языках программирования и технических аспектах. Но там для python3 именно та команда, которую я использую у себя на компе.
Мой комп: Mac Book Pro, MacOS 10.13.6.
raw_input -> input