### Vovuh's blog

By Vovuh, history, 4 weeks ago, translation, ,

UPD: Thanks to Daria ZeroAmbition Stepanova, Mikhail PikMike Piklyaev and Artem Rox Plotkin for help with round preparation!

UPD2: Editorial is published!

<almost-copy-pasted-part>

Hello! Codeforces Round #595 (Div. 3) will start at Oct/22/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

• +283

 » 4 weeks ago, # |   +4
 » 4 weeks ago, # | ← Rev. 2 →   -15 I wish you all good luck
 » 4 weeks ago, # |   -10 hope this contest becomes my last official participation in DIV3.
 » 4 weeks ago, # |   0 I hope become pupil
•  » » 4 weeks ago, # ^ |   0 Believe yourself!
•  » » 4 weeks ago, # ^ |   +3 You'll get it if you solved A,B and C.
•  » » » 4 weeks ago, # ^ |   -11 hope to solve this problem
•  » » 4 weeks ago, # ^ |   -18 try
•  » » » 4 weeks ago, # ^ |   -12 I will do
•  » » 4 weeks ago, # ^ |   -22 And now you won't. Learn some lesson and please stop posting this shit
 » 4 weeks ago, # |   -11 Good luck to everyone. I hope this round will be an exciting contest without dots attacks and lots of hacks. Finally I hope the problems will be solvable and understandable.
 » 4 weeks ago, # | ← Rev. 2 →   -13 Div-3 is Love... True Love... Pure Love...
 » 4 weeks ago, # | ← Rev. 3 →   -12 Love Vovuh's Contest
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 Easy to understand hard to solve!i Love Vovuh's too
 » 4 weeks ago, # |   0 Hope the round will no DDOS attack.
 » 4 weeks ago, # |   +34 Fitness challenge: I'll do one pull up for every rating point lost and I'll do 3 pushups for every point won. Feel free to join the challenge under your conditions.
•  » » 4 weeks ago, # ^ |   +16 5000+ push and pull ups for V--gLaSsH0ldEr593--V lol
•  » » » 4 weeks ago, # ^ |   -10 Yeah. Imagine how shredded he would be now. That's why I'm doing this.
•  » » » 4 weeks ago, # ^ |   +51 qwq
•  » » » » 4 weeks ago, # ^ |   -10 orz gritukan
 » 4 weeks ago, # |   +11 I think you should take part in some contests to become master. It's more beautiful ^^
 » 4 weeks ago, # |   +6 Why Div3 get so little upvotes :(Are we just used to them?
 » 4 weeks ago, # |   +9 Which problem has two subtasks? @Vovuh
•  » » 4 weeks ago, # ^ |   +40 Look, I really don't think it is important information before a round. I prefer Vovuh will spend time improving problem statements and tests.
•  » » » 4 weeks ago, # ^ |   0 I wish it would be the greatest CONTEST ever !!!
 » 4 weeks ago, # |   -45 Why do Vovuh conducts only Div.3? I don't like him.
 » 4 weeks ago, # |   +22 Hi! I decided to simplify one of the problems and divided it into easy and hard versions. That's why I increased the round duration to 2:15. Don't afraid of formally too many problems in the round. You shouldn't think about easy/hard versions as about two independent problems. And good luck!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 will my rating go down, if i am not able to solve even one problem. Like if i don't submit none.
•  » » » 4 weeks ago, # ^ |   0 no if you dont submit
•  » » 4 weeks ago, # ^ |   -11 Very good idea to divide problems into parts. Sometimes, even after solving the problem, it requires additional data structures or optimizations. This way even partially correct solutions that are slower than intended get partial points.
•  » » » 4 weeks ago, # ^ |   0 Another idea is creating one problem with different types of tests. Solutions can first get tested on small tests, and then on bigger numbers. And if it passes small tests, contestant can get partial verdict. This has been done in several rounds, to it is possible. It is just easier to navigate this way, instead of solving 2 same problems
•  » » » » 4 weeks ago, # ^ |   -10 really the two choices are grate but they will put that into consideration! who knows.
 » 4 weeks ago, # |   +18 I will AK this contest !
