Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### Jeel_Vaishnav's blog

By Jeel_Vaishnav, history, 11 months ago, ,

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 Mar/21/2019 18:35 (Moscow time). 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, V--gLaSsH0ldEr593--V, mohammedehab2002 and Um_nik for testing the problems and _kun_ 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

• +376

 » 11 months ago, # | ← Rev. 3 →   +17 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.
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 You can write comment in THIS BLOG, MikeMirzayanov has noticed the issue
•  » » » 11 months ago, # ^ |   0 thx
•  » » 11 months ago, # ^ |   0 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?
•  » » » 11 months ago, # ^ |   0 Mike said here that he was going to fix it later. He probably hasn’t gotten around to it yet.
 » 11 months ago, # |   -42 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
•  » » 11 months ago, # ^ |   +6 keep faith in bhai ka swag , Ashishgup he will not disappoint u .
•  » » » 11 months ago, # ^ |   -29 nah don't have anything goin for
•  » » 11 months ago, # ^ |   +13 The problem setter's handle has letter '_' in it. This won't be a good contests.
 » 11 months ago, # |   +15 Codeforces round by an Indian coder. I am really exciting for this contest.
•  » » 11 months ago, # ^ |   +38 why so ?
•  » » 11 months ago, # ^ |   +65 I hope someone with the handle name "System_test_failed" reply to this comment
•  » » 11 months ago, # ^ |   +1 Let's hope your code will pass in system testing too. :)
•  » » » 11 months ago, # ^ |   +7 We know what happens in this comment
•  » » 11 months ago, # ^ |   0 Any categorization of people according to their respective nationalities is potentially provocative.
•  » » 11 months ago, # ^ |   -12 excited*learn to speak English before trying to look smart online.
 » 11 months ago, # |   +9 Let's hope for a contest with awesome questions with strong pretests !!!
 » 11 months ago, # |   -12 Squad is Back on the occasion of Holi.Super Excited.
 » 11 months ago, # |   -12 Contest on Holi.Confused whether to be happy or to be sad.
•  » » 11 months ago, # ^ |   +2 Anyway it doesn't matter, You won't be busy hitting colours at 9:05pm (IST) in the night.
 » 11 months ago, # |   +1 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.
•  » » 11 months ago, # ^ |   0 Yes, it has most of it, but you need to download and launch Topcoder Arena
•  » » » 11 months ago, # ^ |   0 Thanks. Is there a separate discussion forum on codeforces or do I ask questions on Round blogs like this?
•  » » » » 11 months ago, # ^ |   +1 You should ask questions in blog entry, or comment on the relevant post
•  » » » 11 months ago, # ^ |   0 where?
 » 11 months ago, # |   +80 .
•  » » 11 months ago, # ^ |   +19 Your own comment: https://codeforces.com/blog/entry/66067?#comment-500584 Contradicts the above comment!
•  » » » 11 months ago, # ^ |   0 Memes are just for fun, not to analyze much :P
•  » » » » 11 months ago, # ^ |   +16 Oh thanks. You opened my eyes.
•  » » » 11 months ago, # ^ |   0 he has anime profile picture so he's an irrelevant individual
•  » » 11 months ago, # ^ |   +31 So many girls in your expectations.
•  » » » 11 months ago, # ^ |   -6 I appreciate your ability to notice the girls, despite of those colors xD
•  » » » » 11 months ago, # ^ | ← Rev. 3 →   0 Thanks. xD
•  » » » » 11 months ago, # ^ |   +5 HAHAHHHHAHHAHAHHHHAHHAHAHHHHAHHAHAHHHHAHHAHAHHHHAH=)))))))))))))))))))))))))))))))))))))))))))))))))))
 » 11 months ago, # |   -22 it is too late for our Chinese students (￣_￣ )
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 11 months ago, # ^ |   +3 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.
 » 11 months ago, # |   +1 Should the pretest be strong enough or not ??
