By PikMike, history, 11 months ago, translation, ,

Hello Codeforces!

On Jul/14/2018 17:35 (Moscow time) Educational Codeforces Round 47 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Ivan BledDest Androsov, Vladimir Vovuh Petrov, Maksim Ne0n25 Mescheryakov, Aslan ag2cidk Tamaev and me.

Good luck to all participants!

I also have a message from our partner, Harbour.Space University:

Hi Codeforces!

We want to remind everyone that the Hello Barcelona Programming Bootcamp is right around the corner, and we’d love to see you there!

Our boot camp will once again feature the all-time greats Mike MikeMirzayanov Mirzayanov, Andrey andrewzta Stankevich, Michael Endagorion Tikhomirov, Gleb GlebsHP Evstropov, Artem VArtem Vasilyev, Ivan ifsmirnov Smirnov and other world renowned Russian coaches to train the participants.

We would also like to extend a welcome to some of the newest teams to join us from Colorado School of Mines, University of British Columbia and Reykjavík University.

Be sure to register before August 1st so everyone has time to get visas if needed, and of course for the Early Bird Discount of 15% or the Loyalty Discount* of 20% off registration for the boot camp!

*The loyalty discount is offered to universities and individual participants that took part in Hello Barcelona Bootcamps and Moscow Workshops ICPC.

You can ask any questions by email: hello@harbour.space

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 e-pluszak 7 159
2 hohomu 7 274
3 guille 7 338
5 waynetuinfor 6 148

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 689:-132
2 2014CAIS01 91:-13
3 Marcel_Ib 20:-1
4 Ali_Pi 16:-3
5 20180616sG 15:-3
978 successful hacks and 798 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A AuroraGarden 0:01
B eddy1021 0:05
C e-pluszak 0:09
D hmc 0:09
E Roundgod 0:19
G chemthan 0:28

• +168

 » 11 months ago, # |   +72 Would you consider making the hacking time 6 hours instead of 12 hours as it has been discussed before.
 » 11 months ago, # |   +33 No weak pretest plz.
 » 11 months ago, # |   +31 Can the contest be rescheduled as it clashes with the FIFA WC 3rd Place match tomorrow? Probably delay it by 1 or 1.5 hours?
•  » » 11 months ago, # ^ |   +63 Will provide a nice breathing space after the AtCoder Grand Contest that ends 5 minutes before this contest too
•  » » 11 months ago, # ^ |   -17 NO. Then it will clash with HackerEarth contest.
•  » » » 11 months ago, # ^ |   -12 The hackerearth contest is already clashing with this one.
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   -6 Yes. it is. but just for half an hour.In the other case it would completely overlap with it.
•  » » 11 months ago, # ^ |   0 Ya Plz
 » 11 months ago, # |   +61 How to solve div 2a?
•  » » 11 months ago, # ^ |   +43 We got a guy from future here, peeps.
•  » » 11 months ago, # ^ |   +21 It is not so easy, that we can solve it without a statement
•  » » » 11 months ago, # ^ |   +12 sorry, I thought I was writing in the previous contest :(
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   +4 however you got +30 upvotes :D
•  » » 11 months ago, # ^ |   0 Spoiler...Use DP + Segment Trees !!
•  » » 11 months ago, # ^ |   -9 just do whatever you want. you can use some convex hull tricks, or persistent data structures, just do it :) hahah... dp+convexHull+persistent seg tree = dexHustent tree :)
 » 11 months ago, # |   -6 why educational codeforces rated only for div 2 !!! why not div 1 also ??
•  » » 11 months ago, # ^ | ← Rev. 2 →   -6 The goal of educational rounds is to practice and educate, rather than to compete. You can read the details in this post dedicated to them. In short:" Not only problems, but also exercises can be used Useful ideas will be reused to introduce them to a wider range of participants, even if they are well-known. Often the formal text of the statements "
 » 11 months ago, # |   0 The penalty for WA is 20 or 10?
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 Should be 20. I believe, this change will only affect Div.3 rounds. UPD: I'm wrong, check later comments.
•  » » » » 11 months ago, # ^ |   +27 Okay, sorry for misleading information then, I wasn't notified of it. Then it's 10 minutes.
 » 11 months ago, # |   +3 I can watch Hataraku Saibou right after this contest! It's great!
•  » » 11 months ago, # ^ |   +3 My hero academia too
•  » » 11 months ago, # ^ |   +3 Now I can enjoy it.
•  » » » 11 months ago, # ^ |   0 Enjoy bro cells at work
 » 11 months ago, # |   +1 Educational WorldCupForces Round!
»
11 months ago, # |
-32

# ?detaR ti sI

»
11 months ago, # |
-29

# ?detaR tI sI

 » 11 months ago, # |   +8 Minimize hacking phase to 6 hours
 » 11 months ago, # |   +14
•  » » 11 months ago, # ^ |   0 i lost both the match and my rating
•  » » » 11 months ago, # ^ |   0 so did I
 » 11 months ago, # |   +1 PikMike What will be the penalty in this round, 10 or 20 ?
•  » » 11 months ago, # ^ |   +1 It is 10,read this comments.
 » 11 months ago, # |   +4 its reated? lol OALollolol xDXDxD :)))))))))))))))))))
 » 11 months ago, # |   -9 wish me luck:)