•  » » 4 weeks ago, # ^ |   +1 HaHaHa !
•  » » » 4 weeks ago, # ^ |   +8 aren't you HYH.AK.IOI
•  » » » » 4 weeks ago, # ^ |   0 No, I'm not. I'm IOI_AKer-HYH!
•  » » » » » 4 weeks ago, # ^ |   0 F** you duplicate account bot that ruins genuine div 3 people's fun
 » 4 weeks ago, # |   0 Vovuh ！！！
 » 4 weeks ago, # |   0 Best of luck to everyone on this round ^^
 » 4 weeks ago, # |   0 Vovuh, the half-quarter!
 » 4 weeks ago, # |   0 Good luck!
 » 4 weeks ago, # |   +3 I want to improve myself~
 » 4 weeks ago, # |   0 Good Luck guys
 » 4 weeks ago, # |   +23 There's an expert participant in the trusted participants rankings, by the way.
•  » » 4 weeks ago, # ^ |   +22 That's probably because he registered to the contest before he became Expert, so he was marked as an official participant.
•  » » 4 weeks ago, # ^ |   +6 His rating was updated too.
 » 4 weeks ago, # |   +15 Contest is over. It was a good contest.
•  » » 4 weeks ago, # ^ |   -27 Don't agree.
 » 4 weeks ago, # |   +5 I solved 7 problems for the first time. Feel amazing >__< !!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I solved 6 but still. Which 6 did you solve? I didn't solve D1, D2 and F. Is D1 just straight bruteforce? I didn't try because it seems like it'll be something like O(n^4) :(
•  » » » 4 weeks ago, # ^ |   0 I believe you can see his submissions
•  » » » » 4 weeks ago, # ^ |   0 Oh ye. Problem E is awesome, I tried a dp-greedy method and it worked. I can't even convince myself that it is true, but complexity-wise it passed.dp[i][elevator?(bool)] = Minimum total time to reach ith floor, with last move taking the elevator (or not, depending on the bool)dp[1][false] = 0, dp[1][true] = cdp[i][false] = min(dp[i — 1][false], dp[i — 1][true]) + a_(i — 1)dp[i][true] = min(dp[i — 1][false] + c, dp[i — 1][true]) + b_(i — 1)output *(min(dp[i]) for i in range(1, n + 1))Can someone prove this .-.
•  » » » 4 weeks ago, # ^ | ← Rev. 7 →   0 Ummm I used Segment Tree with Lazy Propagation for D1 & D2. (Segment Tree is really useful >__
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +10 yeah there is an easy way of solving d1 and d2 refer my sol for hint sol: 63150473
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 I solved 7 problems too. I wish this contest is rated.
•  » » » 4 weeks ago, # ^ |   +1 I hope we can all be Blue-coder Kkkk
•  » » » » 4 weeks ago, # ^ |   0 Yes.I'm looking forward to rating update.
 » 4 weeks ago, # | ← Rev. 2 →   0 Can somebody explain test case 2 in F?Thanks
 » 4 weeks ago, # |   +2 How to solve C2 ?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +2 It's just ternary numeral system.My solution:precalculate all values 3^n (0..38 powers), it's 100..000 preseentation of numbernext I check first X that 3^0 + 3^1 + ... + 3^X (presentation of 111..11) >= n, if yes subtract from n 3^X, and add to result same numberdo while n > 0
•  » » » 4 weeks ago, # ^ |   0 What about n = 10^18? In the first test the answer is 1350851717672992089, but 3^38 > 10^18 and less than test's answer
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 You are correct (10^18 — 3^38) < 0 and loop stopped.But first I compare with (3^39-1) and subtract (3^(39-1))upd: sorry, not 3^X-1, but 3^0+3^1+..+3^X and if this value greater or equals than n I subtract 3^X from n and add to result
•  » » » » 4 weeks ago, # ^ |   0 exactly my code prints 1350851717672992000 but answer was given larger than this and I didn't submit :'(
 » 4 weeks ago, # |   +1 How to solve D2?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +2 I solved it using line sweep algorithm. Iterate through the points [1,2e5]. Keep a set that includes current line segments. Whenever you find a condition where the number of line segments exceeds k in the current set, remove the line segments which have higher ending point.