•  » » 11 months ago, # ^ |   0 Ashishgup's contests run smoothly.Hope for this contest too.
•  » » 11 months ago, # ^ |   0 i think pretests should be strong but they should not be too strong otherwise hacking phase will have no meaning !!!
•  » » » 11 months ago, # ^ |   +3 There is no hacking phase...
 » 11 months ago, # |   -7 Happy Holi to everyone.
 » 11 months ago, # | ← Rev. 5 →   -20 I think this contest will be harder than div 3
•  » » 11 months ago, # ^ |   +15 You're a racist.
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 Its not racism, its nazism!
•  » » 11 months ago, # ^ |   +4 Who know, who know)
•  » » 11 months ago, # ^ |   0 Are you from another dimension, where div.2 easier than div.3?
•  » » » 11 months ago, # ^ |   0 it was wrong look one more again
 » 11 months ago, # |   0 I want to add some scores ^_^
 » 11 months ago, # |   +8 Jeel_Vaishnav thanks for contest
 » 11 months ago, # |   +6 Раунд от индуса..........
•  » » 11 months ago, # ^ |   +14 Codechef
 » 11 months ago, # |   0 Hope see some worthy problems this time...
 » 11 months ago, # |   0 Why "fidofido" is the bad word?
 » 11 months ago, # |   0 Woow this round, I will fall) but its doesn't matter, because it will "FUN"!
 » 11 months ago, # |   +17 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.
•  » » 11 months ago, # ^ |   0 What about Firefox? Is the extension working there?
•  » » » 11 months ago, # ^ |   0 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.
 » 11 months ago, # |   -14 Complexity distribution is so balanced
•  » » 11 months ago, # ^ |   -8 lol xx its hard to set a bc
•  » » » 11 months ago, # ^ |   -7 haha , thats why i think why cf doesnt hold div1 rounds frquenttly : reason : div2 problems are more likely equal to div 1 c , d .then why create a seperate rounnd just for div1 e .
 » 11 months ago, # |   +29 Nice Problem D!
 » 11 months ago, # |   +12
•  » » 11 months ago, # ^ |   +1 it just prank bro
 » 11 months ago, # |   -9 What is wrong with the pretest 8 on problem C?
•  » » 11 months ago, # ^ |   +1 I think you have not taken care of adding 10^9+7 while subtracting and then taking mod.
•  » » 11 months ago, # ^ | ← Rev. 2 →   +1 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.
 » 11 months ago, # | ← Rev. 2 →   +24 D is a very cool problem
 » 11 months ago, # | ← Rev. 2 →   +11 Deleted
•  » » 11 months ago, # ^ |   +8 +1
 » 11 months ago, # |   +2 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?
•  » » 11 months ago, # ^ |   0 Yeah, I also faced a couple of times. But it didn't bother me much.
•  » » 11 months ago, # ^ |   +16 You can always try m1.codeforces.com
 » 11 months ago, # |   +116
•  » » 11 months ago, # ^ |   0
•  » » 11 months ago, # ^ |   0 LOL
 » 11 months ago, # |   0 when you don't want to solve graphs problems but cf has another opinion
 » 11 months ago, # |   +4 A lot of people were saved by the authors from being hacked on A due to integer overflow.
 » 11 months ago, # |   -14 PROBLEM C IMPOSSIBLE WHY WA??
•  » » 11 months ago, # ^ |   +36 I think your solution was wrong.
•  » » » 11 months ago, # ^ |   -8 your opinion is wrong. my answer was correct.
 » 11 months ago, # |   +3 who is the setter of problem d ? Ashishgup ?
 » 11 months ago, # |   +34 Million dollar question-How to solve D?
•  » » 11 months ago, # ^ | ← Rev. 2 →   +3 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
 » 11 months ago, # |   +7 Is there O(n*k) solution for C? Or the constraints were there just to bamboozle innocent people like me? :)