•  » » 11 months ago, # ^ |   -6 good luck bro <3and all other ..
 » 11 months ago, # |   -16 i love 2 things in this world ::1 — football2 — codeforceswhy you do that ? my heart will break down !
 » 11 months ago, # |   -42 btw :: How to solve div2 D,E?in this contest yes .
•  » » 11 months ago, # ^ | ← Rev. 2 →   +1 Not sure if this comment meant to gain upvote like before or to gain more downvote so he could be on the last page of contribution rank.Edit : he's already on the last page !
•  » » » 11 months ago, # ^ |   +1 Maybe he is trying to be on the last place.
 » 11 months ago, # |   -23 Why Codeforces (Contest writer) doesn't mention directly that this Educational Round will be rated for Div 3 participants also? As they mention "Rated for Div 2" directly.
•  » » 11 months ago, # ^ |   +36 ¯\_(ツ)_/¯
•  » » 11 months ago, # ^ |   +22 div3 is a subset of div2 maybe that's why who knows
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +8 IMHO whether the round is rated and for which divisions should be an attribute of the contest like "Writers", "Start" and "Length", and not be part of the "Name" of the contest.
•  » » 11 months ago, # ^ |   +1 Using the same logic, Why he didn't mention that it is unrated for Div. 1 participants also? Maybe because they are smart enough to know the contest is unrated for them.
 » 11 months ago, # |   +3 Penalty Time??
•  » » 11 months ago, # ^ |   +15 10
 » 11 months ago, # |   +2 When you want to take part badly but your laptop's display broke 3 hours before the contest :(
 » 11 months ago, # |   -66 problem E is too poisonous,i mod 10^9+7 instead of 998244353.
•  » » 11 months ago, # ^ |   +38 Well, it's even somewhat bold in the statement. And also repeated a couple of times. Should be noticeable.
•  » » » 11 months ago, # ^ |   0 But why though? Why did you choose this mod?
•  » » » » 11 months ago, # ^ |   +41 Well, there are two reasons.The first is that nowadays problemsetters tend to choose this modulo for all problems (not only ones requiring modular FFT) so that people don't see this modulo and instantly react like "Ok, we need a convolution here".And the second reason is that, when I started preparing this problem, I didn't understand that there is a simple math solution, and tried to solve it with online modular FFT instead xD
•  » » » » » 11 months ago, # ^ |   +1 Makes sense now. Thanks =D
•  » » » » » 11 months ago, # ^ |   +8 Hey why wouldn't you use mod 10^9+7 for fft as well?
 » 11 months ago, # | ← Rev. 2 →   -21 OEIS is your friend for Problem E : linkEdit: this sequence gives the number of occurences of each element in reverse order (last one occurs 1, second to last 3 times etc.)
•  » » 11 months ago, # ^ |   +6 aah shit
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 But 40343744 ??? I think that problem E require another sequence 40349064UPD: sorry, my wrong, I just forgot about modulo
•  » » 11 months ago, # ^ |   +5 Not sure why this is being downvoted, I found the exact same sequence online during the contest.A fairly common problem solving technique: 1) write naive solution 2) find pattern (possibly look online) 3) hard code in formula
 » 11 months ago, # |   0 What is the 5th test case for problem C?and someone also give me some hard test case for this problem.
•  » » 11 months ago, # ^ | ← Rev. 2 →   +1 It's a greedy problem.
•  » » » 11 months ago, # ^ |   +1 This one is for B.
•  » » » » 11 months ago, # ^ |   +2 Sorry, Updated!!
•  » » 11 months ago, # ^ |   +2 In your code, "sum" overflows for very large N.
•  » » » 11 months ago, # ^ |   0 JovanBnow i have also tried by long long int instead of double.but i am getting WA at 5th test case :(
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   +4 N should be long long, because even if sum is long long, (N*(N+1))/2 is int, and can go up to 10^10, which is bigger than the limit for int
•  » » » » » 11 months ago, # ^ |   0 Thanks bro
•  » » » » 11 months ago, # ^ |   0 Make n also long long int. You have ll sum = (n*(n+1))/2 but n is an int — the overflow will happen first so sum will end up with a weird value for large enough n.
•  » » 11 months ago, # ^ |   0 Small datatypes may overflow, so long double should fix the problem.
 » 11 months ago, # | ← Rev. 2 →   0 For problem C, Why my solution failed? http://codeforces.com/contest/1009/submission/40348123Edit: Failed on pretest 5