•  » » » 4 weeks ago, # ^ |   +2 wrong code
 » 4 weeks ago, # |   0 What was test case 14 of D1?Also, how where you supposed to solve D2? I thought using a BinaryIndexedTree, but I wasn't sure how to implement.
 » 4 weeks ago, # | ← Rev. 2 →   +1 What is Test 11 for Problem E?
 » 4 weeks ago, # |   0 Isn't Meet in the Middle expected solution for C2. My solution got TLE on test 7
•  » » 4 weeks ago, # ^ |   0 while (q--) {} isn't a good idea when q can be 10^18
•  » » » 4 weeks ago, # ^ |   0 N can be 10^18 not Q. So it's not a bad idea.
•  » » » » 4 weeks ago, # ^ |   0 yea my bad
•  » » 4 weeks ago, # ^ |   +1 I have greedy solution with prefix sums
•  » » » 4 weeks ago, # ^ |   0 This 63197085?
•  » » » » 4 weeks ago, # ^ |   0 This 63198485
•  » » » » » 4 weeks ago, # ^ |   0 Actually both are same :)
•  » » 4 weeks ago, # ^ |   +3 Hey !This is not a Meet In The Middle problem. In fact the intended solution doesn’t require bitmasks at all. Here’s what should be done Write the number in ternary base Look for the leftmost $2$ Look for the nearest $0$ to the left of the $2$ Set the $0$ to $1$ and change all positions to its right to $0$
•  » » » 4 weeks ago, # ^ |   +1 Yeah! I did this :)
 » 4 weeks ago, # |   0 I solved only 2 problems. Will my rating will increase or decrease? The problems were easy but I couldn't cope up with the constraints leading TLE
•  » » 4 weeks ago, # ^ |   +4 You can use the CF-Predictor browser extension
•  » » » 4 weeks ago, # ^ |   0 Thanks a lot! ZeroAmbition
 » 4 weeks ago, # |   +17 How to solve F?
•  » » 4 weeks ago, # ^ |   +3 dp on treedp[i][j] is the max sum can be obtained from the subtree of vertex i with the nearest picked vertex from this subtree is at distance j from vertex i
 » 4 weeks ago, # |   +13 I think this round is easier usual Div 3 round.
 » 4 weeks ago, # |   0 Any Penalties on Unsuccessful Hacking Attempts?
•  » » 4 weeks ago, # ^ |   0 Don't know because there was no points table shown like other Div.1 and Div.2 contests. Even which problem contains how many points is also unknown.
•  » » » 4 weeks ago, # ^ |   0 There is no any fixed scoring distribution in Div3 rounds.
•  » » 4 weeks ago, # ^ |   0 no
 » 4 weeks ago, # |   0 The moment I realized that the comparator used by me is wrong in D1/D2 after printing all the values for an hour...........
 » 4 weeks ago, # |   0 Anyone tell me why this code gives TLE? 63189145
•  » » 4 weeks ago, # ^ |   0 this is fixed code. 63190824 when you call functions, vector v would be copy. it makes tle.
•  » » » 4 weeks ago, # ^ |   0 Thanks a lot
 » 4 weeks ago, # | ← Rev. 2 →   -10 What's wrong with this solution for F — dp[node][level] = answer for subtree rooted at 'node' such that among all selected nodes the smallest depth is at 'level'? This recieved WA-3
 » 4 weeks ago, # |   0 After seeing constraint I thought greedy won't work for C2 so wasted one hour to implement Bit Mask+ Meet in the middle.Lesson learned. -_-