•  » » 11 months ago, # ^ |   0 No need to count connectivity of red edges. Merge all nodes with red edges to components and multiply each member count of adjacent components
•  » » 11 months ago, # ^ |   +4 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^kTotal 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.
 » 11 months ago, # |   +30 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.
•  » » 11 months ago, # ^ |   +6 and a minute for me for 3 fail hacks
 » 11 months ago, # |   0 How to solve C?
•  » » 11 months ago, # ^ | ← Rev. 3 →   +3 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
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 a
 » 11 months ago, # |   0 Can someone explain how to solve C
•  » » 11 months ago, # ^ |   0 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
•  » » » 11 months ago, # ^ |   0 Can u please elaborate. I mean how did you get this?
•  » » 11 months ago, # ^ |   0 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.
•  » » » 11 months ago, # ^ |   +3 Got it. Thanks a ton!
 » 11 months ago, # |   +6 How to solve E?
•  » » 11 months ago, # ^ | ← Rev. 2 →   +30 Spoiler1One 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. Spoiler2Now 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)$.
•  » » » 11 months ago, # ^ |   0 Thanks a lot!
•  » » » 11 months ago, # ^ | ← Rev. 8 →   0 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.com/contest/1139/submission/51653759
•  » » » 11 months ago, # ^ |   0 RobeZH, how are you calculating mex using bipartite matching. Can you please explain. Thanks
•  » » » » 11 months ago, # ^ |   +5 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.
•  » » » » » 11 months ago, # ^ |   0 Thanks human!
 » 11 months ago, # |   0 Help me solve problem B, My solution O(n^2) :'(
•  » » 11 months ago, # ^ |   0 You can solve it in a single iteration from n-1 to 0, making it O(n).Check my simple solution.
•  » » » 11 months ago, # ^ |   0 thank you, I misunderstood the problem. I think it don't need to end at n-1,
•  » » » » 11 months ago, # ^ |   0 Oh sad.. Better luck next time :)
•  » » 11 months ago, # ^ |   0 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...
 » 11 months ago, # |   +3 Can some one help me with problem D?I got wrong answer on test 13.Here's the code
 » 11 months ago, # |   +6 Today's problem C, is the first tree problem I have solved till date without traversing (dfs/bfs) the tree.
•  » » 11 months ago, # ^ |   0 How so?
•  » » » 11 months ago, # ^ |   -7 I used UFDS (Union Find Disjoint Set).Check my solution.
•  » » » » 11 months ago, # ^ |   -11 Oh, yes, I forgot about DSU solution.. But that means that you are expert and never solved MST problem, wierd.
•  » » » » » 11 months ago, # ^ |   0 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 :)
•  » » » » » » 11 months ago, # ^ |   0 Can you talk a little about your solution using DSU?
•  » » » » » » » 11 months ago, # ^ |   0 Merge all the nodes connected by red edges into disjoint sets. Find the no of sequences of size 'k' formed by each of the disjoint sets individually and sum all of them. Answer will be n^k -the sum found in step 2. Also keep in mind we need to subtract sequences with all nodes same. Check my solution for more clarity.
•  » » » » » » » » 11 months ago, # ^ |   0 Thank you!
•  » » 11 months ago, # ^ |   +1 In fact, it can be solved by just dfs.
»
11 months ago, # |
0

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;

}

•  » » 11 months ago, # ^ |   0 Dude, you gotta give input to the code they've submitted on which you think that expected outcome will be different from their's output, nor the code. Hope you get it.
•  » » 11 months ago, # ^ |   0 You need a newline at the end of the input.
 » 11 months ago, # |   +12 Nice set of Problems. Three cheers to the authors :DAlready waiting for the Editorial. Please publish them soon :)
 » 11 months ago, # | ← Rev. 3 →   +3 What is the intended solution for D? I managed to pass the pretests with inclusion-exclusion and some optimisations.
•  » » 11 months ago, # ^ |   +2 My solution was calculating the probability of obtaining an array of length n with the gcd of the array(except the last elemnent) as x with ending element y where $x,y \in [1,m]$, $n \in [1,\inf]$ and y is coprime to x.Then, summed up the contributions with a bit of math.
 » 11 months ago, # |   0 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?