•  » » 11 months ago, # ^ |   +1 n is an int up to 10^5 and you are doing n*(n+1) when you calculate beech
•  » » 11 months ago, # ^ |   +1 One obvious reason is overflow. You have beech = n*(n-1), but n is an int. See what happens when n = 100000 or n = 99999.
 » 11 months ago, # |   0 I've been really enjoying this series of contests, but out of curiosity, wouldn't it be better advertising to create Div 1 rounds? I'd love to go to the camp, but considering how far away I am from making ACM worlds, it's hard to justify the expense.I think Div 1 participants are more likely to take the plunge and spend 1000+$and a week away from school.  » 11 months ago, # | ← Rev. 2 → +26 A very good contest with a very smooth difficulty curve, not an easy thing to make. Good job to the writers  » 11 months ago, # | 0 When can we submit?  » 11 months ago, # | +61 Taking strong tests to another level :P •  » » 11 months ago, # ^ | +110 There are actually 130 tests in this problem.It was originally used in Saratov SU trainings a few days ago, and there was a man who managed to receive RE 130. •  » » » 11 months ago, # ^ | ← Rev. 3 → +9 How can one get RE at 131 if there are only 130 test cases? Am I missing something? •  » » » » 11 months ago, # ^ | +9 Successful hacks are added to the testcases for systests, so there are 130 pretests + any successful hacks. •  » » » » » 11 months ago, # ^ | 0 Oh so thats why. I didn't knew that before. Thank you •  » » 11 months ago, # ^ | -15 Yeah, strong tests in tree problem without test "1-2-3-...-N". This is Educational round.  » 11 months ago, # | ← Rev. 3 → 0 Can somebody explain why my code for E got TLE in Test Case 9 (though I think it's O(n)) and for C got WA in test 5 ? Intercity Travelling#include using namespace std; const long int prime = 998244353; const long int N = (1e6)+7; long long int coeff[N] = {}; void precompute(){ coeff[0] = 1; long int mul = 1; for (int i = 1; i< N; i+=1){ long long int jk = (2*coeff[i-1] + mul)%prime; coeff[i] = jk; mul = (mul*2)%prime; } } int main(){ int n; cin>>n; int arr[n]; precompute(); for (int i = 0; i>arr[i];} unsigned long long int sum = 0; for (int i = 0; i #include using namespace std; long long int mini(int n){ if (n%2 == 0){ int k = n/2; long long int x = k*k; return x; } else{ int k = n/2; long long int x = k*(k+1); return x; } } long long int maxi(int n){ long long int y = (n*(n-1))/2; return y; } int main(){ cout<>n>>m; long int neg = 0, pos = 0; long int sx = 0; for (int i = 0; i < m; i+=1){ int x, d; cin>>x>>d; sx += x; if (d < 0){ neg += d; } else{ pos += d; } } long double foo = (long double)neg*mini(n)/n; foo += (long double)pos*maxi(n)/n; foo+= (long double)sx; cout< •  » » 11 months ago, # ^ | +1 For C: check overflow. You're multiplying two ints and storing the result in a long long. Overflow happens before the storing does. •  » » » 11 months ago, # ^ | ← Rev. 2 → +3 Thanks for finding the error in both the codes :) •  » » 11 months ago, # ^ | +1 For E: You're reading 10^6 numbers using cin. Speed it up with ios::sync_with_stdio(0) and cin.tie(0) or use printf/scanf.  » 11 months ago, # | 0 Could someone please explain why this code doesn't work for problem D? http://codeforces.com/contest/1009/submission/40345268Here's the approach I used — Since the graph has to be connected, the M has to be >= N-1 otherwise impossible. I then proceeded to take the sum of all phi(n) from 1 to N (phi(n) being the Euler Totient Function). If this sum >= M, I then use sieve to create the graph. I started matching 1 to all nodes from 2 to N, thus making the graph connected. This meant I had M — N + 1 edges left to add. I used sieve to find relatively prime numbers and as soon as the count of edges hit 0, I returned 0 and proceeded to print the graph. I would really appreciate a counter-test so that I know where I was going wrong. Thank you! •  » » 11 months ago, # ^ | +4 I tried 20 45 and the last edge you print is 4 10. GCD( 4 , 10 ) = 2. Hope this helps •  » » 11 months ago, # ^ | +4 Looks like you're just counting multiples of a number as non-coprime with it, which is only true for primes — not composite numbers. Try 6 11. You print 4 6. •  » » 11 months ago, # ^ | +4 For every x, sieve will only delete every multiple of x (not relatively prime of x). So your sieve will delete every multiple of x, add every y where y is not multiple of x, and readd every multiple of x •  » » 11 months ago, # ^ | ← Rev. 2 → +3 Got it, thank you Diegogrc, nishank.suresh and Firastic! I'll upsolve this now.  » 11 months ago, # | +3 Educational.....  » 11 months ago, # | ← Rev. 2 → +2 I don't know why I was getting TLE on test case 6 on problem C here. The time complexity looks linear to me. Maybe the logic for the problem I am using is wrong. But stil I shouldn't get TLE as I guess the complexity of the code I am using is O(n). Can someone explain both the logic and the problem with my code? •  » » 11 months ago, # ^ | 0 I'm not sure but i think your arrays are too small (10000 instead of 100000). •  » » » 11 months ago, # ^ | +3 Damn! I also figured that out like a minute ago and yeah the array size is small. I just missed it literally by a '0'. It's frustrating. But the contest was really good. Hats off to problem writers!. •  » » » 11 months ago, # ^ | +3 So if there is a segmentation fault then TLE is given as error on codeforces right? •  » » » » 11 months ago, # ^ | 0 It means it failed to meet the segmentation fault. Instead, it probably got into an infinite loop by changing the value of nearby variables (i.e., 'i' or 'm'), therefore getting TLE from it.  » 11 months ago, # | +32 Great difficulty balance of the problems, shoutout to the writers!  » 11 months ago, # | +5 Oh.... I fall a trap in Problem B and got confused a lot on that problem  » 11 months ago, # | 0 How to solve B? •  » » 11 months ago, # ^ | +9 1011201120112 is 0111111120202 •  » » » 11 months ago, # ^ | 0 greedy doesn't work? I am getting the same soln but still dreaded test case 4 fails • » » » » 11 months ago, # ^ | +3 It works perfectly. my submission : http://codeforces.com/contest/1009/submission/40342688 Greedy doesn't mean that you put all small values before bigger ones, we have to do so but under some constraints. Explanation of my solution: Maintain a reverse_ans string, initially null. Start from last, if there is a '0' or a '1' increase the counter for '0' or '1. If there is a '2', we know that we can't shift any '0' beyond this point, so first put all found zeroes to reverse_ans and reset its counter and now put '2' in reverse_ans. # Important step (greedy but different to what is done above) At the iteration is over, first put all '1' to reverse_ans and then all zeroes. reverse the reverse_ans and print it. •  » » » » » 11 months ago, # ^ | 0 what I thought was get all 21 and convert to 12 and 10 to 01. The only exception to this rule was 201 which becomes 120. run this till I have no 201, 21 or 10 in my string. this soln fails and I want to know why or what test case am I missing. •  » » » » » » 11 months ago, # ^ | 0 2121111111111111111111111111111(up to 10^5 length)If you look for all occurrences of "12" or "21", you should get a TLE.For WA, 0000212000001 Answer : 0000112200000 •  » » 11 months ago, # ^ | +9 Put all '1' s just before first "2". 012012 becomes 011202 , whereas your code gives 012012 •  » » 11 months ago, # ^ | 0 so, count '2' and '0' from first '2' and put them back of the string with same order. fill the rest of numbers 1 •  » » 11 months ago, # ^ | ← Rev. 3 → 0 count 1 in string then count 0 before any 2 comes then print 0 as per count then print all 1, then just print 0/2 as they come in string. for eg. 101201120 becomes 011112020 •  » » 11 months ago, # ^ | 0 Maintain the order of 0's ans 2's. Take all 1's and put them just before 1st occurence of 2.  » 11 months ago, # | +33 1:59:59 :D •  » » 11 months ago, # ^ | ← Rev. 3 → +4 AmazingBut what's more Amazing is that you just submit the first 3 problems in 3 minutes  » 11 months ago, # | 0 Cool problems, thanks to round authors.why is this recurrence wrong for E?where dp[0] = 0 and a[i] is the prefix sum. I can use fenwick tree for prefix sum but why logic error? I am choosing the rightmost stop and then I calculate difficulty for remaining sub problem. •  » » 11 months ago, # ^ | 0 This recurrence is wrong because it doesn't take probabilities into account.For example, suppose you are analyzing 4-th kilometer and trying to find a closest rest stop before it. The probability that it will be on position 3 is 0.5, the probability that it is on coordinate 2 is 0.25, and so on. So we can't just sum all these dp values up, we need some coefficients.  » 11 months ago, # | 0 How to solve E ? •  » » 11 months ago, # ^ | ← Rev. 3 → +5 Note: I didn't actually solve E but I got the problem right after contest ended...The answer is: whereP[i] = 2N - i - 1·(N - i + 2) for i = 1...N-1P[N] = 1 (technically same as above but 2 - 1 is fractional)mod MOD at each step of courseI used brute force to find array for first 10 numbers and entered the list into OEISedit: off by 1  » 11 months ago, # | ← Rev. 2 → 0 Why this got MLE 40349306 and this didn't 40349677? Very strange, how much memory deque uses... •  » » 11 months ago, # ^ | 0 stl deque many times proves inefficient for many problems in time n memory usage •  » » 11 months ago, # ^ | 0 I think .clear() doesn't free memory. Could you try delete operation?  » 11 months ago, # | +10 NEVEEER USE DEQUE If you don't like to get MLE :( •  » » 11 months ago, # ^ | +5 SAAAME •  » » » 11 months ago, # ^ | 0 I use them. Never experienced ML till now because of them.  » 11 months ago, # | +4 problem B was very good! •  » » 11 months ago, # ^ | +1 With a greedy taste.  » 11 months ago, # | 0 Huh. For problem E if you use cin, you get TLE on test case 7, but if you use scanf you get AC :O •  » » 11 months ago, # ^ | +2 try using ios::sync_with_stdio(false);cin.tie(NULL);. It can boost up speed of cin/cout to that of scanf/printf. See 40351502 •  » » » 11 months ago, # ^ | 0 oh i used scanf during contest  » 11 months ago, # | ← Rev. 3 → 0 In D problem even the custom invocation is showing possible but the test case 18 is giving Impossibe for my code Please check out this solution http://codeforces.com/contest/1009/submission/40348587Same Code gets submitted after ccontest http://codeforces.com/contest/1009/submission/40350442OOps figured out n*(n-1) crossed int limit •  » » 11 months ago, # ^ | 0 Looks like your solutions just overflows in m>(n*(n-1)/2). •  » » 11 months ago, # ^ | 0 The problem with the first one was overflow: you were comparing m with (n*(n-1))/2 where n was an integer. If n is large enough the product will overflow and become negative. Second submission doesn't have that comparison so it passed.  » 11 months ago, # | +5 For C i used double instead of long double to store (double)total_sum / n. Can it cause wrong ans in main test due to precision issue? •  » » 11 months ago, # ^ | ← Rev. 3 → -7 double ans = (double)sum/nans might overflow, you should've typecasted sum to long double! •  » » » 11 months ago, # ^ | 0 sum will not overflow, it's about O(n3·maxn) which is smaller than 1018 •  » » » » 11 months ago, # ^ | ← Rev. 2 → 0 I meant after typecasting long long int to double it might overflow!Updated! •  » » 11 months ago, # ^ | 0 No, it should be okay.  » 11 months ago, # | 0 Today's D was easier (till now I think) compared to the last contests. And I wasted my time to look for corner cases and if any case that will lead me to TLE. Could not get time to solve E (which had a nice pattern). Anyway, educational contests are fun than the usual ones. Though I messed up today's one badly. Did not think today's one was going to be simpler than the past.  » 11 months ago, # | ← Rev. 6 → -26 ... •  » » 11 months ago, # ^ | +1 We can always bring any 1 to the beginning of the string, since we can swap 1 with any other digit. •  » » 11 months ago, # ^ | 0 because there are sufficiently many 1s in the string, the 0 and 2s have become invisible after the moves.  » 11 months ago, # | +4 guys someone sent me a message which asks me to help him solve C and that he will help me solve B. Fortunately I was not noticed with that message during the contest and as you guys can see I ended up without solving B and after the contest i solved it by myself. My question is: how can I report him for cheating?  » 11 months ago, # | ← Rev. 2 → +19 In the test 11 of problem C:Checker comment ok found '621354311313.3487500', expected '621354311564.2170400', error '0.0000000'Why is the output correct? •  » » 11 months ago, # ^ | +12 Its relative error is smaller than 10 - 6 •  » » 11 months ago, # ^ | 0 In terms of relative error, it's correct.If it is stated that "Your answer is considered correct if its absolute or relative error doesn't exceed 10 - x", then checker considers the minimum of absolute and relative errors.  » 11 months ago, # | 0 how to solve D? •  » » 11 months ago, # ^ | 0 Run two loops(1 to n and from i+1 to n)and calculate gcd (i,j)if it is 1 then print as m can be atmost 100000 so the both loop terminates after m iteration. And if n>m-1 you have to print impossible as the graph then can't remain connected •  » » » 11 months ago, # ^ | +2 "as m can be atmost 100000 so the both loop terminates after m iteration" can you please prove it or can give some intuition behind it? •  » » » » 11 months ago, # ^ | 0 if(m < n-1){ out.println("Impossible"); return; } List es = new ArrayList<>(); for(int i = 1;i <= n && m > 0;i++){ for(int j = i+1;j <= n && m > 0;j++){ if(gcd(i, j) == 1){ es.add(i + " " + j); m--; } } } •  » » » » 11 months ago, # ^ | +1 It's not true, using this method at least. Since every pair is being checked, even those with gcd(i, j) != 1 will be checked, leading to more than m iterations in total. •  » » » » » 11 months ago, # ^ | 0 for(int i=1;i<=100000 && al.size()<=100000;i++){ for (int j = i+1; j <=100000 && al.size()<=100000; j++) { if(gcd(i,j)==1){ al.add(new pair(i,j)); } x++; } }x came out to be 100002 •  » » » » » » 11 months ago, # ^ | 0 We can get 100000 pairs where gcd(i,j)=1 in 100002 iteration so it doesn't give TLE •  » » » » » » 11 months ago, # ^ | ← Rev. 3 → 0 The worst case for this will actually be with a somewhat smaller n but large m. Maybe something like n = 10000, m = 100000 will work, I haven't tested exactly. If n is very large, most of the edges will come very quickly since you get n-1 from 1, and 2 and 3 are both prime. Only when you need i to go fairly high (and be composite) do you start getting less edges added per iteration.Edit: n = 10000 and m = 100000 gives x = 161528. This algorithm is probably going to be fast enough, but certainly not going to stop in exactly m steps. •  » » » » 11 months ago, # ^ | ← Rev. 2 → +1 The ratio of number of relatively prime pairs (i, j) that 1 ≤ i ≤ j ≤ n and all pairs is: Probability of coprimality. We can generate random pairs using uniform distribution and choose only$ m \$. In C++ I used std::uniform_int_distribution, std::mt19937 and my hastable and got accepted.