•  » » 4 weeks ago, # ^ |   0 My Meet in the Middle got TLE on test 7
•  » » » 4 weeks ago, # ^ |   0 Can you describe better, what was your Idea behind meet in the middle algorithm?
•  » » » » 4 weeks ago, # ^ |   0 Divide the powers of three into two vectors. Then each vector contains all possible numbers which contain distinct powers of three. Iterate through the first vector and binary search on the second vector for number >= (n — number in first vector ).
•  » » » 4 weeks ago, # ^ |   0 Don't divide power of three into two vectors of almost equal size, try keeping powers from 0-15 in first one, and 16-38 in second one (i.e one you use in binary search).
•  » » » » 4 weeks ago, # ^ |   0 I tried that too but no luck. You can check my recent submissions I tried all feasible combinations.
•  » » » » » 4 weeks ago, # ^ |   0 Check my solution. I have also used meet in the middle technique. The difference is I am not iterating through the whole set while answering a query. You can only check certain cases and get the correct answer.https://codeforces.com/contest/1249/submission/63178411
•  » » » » 4 weeks ago, # ^ |   0 Submission with (16, 23) sizes of subsets.
•  » » » » » 4 weeks ago, # ^ |   0 I didn't iterate through first vector... I used 2 binary search. First one for find the lowest value from vector1, lets say X, for which 2nd vector has a value, lets say Y, and X+Y>=n and X+Y is minimum possible. And Then Find the lowest value from vector2 in same way. And ANS is minimum of them. See my code for better understanding.
 » 4 weeks ago, # | ← Rev. 3 →   +16 My solution for $F$:Root the tree at node $1$. Let $dp[i][j]$ be the maximum subset weight for the sub-tree rooted at node $i$ if the nearest node in the subset to $i$ is at distance $j$ from it. Let $mxdp[i][j]$ be $max(dp[i][k])$ for $k$ from $j$ to $n$.How to fill $dp$?$dp[i][0]=a[i]+\sum_{c}mxdp[c][k]$ where $c$ is every child of $i$.$dp[i][j]$ (for $j$ from $1$ to $n$) $=max(dp[c_1][j-1]+\sum_{c_2!=c_1}mxdp[c_2][max(k-j,j-1)])$ where $c_1$ is every child of $i$, and $c_2$ is every other child of $i$.The answer is $mxdp[1][0]$.
•  » » 4 weeks ago, # ^ |   0 Shouldn't the answer be mxdp[1][0]?
•  » » » 4 weeks ago, # ^ |   +3 Sorry, it is a typo. fixed now.
•  » » 4 weeks ago, # ^ |   0 I think it should be $dp[i][0] = a[i] + \sum_c mxdp[c][k]$
•  » » » 4 weeks ago, # ^ |   0 Yes, another typo. Fixed.
 » 4 weeks ago, # |   +3 In D why remove segments from longest to shortest length is wrong?
•  » » 4 weeks ago, # ^ |   +1 Imagine three segments [1, 1000] [1001, 2000] and [1000, 1001] and k = 1. There are two points that have k = 2 : 1000 and 1001. If you remove longest segments, then you will need to remove both of the big ones. In another case, you can just remove the third one and m = 1
•  » » » 4 weeks ago, # ^ |   +1 thank you now I understand
 » 4 weeks ago, # |   0 how to solve B2?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 use dfs, to travel continuously until u get end point of cycle.then update all the travelled value to max distance you have travelled until now.see my code.submission
•  » » » 4 weeks ago, # ^ |   0 Thanks, It seems easy now
•  » » 4 weeks ago, # ^ |   0 You could use disjoint sets too... Just put i and arr[i] in same set (union) and like size find size of each set, the answer is same for all the elements in the same set, ie, size of the set.
•  » » 4 weeks ago, # ^ |   0 Standard Disjoint Set problem
 » 4 weeks ago, # |   0  ll n;cin>>n;ll temp=n; int idx=0;ll mn_diff=LONG_MAX; while(psm[idx]=0;cnt--,idx--){ mn_diff=min(mn_diff,pt[idx+1]-n); if(n>psm[idx])break; if(n>=pt[idx])n-=pt[idx]; if(n==0)mn_diff=0; } cout<
