Hi everyone!
I would like to invite you to my second Codeforces round, which I have created with my friends Ashishgup and Vivek1998299.
With that said, I bring to your attention our new Codeforces Round 548 (Div. 2) that will take place on 21.03.2019 18:35 (Московское время). If your rating is less than 2100, this round will be rated for you; otherwise, you can participate out of competition.
I would like to thank Ashishgup and Vivek1998299 for their help with preparing problems, vintage_Vlad_Makeev, mohammedehab2002 and Um_nik for testing the problems and cdkrot for coordinating our round. I would also like to thank MikeMirzayanov for the awesome Codeforces and Polygon platforms.
You will be given 6 problems and 2 hours to solve them. Scoring distribution will be announced later.
Good luck! :D
UPD1: Shortly after the contest, we'll be on the community Discord server to discuss the tasks.
UPD2: Score distribution is — 500-1000-1750-2250-2500-3000
UPD3: Editorial
Is there something wrong with the registration system before? I noticed that it said the contest will be rated for people whose rating is under 1900 on the registration page when I registered for this contest.The Candidate Masters who registered that time have the sign of out of competition. What should we do now? Should we register again or the administrator will help us fix the bug? Please fix it, thanks and wish all the participants have a good contest and get a good rating.
You can write comment in THIS BLOG, MikeMirzayanov has noticed the issue
thx
I was registered out of competition and had to re-register. I am not sure if everybody noticed that — is there a way to automatically transfer all out-of-comp candidate masters to normal registration?
Mike said here that he was going to fix it later. He probably hasn’t gotten around to it yet.
oh god PLEASE no useless math so we can participate .... i know we don't matter for you anymore but make an effort for us and don't bullshit us.
but i don't have much hope in this one as the problem setter is from india . oh well
keep faith in bhai ka swag , Ashishgup he will not disappoint u .
nah don't have anything goin for
The problem setter's handle has letter '_' in it. This won't be a good contests.
Codeforces round by an Indian coder. I am really exciting for this contest.
why so ?
I hope someone with the handle name "System_test_failed" reply to this comment
Let's hope your code will pass in system testing too. :)
We know what happens in this comment
Any categorization of people according to their respective nationalities is potentially provocative.
excited*
learn to speak English before trying to look smart online.
Let's hope for a contest with awesome questions with strong pretests !!!
Squad is Back on the occasion of Holi.
Super Excited.
Contest on Holi.
Confused whether to be happy or to be sad.
Anyway it doesn't matter, You won't be busy hitting colours at 9:05pm (IST) in the night.
Is there a separate discussion forum for Codeforces or do people have to write blog entries?
Does anyone know if Topcoder has the same functionality as Codeforces like being able to solve past problems, submit solutions for testing, viewing other people's solutions filtered by language sorted by executions time, etc.? Topcoder website seems like a disaster. I would ask this in the Topcoder forum except I can't find a way to make a post there and there customer support seems unable to help. Thanks.
Yes, it has most of it, but you need to download and launch Topcoder Arena
Thanks. Is there a separate discussion forum on codeforces or do I ask questions on Round blogs like this?
You should ask questions in blog entry, or comment on the relevant post
.
Your own comment: https://codeforces.net/blog/entry/66067?#comment-500584 Contradicts the above comment!
Memes are just for fun, not to analyze much :P
Oh thanks. You opened my eyes.
he has anime profile picture so he's an irrelevant individual
So many girls in your expectations.
I appreciate your ability to notice the girls, despite of those colors xD
Thanks. xD
HAHAHHHHAHHAHAHHHHAHHAHAHHHHAHHAHAHHHHAHHAHAHHHHAH=)))))))))))))))))))))))))))))))))))))))))))))))))))
it is too late for our Chinese students ( ̄_ ̄ )
Because it needs to consider the time in Russia and the time in the author's country. It is late for Chinese students sometimes, but whether you participate in it or not still depends on you. You can balance your study, sleep and the training and the contests. If you really want to join the contest, just do it. If you are worried about the time and will not join it, you still can virtual participate or just practice the problems when you are free.
There is no doubt that I will participate in it,because I really enjoy it.However it just goes against my original intention of wanting a healthy life. :D thanks for your reply.
Should the pretest be strong enough or not ??
Ashishgup's contests run smoothly.
Hope for this contest too.
i think pretests should be strong but they should not be too strong otherwise hacking phase will have no meaning !!!
There is no hacking phase...
I think this contest will be harder than div 3
You're a racist.
Its not racism, its nazism!
Who know, who know)
Are you from another dimension, where div.2 easier than div.3?
I want to add some scores ^_^
Jeel_Vaishnav thanks for contest
Раунд от индуса..........
Codechef
Why "fidofido" is the bad word?
Woow this round, I will fall) but its doesn't matter, because it will "FUN"!
Hi guys! Unfortunately CF-Predictor doesn't work in last version of Chrome. They changed Cross-Origin Read Blocking policy and my extension can't send requests to the backend anymore. But the actual problem is that I can't update code and fix issue ASAP. I recently started working in Google and they have pretty strict policy about open source projects. I'll try to come up with some solution, but sorry terms are unknown.
Current solution is to use website version.
What about Firefox? Is the extension working there?
Yes, I suppose so. It even can works in Chrome if it doesn't updated yet.
You can just open any past contest and if you see additional column with rating change, extension is working.
Complexity distribution is so balanced
Nice Problem D!
it just prank bro
What is wrong with the pretest 8 on problem C?
I think you have not taken care of adding 10^9+7 while subtracting and then taking mod.
you might be doing (total-calculated_value)%mod, which gave WA to me , but using (((total-calcualted_value)%mod )+mod)%mod which gave AC,hope it may help.
D is a very cool problem
.
+1
During the contest, I got alot of "codeforces is temporarily unavailable" page and the problem was taking a lot in order to show anyone face the same issue like me?
You can always try m1.codeforces.com
zh_zhumash xD
when you don't want to solve graphs problems but cf has another opinion
A lot of people were saved by the authors from being hacked on A due to integer overflow.
PROBLEM C IMPOSSIBLE WHY WA??
I think your solution was wrong.
your opinion is wrong. my answer was correct.
who is the setter of problem d ? Ashishgup ?
Million dollar question-How to solve D?
for each number g you have to find 3 things:
a = how many numbers are relatively prime to g within range [1,m]
b = how many numbers will have gcd g again when paired with g within range [1,m]
c = how many numbers have gcd<g when paired with g. (This was the hardest part for me in this problem)
The rest is calculating E(g) with a bit of knowledge of probability
My code: 51649595
Is there O(n*k) solution for C? Or the constraints were there just to bamboozle innocent people like me? :)
No need to count connectivity of red edges. Merge all nodes with red edges to components and multiply each member count of adjacent components
Just a linear time solution. O(n)
Count the number of bad strings, and subtract them from total (n^k) to get the final answer.
Think how you can form a bad string, which doesn't traverse through any of the black edges. For simplicity remove the black edges from the graph and then, you'll get some connected components.
To Form a Bad string of length K, all the nodes should be from the same component. If you take nodes from different components, they must have to traverse through a black edge and hence it will not remain a "bad string".
Now suppose cnt = no. of nodes in a connected component. Then no. of bad strings formed by nodes of that particular connected component is = cnt^k
Total no. of bad strings = sum of bad strings of each component.
Note : If the difference is less than 0 after taking modulus with 1e9+7, Add 1e9+7 to make it positive.
One minute silence for the three Indians: alwaysGREEEN, Abhinaviitbhu and imhemant.
Who were the only people to get hacked today, on the occasion of holi.
and a minute for me for 3 fail hacks
How to solve C?
First, notice that this is an inclusion-exclusion type of problem. So the answer will be something like: all possible permutations — all impossible ones. After realizing that, you'll soon notice that all the impossible ones are the collection of nodes that don't have any black edge at all.
Hence, we can simply isolate collection of nodes by using disjoint set. Simply merge when the edge is red and skip the black edge. When you have got a bunch of disjoint sets, you can calculate how many permutations can be constructed from a disjoint set of size x. pow(x, k)
The total answer would be pow(k, n) — (for each disjoint set of size x, pow(x, k))
Solution
Can someone explain how to solve C
lets do tree with only RED . we have forest and answer is n ** k — a1 ** k — .. — af ** k, whee ai number of vertexes in i tree
Count how many sequences are bad (not good) and subtract it from N^K. If we make the graph only with red edges, for each connected component with size X we will get X^K bad sequences from this component. Sum of bad sequences for each component will give total number of bad sequences. It's not possible to get any more bad sequence because merging any two component would need black edge which we can't use in bad sequences.
Got it. Thanks a ton!
How to solve E?
One can see that we are matching the clubs with a certain range of potentials. If there are no deletion, we can run any bipartite matching algorithm and meanwhie keep the maximum mex.
Now that there are deletions, a smart way to get around this is build the graph after all deletion and add edges to it in reverse order. In this way, we are only adding edges, and then we can check whether there are new augmenting paths in the new graph.
The amortized complexity will be $$$O(VE)$$$.
Thanks a lot!
Is this the right approach?
We start with a bipartite graph with 0 potential vertices on the right. We will first add all persons that were never removed to the clubs on the left. We will process the days in reverse order. We will add the person that was removed on this day to our bipartite graph after we have processed this day. As long as the bipartite matching is maximal, we add the first available potential (first 0, then 1, then 2, etc) to the bipartite graph and rerun the matching algorithm. When the matching is not maximal anymore, the final value we tried to add is our MEX value for this day. The MEX can only increase during this process, so we never have to remove added potentials anymore in the graph.
Edit: solved while processing the days in chronological order with a similar approach as described above (but instead of adding potentials, we remove them when the matching isn't maximal). https://codeforces.net/contest/1139/submission/51653759
RobeZH, how are you calculating mex using bipartite matching. Can you please explain. Thanks
First we build a graph to check that whether the mex can be 1 (, more specifically, say we put the potentials on the right hand side of the bipartite graph, we build it such that only potential 0 is connected to the sink, and see if there is a perfect matching). If yes, we incrementally build the graph to check that whether the mex can be 2, and so on. If no, we know that the previous number is the mex for the current set of people.
Thanks human!
Help me solve problem B, My solution O(n^2) :'(
You can solve it in a single iteration from n-1 to 0, making it O(n).
Check my simple solution.
thank you, I misunderstood the problem. I think it don't need to end at n-1,
Oh sad.. Better luck next time :)
Think greedy.
Use the maximum possible number of chocolates from a_n and with considering the picks use the maximum possible number of chocolates from a_n-1 and so on...
Can some one help me with problem D?
I got wrong answer on test 13.
Here's the code
Today's problem C, is the first tree problem I have solved till date without traversing (dfs/bfs) the tree.
How so?
I used UFDS (Union Find Disjoint Set).
Check my solution.
Oh, yes, I forgot about DSU solution.. But that means that you are expert and never solved MST problem, wierd.
I am talking about exclusive tree problems usually given in cf.
I believe MST is found on a given general graph.
Or maybe I just don't remember. Thanks for judging me :)
Can you talk a little about your solution using DSU?
Check my solution for more clarity.
In fact, it can be solved by just dfs.
How to write code to hack others? I use this code to hack problem B, why the return is "Invaild input"?
include
using namespace std; int main() { int n=100000; printf("%d\n",n); for(int j=n;j>=1;j--){ int t=10000000-j+1; if(j==n){ printf("%d",t); } else printf(" %d",t); } return 0;
}
You need a newline at the end of the input.
Nice set of Problems. Three cheers to the authors :D
Already waiting for the Editorial. Please publish them soon :)
What is the intended solution for D? I managed to pass the pretests with inclusion-exclusion and some optimisations.
My solution was calculating the probability of obtaining an array of length
n
with the gcd of the array(except the last elemnent) asx
with ending elementy
where $$$x,y \in [1,m]$$$, $$$ n \in [1,\inf]$$$ andy
is coprime tox
.Then, summed up the contributions with a bit of math.
Problem E: The mex of the multiset S is the smallest non-negative integer that is not present in S. For example, the mex of {1,2,3} is 0. Why the mex of {1, 2, 3} is not 4?
0 is non-negative and 0 is smaller than 4.
0 is a non-negative integer. The MEX of {1,2,3} is 0, because 0 is not in the set. It would be 4 if the set was {0,1,2,3}.
EDIT: Triple ninja-d :) Because 0 is nonnegative?
non-negative integer means zero is included.
{0,1,2,3,...}
Oh thanks, I'm sleepy :D
Problem C: Count connected components of red nodes. If a connected component has p nodes. Impossible paths are p^k, sum similarly for all connected components. Finally subtract this value from n^k, also subtract no of nodes that have zero red edges. Is my idea anywhere close at least? I couldn't manage the time to implement though..
I think the answer is just $$$n^k-\sum p^k \pmod{1e9+7}$$$
can E be solved by maximum matching?
Yes. I used Kuhn's Algorithm
can prob E solved by bipartite match?
Yes. But there is tricky part, it is not just reduction to maximal matching problem.
so sad...
When I recognised how to solve this problem, it was 10 minutes before the conteat ends.
It was a very unbalanced round. The jump in difficulty from B to C was to great. The problems were interesting but I felt like there should have been a problem between B and C.
I have the same thoughts about C and D))
I made an idea for Problem D and couldn't implement it for 1 hour 30 minutes XD
why ?
My idea is very hard to implement(at least for me).
My solution idea for D:
We can define the weighted/directed graph to solve this problem. Each node has distinct set of primes. This means the prime divisors of greatest common divisor made by array $$$a$$$ so far. For example, if the $$$a = [24, 30, 18]$$$ then the state of $$$a$$$ is $$$(2, 3)$$$. Of course there can be self-looping edge exist.
There is a special node called all, this node contains all prime numbers in $$$[1, m]$$$. For all non-special nodes there is an edge exists directed from all to that node.
Calculate weight of all each edges, then you can solve the equation such like; $$$EX(node) = 1 + \sum_{\text{all neighbors}}^{} EX(neighbor) * weight$$$ where $$$EX$$$ means the expectation of length of sequence started from that state. There is an exception; $$$EX(NULL) = 0$$$.
Example for $$$m=10$$$
You can find weight of all edges with fast factorization.
More simple example $$$m=4$$$
Thanks for awesome problemset and super fast system testing !
I have enjoyed the contest a lot.
if a problem submit twice, all accept, which is the score in the problem?
The first one will be ignored and you will get penalty of -50 for re-submission.
thanks
Why is this invalid input for hacking A? Why is this N^2 solution passing for A?? Please help.
Because servers are now upgraded and with compiler optimizations almost around O(10^9) passes in one sec.
Probably compiler optimization.
Thanks!
The compiler optimizes the increments in the for loop into an addition. After optimization, the complexity is $$$O(n)$$$.
Thanks!
I was kind of confused by problem B, it implies you can decided to buy a chocolate or not, but in reality you always buy a certain chocolate, even if 0 times...
Can anybody tell me how to solve problem D? I was thinking to solve it like E[len]=E[number of 1's]+E[number of 2's]+E[number of 3's]+------E[number of n's] in the sequence but could not able to solve it.
See my solution: https://codeforces.net/blog/entry/66067?#comment-500828
No. of N-length arrays: Sum(C[i] ^ N) / m ^ N. ( 1 <= N <= ...)
C[i]: Count of multiples of C[i] <= m. (Make sure that we do not re-count multiples, C[x] -= C[y])
If you re-arrange 1st statement, you can get sum of infinite GPs for each C[i].
Sum the answer for all C[i].
You are taking C[i]^N for length N but it contains all the elements that have GCD>1 so length will no longer be N and it will be more than N
In problem D, can someone explain the solution with mobius function?
My solution is $$$\sum_{i=1}^{\infty} i*q^i = q / (q-1)^2$$$, and the answer is $$$\sum_{i=1}^{m}mu[i] * q / (q-1)^2$$$, $$$q=[m/i]/m(i=1\dots m)$$$, but it is wrong :(
Because you count something twice or more. Let call the first expression is f(q), then you want f(i) is the answer with some first element have gcd() = i, but you also count the other with gcd = 2i, 3i, ... So you need to subtract f(2i), f(3i) to get the right answer.
Actually, what you're looking for is $$$\sum_{i=1}^{\infty} (i+1)*q^i*(1-q)=\frac{q*(2-q)}{1-q}$$$(you need to factor out the $$$1-q$$$ for wolfram alpha to give you the result: https://www.wolframalpha.com/input/?i=(sum+of+i+from+1+to+inf+(i%2B1)*a%5Ei)*(1-a)*1 . Make sure to add $$$\frac{1}{m}$$$ at the end for the special case of length 1. AC code: 51651931
I get it, Thx!
It seems that I missed the case that the first element is 1.
When will tutorial be out?
[Problem B] I just realized I didn’t understand the task properly. But now I wonder if there is a nice algorithm to solve the version of this problem that I had in mind.
So the condition is such that the number of chocolates we buy has to be a strictly increasing segment. In particular we are allowed to leave some types of chocolates on the right side. For example:
Should produce 6.
I had the same misconception in the beginning, couldn't thing of anything better than O(N^2).
Same happened to me. Lost a lot of time for not reading again the problem statement.
Couldn't solve it because I understood the same.. After almost 2 hours thinking i'm pretty sure there isn't anything better than N^2.
This problem can be solved in O(N).
Could you explain how?
This can be solved in O(nlog(n)) it is simply LIS dp problem in your variant
I don't know if we are understanding the same problem.
For input array = {1 1 4 3 5 1} result would be 11 (0 1 2 3 5 0).
How would you solve it with LIS?
I liked the C priblem a lot. At first I found it difficult to solve it, but after that i understood it was easy.
Please publish the editorial as early as possible. Can't wait to see the solution of problem D, E and F!
Thanx. Nice problems. It is good that in pretests exists test for TLE, at least for E. There is happen that seems like optimization do not need, but pretest got TLE and one saves time for testing and will not get disappointment after contest.
How did (n*n) solution got accepted in Q A? Link https://codeforces.net/contest/1139/submission/51625556
It's magic of GNU C++
Maybe compiler optimization
The above block is optimized to
ans += i + 1;
you can see that here.compiler optimization + server upgrades !!!
I know that E's Solution is Khun's algo with reversing queries, but I am interested to know was there any direct HopcraftKarp Solutions that passed it should be $$$O(N^2sqrtN)$$$, since the number of edges <= 5000 and the number of nodes <= 5000 that totals to $$$\cdot{2*10^9}$$$ operations approx.
but as I don't really understand how HopcraftKarp works I am not sure can it be optimized to pass?
I think if we use Hopcroft Karp we need to binary search on the answer and so we attain complexity of $$$O(N^2 \cdot sqrtN \cdot logN)$$$. Can you explain your approach of using Hopcroft Karp and attaining complexity $$$O(N^2 \cdot sqrtN)$$$?.
Sorry, apparently I really didn't understand Hopcroft Karp that well, a friend of mine explained it to me afterward and told me that a simple $$$O(N^2sqrtN)$$$ Hopcroft Karp is not doable.
I am getting TLE on pretest 6 in Problem A. Please help. Link to the submission. In this code I'm taking each substring and just checking the last digit is even or not. Is it not one of the right way to do so?
Your complexity of solution is O(n^2) and I guess java is slower than c++ and the multiplier for java might not be enough for an O(n^2) to pass but in c++ it is, just bad luck i assume!
Why did my Submission 51646792 fail? Does it have something to do with modular arithmetic?
I am getting WA on pretest 10 in Problem B. The longest testcase, I suppose. Link to my submission. Please Help.
Learn the range of different data types in your preferred language.
int can only handle values up to about 2 billion.
Using long passes. See https://codeforces.net/contest/1139/submission/51652989
Why do i need to make the ans[] in the above code as long too? I tried it with sum as long, but not with ans array as long.
You don’t need to. As long as sum is long, it will pass. See https://codeforces.net/contest/1139/submission/51653644
Can someone check if my solution for E is correct? It's not maximum matching.
First, I find max mex for the given situation without considering updates. Here's how I do that: I go from $$$0$$$ to as far as I can go by randomly picking a club which has a member of the required potential. When I choose the $$$i$$$'th club for potential $$$j$$$, I make a directed edge from all other clubs who have a member with potential $$$j$$$ to $$$i$$$. Now, if I get stuck at some potential k, I will bfs from the unused clubs to find a club which has a member with potential $$$k$$$. Now, if the path to this club is like $$$p_{x}$$$ -> $$$p_{a_{1}}$$$ -> ... -> $$$p_{y}$$$, where $$$p_{x}$$$ is the unused club and $$$p_{y}$$$ has a member with potential $$$k$$$, I can replace $$$p_{a_{1}}$$$ with $$$p_{x}$$$, and $$$p_{a_{2}}$$$ with $$$p_{a_{1}}$$$ and so on. After this I update the edges of the graph as required. By the end, I will find the max mex for the given situation.
Now, for updates: First notice that the max mex can only decrease or remain same. Now, I maintain the reverse of the graph I mentioned above, if a member from club $$$i$$$ is chosen for potential $$$j$$$, then I make a edge from club $$$i$$$ to every other club which also has a member with potential $$$j$$$. Now, for each member which leaves, we see if we were using this member in our chosen max mex, if not, we do nothing. If yes, then we bfs from this club to either find a club which is unused right now (in which case max mex remains same) or we find a used club from which we have taken a member with the highest potential (in this case max mex becomes this new potential). In both cases we update the entire graph again as required.
My solution for C runs in O(nk) time and it still TLEs, does anyone know why it exceeds the time limit
https://codeforces.net/contest/1139/submission/51649583
edit: I found the reason: apparently running a DFS has a much larger constant than I thought. I ended up passing by precomputing the DFS order and then doing DP directly on that
https://codeforces.net/contest/1139/submission/51920785
In Problem D how to find no of possible ways to get an array of length k with gcd say x
You need to get needed prime divisors and avoided prime divisors. That's the key.
Hello, Div.2, my old friend
I've come to solve your tasks again...