•  » » 11 months ago, # ^ |   +13 Given n, the number of possible edges is basically all those (unordered) pairs (x, y) such that x, y ≤ n and gcd(x, y) = 1 and x ≠ y. This number is simply φ(1) + φ(2) + ... + φ(n) - 1, where φ is the totient function. (subtracting 1 since we can't have the pair (1, 1).This gives us 2 edge cases: if m is greater than this number or m < n-1 it's not possible to create such a graph — either it won't be connected or there won't be enough edges.In every other case, it's possible. Connect 1 to every other node first to connect the graph. Then, for each pair (i, j) such that gcd(i, j) = 1, i ≤ j, 1 < i, j ≤ min(n, 600) you have one edge. 600 because φ(1) + ... + φ(600) > 100000 so you're guaranteed to have enough edges with just that.
•  » » » 11 months ago, # ^ |   0 nice observation! and thanks a lot.
•  » » 11 months ago, # ^ |   0 In D, the most important task was to check possible or not because other than that, we just need to output co-primes together. In order to check co-primes of available, you just need to implement Euler's totient function. Thus in O(n), we can check possibility or not.We could have stored this value in a vector to check is total count is greater than required and n-1 as well. But that can bring TLE for large cases.Submission
 » 11 months ago, # |   0 How to solve F? Can it be done in O(NlogN) or O(N)?