•  » » 4 weeks ago, # ^ |   0 LONG_MAX gives you a "long long" value, but you are storing it in an "int".
•  » » » 4 weeks ago, # ^ |   0 no when i used mn_diff=1e18 it gives AC
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 1e18 is different that LONG_MAX. Both will give you different values, and if you don't store that values in a "long long", LONG_MAX can give you a negative value and 1e18 can give you a positive value (depends on the compiler). Sorry for my poor english xd ex:Codeforces submission Ideone submission
•  » » » » » 4 weeks ago, # ^ |   0 but i never used int, u could see above its long long.
•  » » » » » » 4 weeks ago, # ^ |   0 Sorry, I didn't see the "ll" :c Your code on my compiler prints the correct answer too.
•  » » 4 weeks ago, # ^ |   +1 UPDATE :: never use LONG_MAX on codeforces as LONG_MAX is same as INT_MAX on Windows, and codeforces uses 32 bit windows, so always use LLONG_MAX it is universal (2^63-1).
 » 4 weeks ago, # |   0 For problem E, could anybody tell me why PyPy 2 TLEs but PyPy 3 ACs?
•  » » 4 weeks ago, # ^ |   0 because Python 3 is much faster than Python 2 (especially more recent versions)
•  » » » 4 weeks ago, # ^ |   0 Python 3 is still slower than Python 2 on most counts, especially in competitive programming.It seems like it's only PyPy 2 that's slow. Even Python 2 ACs.
•  » » 4 weeks ago, # ^ |   +1 Just added my fast io got accepted in PYPY2 . Do check my submissionhttps://codeforces.com/contest/1249/submission/63196194
•  » » 4 weeks ago, # ^ |   0 Had it helped you ?
•  » » » 4 weeks ago, # ^ |   0 Thanks for making my submission work. I've never seen output buffering in Python like this before, will have to look more into it.
 » 4 weeks ago, # | ← Rev. 3 →   +1 My approach for problem D1 is keep removing the segments intersecting with maximum number of bad points .Is this approach correct ? My submission is giving wrong answer though My Submission
•  » » 4 weeks ago, # ^ |   0 I got WA on 9. Switched to iterate from left to right on bad points and keep removing segment with largest end point, and that passed.
•  » » » 4 weeks ago, # ^ |   0 Your approach is also nice.Still wondering what is wrong with our first approach .
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 I found out whats wrong.Take the following case5 1 1 2 2 5 3 10 7 14 14 15 Here if we try deleting segments with most bad points, we will first delete 3 10, then 2 5, then 7 14. But the correct approach is to delete 2 5, and 7 14.
•  » » » » » 4 weeks ago, # ^ |   0 You are right . Thanks !
 » 4 weeks ago, # |   0 Hack case for B?
 » 4 weeks ago, # |   +14 The problem-set contained better stories than all of my films combined.
 » 4 weeks ago, # |   0 How to prove this solution ?#include using namespace std; #define int long long int32_t main() { vector pw3; pw3.push_back(1); while(pw3.back() < 1e18) { int x = pw3.back(); x *= 3; pw3.push_back(x); } int q, n, sz = pw3.size(); cin >> q; while(q--) { cin >> n; int ans = 0; for(int i = 0; i < sz; i++) { if(ans >= n) break; ans += pw3[i]; } for(int i = sz - 1; i >= 0; i--) { if(ans - pw3[i] >= n) ans -= pw3[i]; } cout << ans << endl; } return 0; } 
 » 4 weeks ago, # |   0 In problem C2  // Wrong Answer /* for(int i = 0 ; i < 40 ; i++){ my[i] = (int)pow(3LL,i) ; } */ // Accepted Solution my[0] = 1 ; for(int i = 1 ; i < 40 ; i++){ my[i] = my[i-1] * 3LL ; } // This is my AC Code 63196491what is wrong with this line my[i] = (int)pow(3LL,i) ;