•  » » 11 months ago, # ^ |   0 0 is non-negative and 0 is smaller than 4.
•  » » 11 months ago, # ^ |   0 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}.
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 EDIT: Triple ninja-d :) Because 0 is nonnegative?
•  » » 11 months ago, # ^ |   0 non-negative integer means zero is included.{0,1,2,3,...}
•  » » 11 months ago, # ^ |   0 Oh thanks, I'm sleepy :D
 » 11 months ago, # | ← Rev. 2 →   0 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..
•  » » 11 months ago, # ^ |   0 I think the answer is just $n^k-\sum p^k \pmod{1e9+7}$
•  » » » 11 months ago, # ^ |   0 What is the reasoning behind your formula?
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   0 There are n^k paths in total. If there are p nodes in a connected component(>=0 red edges, ==0 black edges), invalid paths are p^k. Sum all such p^k, subtracting this from n^k gives valid paths.
 » 11 months ago, # |   0 oh shiiiiit , i solved problem C but i forgot to Print the number of good sequences modulo 109+7.
 » 11 months ago, # |   0 contest was good !! Happy Holi everyone :)
 » 11 months ago, # |   +17 can E be solved by maximum matching?
•  » » 11 months ago, # ^ |   +5 Yes. I used Kuhn's Algorithm
 » 11 months ago, # |   +3 can prob E solved by bipartite match?
•  » » 11 months ago, # ^ |   0 Yes. But there is tricky part, it is not just reduction to maximal matching problem.
•  » » » 11 months ago, # ^ |   0 so sad...When I recognised how to solve this problem, it was 10 minutes before the conteat ends.
 » 11 months ago, # |   0 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.
•  » » 11 months ago, # ^ |   -24 yup! but petr can solve every question. he solved such hard problems of Atcoder world finals where gennady just solved one . so before listening to twice , listen to his stream
•  » » 11 months ago, # ^ |   +5 I have the same thoughts about C and D))
 » 11 months ago, # |   +38
 » 11 months ago, # | ← Rev. 2 →   0 I made an idea for Problem D and couldn't implement it for 1 hour 30 minutes XD
•  » » 11 months ago, # ^ |   +2 why ?
•  » » » 11 months ago, # ^ | ← Rev. 8 →   +5 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$.
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 Example for $m=10$ all -> null: 1 (1), [2]: 3 (2, 4, 8), [3]: 2 (3, 9), [2, 3]: 1 (6), [2, 5]: 1 (10), [7]: 1 (7), $EX(ALL) = 1 + 0.1 EX(NULL) + 0.3 EX([2]) + 0.2 EX([3]) + 0.1 EX([2, 3]) + 0.1 EX([2, 5]) + 0.1 EX([7])$ [2] -> [2]: 5 (2, 4, 6, 8, 10), null: 5 (1, 3, 5, 7, 9), $EX([2]) = 1 + 0.5 EX([2]) + 0.5 EX(NULL)$ [2, 3] -> [2]: 4 (2, 4, 8, 10), [2, 3]: 1 (6), [3]: 2 (3, 9), null: 3 (1, 5, 7), $EX([2, 3]) = 1 + 0.4 EX([2]) + 0.1 EX([2, 3]) + 0.2 EX([3]) + 0.3 EX(NULL)$ You can find weight of all edges with fast factorization.
•  » » » 11 months ago, # ^ | ← Rev. 3 →   +5 More simple example $m=4$ all -> null: 1 (1), [2]: 2 (2, 4), [3]: 1 (3), $EX(ALL) = 1 + 0.25 EX(NULL) + 0.5 EX([2]) + 0.25 EX([3])$ [2] -> null: 2 (1, 3), [2]: 2 (2, 4), $EX([2]) = 1 + 0.5 EX(NULL) + 0.5 EX([2]) = 2$ [3] -> null: 3 (1, 2, 4), [3]: 1 (3), $EX([3]) = 1 + 0.75 EX(NULL) + 0.25 EX([3]) = \frac{4}{3}$ $EX(ALL) = 1 + 0.25 \times 0 + 0.5 \times 2 + 0.25 \times \frac{4}{3} = \frac{7}{3}$
 » 11 months ago, # |   +3 Thanks for awesome problemset and super fast system testing !I have enjoyed the contest a lot.
 » 11 months ago, # |   0 if a problem submit twice, all accept, which is the score in the problem?