•  » » 11 months ago, # ^ |   0
•  » » 11 months ago, # ^ |   0 Do dfs on a tree, and for every node x, you can find the array d(x). You can make it in O(nlogn) if you merge there arrays carefully. MLE solution: 40349306 Correct: 40349677
•  » » » 11 months ago, # ^ |   0 This technique is called dsu on tree?
•  » » » » 11 months ago, # ^ |   0 Idk, I just call it merging vectors on trees.
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +5 In fact, we can even make it O(n) if we merge the structures for subtrees not according to their sizes, but according to their heights (merge lower subtree to higher).
•  » » » » 11 months ago, # ^ |   0 Can you explain this, how to merge in O(n)?
•  » » » » » 11 months ago, # ^ | ← Rev. 2 →   +8 It seems that 40349677 (if I understood the code correctly) actually uses this method of merging in O(n). You just need to do the same things you do in standard small-to-large approach, and it "magically" works in O(n) time if the size of subtree's structure is proportional to its height (and merging two structures can be done in time proportional to the size of a smaller structure).A more detailed explanation, proof and my implementation will be in editorial.
•  » » » » » » 11 months ago, # ^ |   0 Okay , thanks!
 » 11 months ago, # |   0 Can someone confirm if everything is okay with Problem-D ? My solution SEEMS to be working well on my system but failed pretest number 3.