•  » » 4 weeks ago, # ^ |   +1 Overflow, my[i] can be greater than INT_MAX
•  » » » 4 weeks ago, # ^ |   +4 But I have defined int to long long
•  » » » » 4 weeks ago, # ^ |   +1 Oh sorry, I saw it later, below comment is correct
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +4 pow returns double, which can't represent all values of a long long (think about it: both are 64 bit types, therefore pigeonhole principle etc etc)
•  » » 4 weeks ago, # ^ |   +2 I could suggest you one thing, if I may.... Don't use inbuilt pow function, it's very deceptive sometimes..... Just to be on the safe side, you could make your own pow function using fast exponentiation....
•  » » 4 weeks ago, # ^ |   +1 pow(x) returns double, which is not enough for 1e18. Try using powl(x), which returns long double instead. P.S. Both pow and powl are inaccurate, try to avoid using them
 » 4 weeks ago, # |   +2 thanks for this amazing contest :)
 » 4 weeks ago, # |   -8 Sorry for my bad english, but the user named AHR9N has cheated, he asked me for the code of the problem B2, but I did not send. I think he needs to be severely punished
 » 4 weeks ago, # | ← Rev. 2 →   0 Oh,I can't get problem c2,problem c2 and problem e by using m2.codeforces in this contest. It told me that the statement is available.
 » 4 weeks ago, # |   0 Thanks for the contest:)
 » 4 weeks ago, # |   0 Can anyone give me the solution of Problem B2 using DSU?
•  » » 4 weeks ago, # ^ |   0 refer my submission: https://codeforces.com/contest/1249/submission/63209409
•  » » 4 weeks ago, # ^ |   0 you can also see 63213320
 » 4 weeks ago, # |   0 In question https://codeforces.com/contest/1249/problem/A A. Yet Another Dividing into Teams from equation it means that difference should not be 1. Statement says difference should be strictly greater than 1. And test cases are aiming just for difference not equal to 1. There is a bit ambiguity . As for input 1 1 1 1 1 1 Answer should be 5. In test cases answer is either 1 or 2.
•  » » 4 weeks ago, # ^ |   0 All students have distinct programming skills!
•  » » » 4 weeks ago, # ^ |   0 You got me or you are trying to make fun of it in a way??
•  » » » 4 weeks ago, # ^ |   0 Thank you
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 The second line of the query contains n integers $a_1,a_2,…,a_n$ ($1≤a_i≤100$, all $a_i$ are distinct), where $a_i$ is the programming skill of the i-th student.
•  » » » 4 weeks ago, # ^ |   0 Thank you
 » 4 weeks ago, # |   0 Is the round unrated? Why the ratings are not updated ?
•  » » 4 weeks ago, # ^ |   0 Cause you are not rated in this round. You have to participate at least 3 contest in div2.and your solution was skipped-- probably you have break any Terms of agreement of codeforces.
 » 4 weeks ago, # | ← Rev. 2 →   0 Problem F is basically the same as BOI 2017 day 2 "Cat in a tree"
 » 4 weeks ago, # | ← Rev. 2 →   0 Edit: I was mistaken, please ignore. Original messageThere's a typo in problem F:"OutputPrint one integer — the maximum total weight of the subset in which all pairs of vertices have distance more than $k$."I think you mean "distance no more than $k$"?