•  » » 11 months ago, # ^ |   +3 The first one will be ignored and you will get penalty of -50 for re-submission.
•  » » » 11 months ago, # ^ |   +1 thanks
 » 11 months ago, # | ← Rev. 6 →   0 Why is this invalid input for hacking A? Why is this N^2 solution passing for A?? Please help.
•  » » 11 months ago, # ^ |   0 Because servers are now upgraded and with compiler optimizations almost around O(10^9) passes in one sec.
•  » » 11 months ago, # ^ |   +3 Probably compiler optimization.
•  » » » 11 months ago, # ^ |   0 Thanks!
•  » » 11 months ago, # ^ | ← Rev. 3 →   +3 The compiler optimizes the increments in the for loop into an addition. After optimization, the complexity is $O(n)$.
•  » » » 11 months ago, # ^ |   0 Thanks!
 » 11 months ago, # |   +1 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...
 » 11 months ago, # |   0 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.
•  » » 11 months ago, # ^ |   0 See my solution: https://codeforces.com/blog/entry/66067?#comment-500828
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 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].
•  » » » 11 months ago, # ^ |   0 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
 » 11 months ago, # |   0 Good contest
 » 11 months ago, # |   0 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 :(
•  » » 11 months ago, # ^ | ← Rev. 4 →   0 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.
•  » » 11 months ago, # ^ | ← Rev. 2 →   +3 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
•  » » » 11 months ago, # ^ |   0 I get it, Thx!It seems that I missed the case that the first element is 1.
 » 11 months ago, # |   +5 When will tutorial be out?
 » 11 months ago, # |   +15 [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: 5 1 2 3 1 1 Should produce 6.
•  » » 11 months ago, # ^ |   +6 I had the same misconception in the beginning, couldn't thing of anything better than O(N^2).
•  » » 11 months ago, # ^ |   +3 Same happened to me. Lost a lot of time for not reading again the problem statement.
•  » » 11 months ago, # ^ |   +3 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.
•  » » » 11 months ago, # ^ |   0 This problem can be solved in O(N).
•  » » » » 11 months ago, # ^ |   0 Could you explain how?
•  » » » » » 11 months ago, # ^ |   0 You run the loop greedily from the last index. Then we take min(Ai,x-1) at the ith index where x is the current maximum. If it becomes 0, then we break the loop and print the final answer.
•  » » » » » » 11 months ago, # ^ |   0 Here is the link to my submission for better understanding. https://codeforces.com/contest/1139/submission/51651782
•  » » » 11 months ago, # ^ |   +3 This can be solved in O(nlog(n)) it is simply LIS dp problem in your variant
•  » » » » 11 months ago, # ^ |   0 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?
•  » » » » » 11 months ago, # ^ | ← Rev. 2 →   0 I was stuck at B because of same understanding. I am also wondering how to solve it in O(n) even though it was not the original problem.
•  » » 11 months ago, # ^ |   0 This should produce 1 not 6
•  » » 11 months ago, # ^ | ← Rev. 3 →   0 Lol , looks like I was not the only one who understood the problem in this way during contest time. I was stuck at this testcase for B (ofcourse because of same assumption as yours)58 6 5 3 4here answer should be 12 by taking 3 from 8 , 4 from 6 , and 5 from 5.can anyone suggest how to solve this problem , where order should be increasing and we have to maximize the sum just like given above testcase.
•  » » » 11 months ago, # ^ |   0 The answer for the above test case will be 10 and not 12 by taking 0 1 2 3 4.
•  » » » » 11 months ago, # ^ |   0 Thank you , but now I am curious about solving this imaginary problem .
•  » » » 11 months ago, # ^ |   0 If we take your approach [3,4,5,0,0], then we see that for j=2 (here 5), and i=3 (here 0) , Aj is not less than Ai as 5>0, and neither it is 0. Hence, we are not satisfying any of the conditions.
 » 11 months ago, # |   0 I liked the C priblem a lot. At first I found it difficult to solve it, but after that i understood it was easy.
 » 11 months ago, # |   +11 Please publish the editorial as early as possible. Can't wait to see the solution of problem D, E and F!
 » 11 months ago, # |   +8 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.
 » 11 months ago, # |   0 How did (n*n) solution got accepted in Q A? Link https://codeforces.com/contest/1139/submission/51625556