•  » » 11 months ago, # ^ |   0 Turns out my solution was wrong. Sorry.
 » 11 months ago, # | ← Rev. 2 →   0 Obviously http://codeforces.com/contest/1009/submission/40351881 submission will eventually fail, because of taking limit small, but I can't for the life of me figure out why it is getting wrong answer on test case 4. Could someone please help me out? Every single thing besides considering number of nodes(which should in no way be a cause of getting wa at this test case) seems fine in here to me and yet I'm getting WA on F, test case 4
 » 11 months ago, # |   -13 How to solve B, C, D, E?
 » 11 months ago, # |   +1 Can anyone tell why my solution got hacked after passing the preliminary tests here
•  » » 11 months ago, # ^ |   0 Maybe using long double instead double will help?
•  » » » 11 months ago, # ^ |   0 long double where?
•  » » » » 11 months ago, # ^ |   0 cout<
•  » » » » » 11 months ago, # ^ |   0 I tried, still, it got hacked :(. My solution here. Any idea what the failed test case might be?
•  » » » » » » 11 months ago, # ^ | ← Rev. 2 →   0 The answer can be up to 5.0005 * 10^12 * 10^5 = 5.0005 * 10^17 — when n, m = 10^5, all x = 1000 and all d = 1000. So 8 digits isn't enough.
•  » » » » » » 11 months ago, # ^ |   0 Please try this test: 3 1 0 -1 The answer must be -0.6666667
•  » » » » » » 11 months ago, # ^ |   0 if d<0 we need to take into consideration 2 cases: n is odd and n is even. 40355675
•  » » » » » » » 11 months ago, # ^ |   0 It's working now and I got it. I just considered the case of n is odd. Thanks a lot!.
•  » » » » » » » » 11 months ago, # ^ |   0 You're welcome! Good luck!
 » 11 months ago, # |   +36 Maybe it's one of the simplest solutions on problem E. #include using namespace std; const int p=998244353; int n,x,l,s; int main(){ cin>>n; while(n--){ l=(l*2%p+x)%p; cin>>x; s=(s*2%p+l+x)%p; } cout<
 » 11 months ago, # |   0 In Problem D . I tried to use totient function to find out if it's possible or impossible to form the graph. And then just printed out the no whose __gcd(i,j) == 1. Is this approach correct although I'm getting wrong answers . Am I missing some vertices? http://codeforces.com/contest/1009/submission/40351068
•  » » 11 months ago, # ^ |   +9 The graph should be connected.So your solution got wrong when m
•  » » » 11 months ago, # ^ |   0 So what's the correct procedure to print?
•  » » » » 11 months ago, # ^ |   +9 You are supposed to print "Impossible" when m
•  » » 11 months ago, # ^ | ← Rev. 7 →   +7 Yes, 3 things- 1) Your graph is not necessarily connected so include all the edges of type 1 i ,i>=22) Check condition for p>=m and m>=n-1 in your if part3) Run loop only till 600 because summation of euler function is >100000 for 600 i.e upto 600 you will get enough edges to make the graph connected satisfying condition for m edges.
 » 11 months ago, # |   +62 Can't be more accurate
 » 11 months ago, # |   0 Recurrence for generating coprime pairs for D.https://en.wikipedia.org/wiki/Coprime_integers#Generating_all_coprime_pairs