•  » » 4 weeks ago, # ^ |   0 No, distance between any pair of selected vertices should be greater than k
•  » » » 4 weeks ago, # ^ |   0 Oh right, I misread the prose in the problem description and thought there was a contradiction.
 » 4 weeks ago, # | ← Rev. 2 →   0 If I modify problem A to..like find minimum number of teams you can form if no two students i and j such that |Ai-Aj|<=k may belong to the same team (i.e. skills of each pair of students in the same team has the difference strictly greater than k). So if N be the no of students then I can solve it in O(NlogN + Nk^2). is there ant faster approach if any one can suggest???
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Maintain a sorted array. Pick the first element(lets say a), then find the upper bound of a+k. Keep on doing the same thing for this new element until you reach end of array and also maintain the elements which have been allocated a team. Pick the next element in the sorted array which has not been allocated a team yet and repeat the above steps and increment the number of teams. This approach should be O(NlogN).
•  » » » 4 weeks ago, # ^ |   0 No worst case complexity of your idea is O(N^2) Consider the case of N consecutive numbers with k=N;
•  » » » » 4 weeks ago, # ^ |   0 How?
•  » » » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 just apply your idea and see... pick your a(first element of sorted array) in search of a+k (i.e. a+N here) you will traverse the whole array(end of array) but you will not find it.. Note1 you have picked just 1 element in 1 traversal do same for 2nd, 3rd and so on... so N(N+1)/2... O(N^2)complexity……. also Note2 you can't say here for this very case to use binary search(however here may work) bcz in general solution binary search will not work.
•  » » » » » » 4 weeks ago, # ^ |   0 I won't traverse the whole array. I would just binary search and why would it not work in general?
•  » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 not work means complexity will become even worst bcz at every such a+k you need to do binary search prev=a; curr=a+k; next a+k+k;..... so on and every time cost is logarithmic time. Also there might be case that a+k doesnot exist but a+k+2 or a+k+5 exist here these will be included in the same partition but then how you will handle those cases using binary search.... Just think once what is your complete idea and check the complexity... once done I will be thankful and love to know that.
•  » » » » » » » » 4 weeks ago, # ^ |   0 I think Brute_Forced approach is O(NlogN)
 » 4 weeks ago, # |   +5 Why have the rating changes been temporarily rolled back ?
•  » » 4 weeks ago, # ^ |   +9
•  » » » 4 weeks ago, # ^ |   0 Oh.. ! Great that it's being taken so seriously !
 » 4 weeks ago, # |   +2 Stop naming test cases as "queries", ffs.
•  » » 4 weeks ago, # ^ |   0 This is not the first time you are saying this. But I don't think it makes any difference. It is okay until and unless it is not creating any confusion in the problem statement. Isn't it?
•  » » » 4 weeks ago, # ^ |   -8 And it does create confusion because queries usually mean something else.
 » 4 weeks ago, # |   0 So when on earth can our rating be back?
•  » » 4 weeks ago, # ^ |   0 It's back for me.
 » 4 weeks ago, # |   0 I got plagiarism mail for the following solution coincided https://codeforces.com/contest/1249/submission/63187125 with another guy solution. However my first accepted solution for this problem was https://codeforces.com/contest/1249/submission/63184980. So the thing of plagiarism, I guess is completely irrelevant.
•  » » 4 weeks ago, # ^ |   0 Don't use IDEOne for coding.
•  » » » 4 weeks ago, # ^ |   0 Is there any way to restore my credits for this round, I was unaware regarding Ideone thing.
•  » » » » 4 weeks ago, # ^ |   0 Try appealing to the problemsetters and the organizers. I tried a few contests back, didn't help. Now I only use my personal IDE.
 » 4 weeks ago, # | ← Rev. 2 →   +20 Is it ok, what a few participants 1600+ rating got it updated after contest?
 » 4 weeks ago, # |   0 Yesterday after the end of the contest the rating predictor should (+2) usually the predictor never turns out to be wrong if i don't get system testing failed. In fact i get +1 extra with the rating change is showed by the predictor. But today i see it is (-3) turns out predictor changed its value. This never happened before. So much difference from the value it showed yesterday. i don't understand why.
•  » » 4 weeks ago, # ^ |   0 I think Rankings have been changed because of Plagiarism checking. That has led towards rating change
 » 4 weeks ago, # |   0 i try to solve D1 by using activity selection problem but it gives me WA on test case 14.so i would do activity selection for K times and of course for each activity selection it will gives you as many as segments which not intersect with each other.if you do it for K times then you will get points which covered at most K times, i couldn't think the corner case for my solution.