•  » » 11 months ago, # ^ |   0 It's magic of GNU C++
•  » » 11 months ago, # ^ |   0 Maybe compiler optimization
•  » » 11 months ago, # ^ |   +12 for (int j = 0; j <= i; j++){ ans++; } The above block is optimized to ans += i + 1; you can see that here.
•  » » 11 months ago, # ^ |   0 compiler optimization + server upgrades !!!
 » 11 months ago, # | ← Rev. 2 →   +8 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?
•  » » 11 months ago, # ^ | ← Rev. 2 →   +8 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)$?.
•  » » » 11 months ago, # ^ |   +8 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.
 » 11 months ago, # |   0 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?
•  » » 11 months ago, # ^ |   0 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!
•  » » » 11 months ago, # ^ |   0 Thanks buddy. Bad luck today indeed.
 » 11 months ago, # |   0 Why did my Submission 51646792 fail? Does it have something to do with modular arithmetic?
 » 11 months ago, # |   0 I am getting WA on pretest 10 in Problem B. The longest testcase, I suppose. Link to my submission. Please Help.
•  » » 11 months ago, # ^ |   0 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.com/contest/1139/submission/51652989
•  » » » 11 months ago, # ^ |   0 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.
•  » » » » 11 months ago, # ^ |   0 You don’t need to. As long as sum is long, it will pass. See https://codeforces.com/contest/1139/submission/51653644
•  » » » » » 11 months ago, # ^ |   0 Thanks Redux. You came as a savior today. Getting the logic but failing at implementation tired me out today
 » 11 months ago, # |   0 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.
 » 11 months ago, # | ← Rev. 2 →   0 My solution for C runs in O(nk) time and it still TLEs, does anyone know why it exceeds the time limithttps://codeforces.com/contest/1139/submission/51649583edit: 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 thathttps://codeforces.com/contest/1139/submission/51920785
 » 11 months ago, # |   0 In Problem D how to find no of possible ways to get an array of length k with gcd say x
•  » » 11 months ago, # ^ |   0 You need to get needed prime divisors and avoided prime divisors. That's the key.
 » 11 months ago, # |   0 benim neden degerlendirmem dusuyorki bir problem cozdum ve bir kez bile yalnis gondermedim puanym 844 ve 24 degerlendirmemi kaybetdim bunun nedenini bana soyliyebilirmisiniz lutfan
 » 11 months ago, # |   +3 Hello, Div.2, my old friendI've come to solve your tasks again...
 » 11 months ago, # |   0 I have a solution to Problem B but cannot pass the pretest 10 (very large values).could anyone help me to find out flaws in my solution?The basic idea is to find the most right tangent line of the curve of $a_i$, it treats the final solution as two parts: an increasing straight line with slope rate k=1. values after the last joint point. We can get the answer easily by adding those two parts together.here is my solution： https://codeforces.com/contest/1139/submission/51664626
 » 11 months ago, # |   0 In problem D. Why the example 3 has the output 3333333338?