•  » » 11 months ago, # ^ |   0 This works, but wouldn't there be any overlapping cases ?
•  » » » 11 months ago, # ^ |   +4 It says that "This scheme is exhaustive and non-redundant with no invalid members" so it shouldn't produce overlaps.
 » 11 months ago, # |   0 The Pretests were easy for B and C and hence easily hackable. T_T
 » 11 months ago, # |   +3 Sequence A001792 in OEIS for task E.
 » 11 months ago, # |   -8 Was the evaluator for problem C correct? My solution ( 40334143 ) got hacked after the contest, and after checking the test cases that were ok i found something weird. In Test 11 my answer was off by more than 100 and the evaluator returned ok. Is this a problem with the evaluator? I believe this shouldn't happen
•  » » 11 months ago, # ^ |   +8
•  » » 11 months ago, # ^ |   0 In terms of relative error, it's correct
 » 11 months ago, # |   0 None of this matters much, but I'm curious how the standings and problems solved vary during the hacking phase. I understand that as solutions get hacked, people lose credit for problems, so their ranking would go down. That means that if you don't have a solution hacked, your rank tends to get better. And, the dashboard generally shows fewer of each problem solved, as solutions get hacked.But, I've also seen my ranking get worse (without having a solution hacked) at some points during the hacking phase — generally just a little bit — maybe 10 places. And, I occasionally see the number of solved problems go up during the hacking phase. I imagine the number solved might include people submitting them afterward, but presumably that doesn't affect ranking. Any ideas how this is happening?
•  » » 11 months ago, # ^ |   0 Virtual participators.
•  » » 11 months ago, # ^ |   0 Uncheck the checkbox stating "show unofficial" on top right corner of Standings page.
 » 11 months ago, # |   0 In today's contest I saw many solution of C got hacked,after the hacking phase could anyone please state in what case many of the contestant's solution went wrong.
•  » » 11 months ago, # ^ |   0 most of them have kept of datatype of sum variable as double which will overflow for large values x and d when summed across m queries.So use long double instead!!
•  » » » 11 months ago, # ^ |   +3 I also have used double, but when I tried to hack my solution by putting maximum constraints, even then it passed the test.
•  » » » 11 months ago, # ^ |   +17 I used long long. Still no hack. And a lot of used long long. long long sum and then cout << fixed << setprecision (10) << (double) sum / n * 1.0 << endl; This seems to work fine. So, I am curious about what the hack case is.
•  » » » » 11 months ago, # ^ | ← Rev. 3 →   0 I see that Test #11 says "ok found '621354311564.2196000', expected '621354311564.2170400', error '0.0000000'". Umm why is this? Edit: Sorry for the mistake, I just found out that it is the relative error.
•  » » » 11 months ago, # ^ |   0 Yeah I just checked the sizes of double and long double.Double is of 8 bytes while long double is 16 bytes on C++ 14. I kind of had a misconception both were of 8 bytes,but now I see those were for older versions.
 » 11 months ago, # |   0 Can somebody please explain how double in C++ works? I was sure it takes 8 bytes and has diapason from -9 * 10^18 to 9 * 10^18. Where am I wrong?
•  » » 11 months ago, # ^ |   +11 Double (and other data types for real numbers) can have precision errors. The numbers in computers are represented by bits. Int takes 4 bytes, long depends on the OS, long long 8, float 4, double 8 and so on.. Check this link for more information: https://www.tutorialspoint.com/cplusplus/cpp_data_types.htmI think you know that int data type is limited to values between -2^31 to (2^31 — 1). In that range, there are exactly 2^32 different numbers which is the maximum we can represent with 32 bits. Float is a data type for real numbers and its size is 4 bytes (same as int). That means, we have 32 bits and we can represent at most 2^32 different values. We know that float can be used to represent some real numbers which we cannot represent with int. That means for one real number, we have used one of those 2^32 combinations for its representation. Then if we try to represent every possible integer in the int range, there will be some numbers whose int and float values will be different. Thus those floats will be rounded to another value.Real numbers can be represented with the IEEE 754 standard. You can Google it for more information if you want to see how it works. That representation, allows us to represent very high numbers (I think it’s something like 10^308). But, we can only represent 2^size different numbers where size is the size of the data type in bits.I explained you about float, and I hope you understand what’s the problem with those representations. It’s similar for double, its length is just 8 bytes.Try the following program. An example of an integer that gets rounded when represented by double. #include using namespace std; typedef long long ll; typedef double db; int main() { ll x = (1LL << 61) + 13213124123213213LL; db y = (db) x; cout << fixed; cout << x << endl; cout << y << endl; return 0; } And since some integer numbers get rounded by real data types, it’s also true that some real numbers will get rounded as we don’t have infinite precision. And if your program rounds the number many times, you may get wrong answer verdict for some example.I fixed your program: http://codeforces.com/contest/1009/submission/40360084 My advice is, try to use as less real data types as possible. In line #13, you were using double to calculate a number which can be as big as 10^10 (= (10^5)^2) and as I explained you, it’s a bad idea.
•  » » » 11 months ago, # ^ |   0 Thank you very much!
 » 11 months ago, # |   +33 halyavin is doing wonders!!! What a hacker!!
•  » » 11 months ago, # ^ |   +6 True hacker
•  » » 11 months ago, # ^ |   +3 That's system testing in disguise
 » 11 months ago, # |   0 I think that for C the judge should be made with integers, because it can be not fair sometimes.
 » 11 months ago, # |   0 After how many hours does system testing start for educational CF rounds?
 » 11 months ago, # |   +12 Where's editorial?
 » 11 months ago, # |   0 where can i find the editorial for this contest?
 » 11 months ago, # |   0 Can anyone please tell me what is wrong with this 40362288 ?40362440 This one gives me AC. The Only difference is I have declared the variable sum as long long is this submission and as double in the previous submission ? How can this give me wrong answer ?
 » 11 months ago, # |   0 Can someone help me with problem A? My solution passed all test cases yesterday but now it shows wrong output on test case 9, but on my machine the output matches correctly with the answer.40325412
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 Before accessing any kind of container (queue,stack,set etc.) You should always check either it empty or not.
•  » » 11 months ago, # ^ |   0 Use this as conditionif(!wallet.empty() && arr[i]<=wallet.front())
•  » » » 11 months ago, # ^ |   0 thank you :)
 » 11 months ago, # | ← Rev. 2 →   0 how did halyavin hack 600+ in 12 hours manually?
•  » » 11 months ago, # ^ |   0 He ran some sort of script
•  » » » 11 months ago, # ^ |   0 is it allow?
•  » » 11 months ago, # ^ |   0 You still think he did it manually
•  » » » 11 months ago, # ^ |   0 not now!
 » 11 months ago, # |   0 I don't understand why my solution got Hacked
•  » » 11 months ago, # ^ |   +3 double has problems with precision. For example, calculating 1e18 - 1 - 1e18 sequentially results in 0.0 instead of -1.0.View test provides the generator of the hack. It constructs a general input hacking all solutions that accumulate the answer with double.
•  » » » 11 months ago, # ^ |   +5 thanks!!! and can you suggest how can I tackle this problem
•  » » » » 11 months ago, # ^ |   +3 The answer before being divided by n won't exceed mn2(d + x) about 1e18. Thus int64 (long in Java?) is efficient to store the answer. Then you can output the answer divided by n in double.
•  » » » » » 11 months ago, # ^ |   0 thanks!!! finally got Accepted
 » 11 months ago, # |   0 Can anyone tell if my submission for problem C is correct or not? Whether it will pass the tests used in the hacking. http://codeforces.com/contest/1009/submission/40330305I used double in the end for division and before that used long long to store the sum. Can’t double store till 10^18?
 » 11 months ago, # | ← Rev. 2 →   0 I didn't understand problem F. How depth array of vertex 1 of example 1 look like?I thought it would be {0, 1, 1, 1, 0, ...} and the dominant index would be 1 but 0.Is a vertex an ancestor of itself?
•  » » 11 months ago, # ^ |   0 It depends on how we define i guess. I think it should have been specified to consider a vertex as ancestor of itself,but by looking at the sample tests you can get it.
•  » » 11 months ago, # ^ |   +8 Yes, vertex is an ancestor of itself in this problem.
•  » » 11 months ago, # ^ |   0 The array is actually [1, 1, 1, 1, 0, 0, ...]. The first element is 1 because (by definition) there is one vertex so that the simple path between 1 and y contains 0 edges. Path with 0 edges means its the vertex itself, so it's 1. And yes, the vertex is its ancestor. The same is true any other vertex, so the array always starts from 1.
•  » » 11 months ago, # ^ |   0 Thank you all for kind reply.During the contest, I was searching the definition of ancestor over and over... to understand example
 » 11 months ago, # |   +8 Great contest
 » 11 months ago, # |   0 can you tell me why my submission 40370101 is WA at test 39?PLz PLz PLz
•  » » 11 months ago, # ^ | ← Rev. 3 →   +3 precision error,use long double or change approach slightly and use int64
 » 11 months ago, # |   0 Can someone list what should I study to solve C, E and F. Thank you.
 » 11 months ago, # |   0 Where's editorial ?? Also what's the approach of E? Or should we just use OEIS to find the pattern?
•  » » 11 months ago, # ^ |   +3 The editorials for educational rounds are always really late. Probably will take a few more hours/days. :-(E is just dynamic programming. Find a recursion for dp[i] = sum of all path between 0 and i. Hint: think about the location of the last rest site.
•  » » 11 months ago, # ^ |   +3 Editorial will be published in 4-5 hours, sorry for the delay.
 » 11 months ago, # |   0 How to solve F with dsu?
 » 11 months ago, # |   -10 Your crafting.oj.uz ratings are updated! :D
 » 11 months ago, # |   0 halyavin do you use a program(robot) to hack for you .. incredible
 » 11 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 11 months ago, # |   +18 Can someone explain how halyavin's hack for C causes double to not be precise enough?
•  » » 11 months ago, # ^ |   +40 I construct a test where answer is close to zero but intermediate results are as large as possible. This causes catastrophic cancellation and loss of relative precision.
 » 11 months ago, # |   0 There he strikes again, halyavin ;)
 » 11 months ago, # |   +8 978 successful hacks So the green hacks team won again?
 » 11 months ago, # |   0 good job Marcel_Ib 20 hacks