By awoo, history, 3 years ago, translation,

Hello Codeforces!

On February 16, 18:05 MSK Educational Codeforces Round 38 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 Div. 2. 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 prepared by Ivan BledDest Androsov, Sahand Xahandd Alitanloo and me.

Thanks Mike MikeMirzayanov Mirzayanov for great system Polygon!

Good luck to all participants!

UPD: Since there will be another Div. 2 contest soon, the hacking phase will be shorter (only 12 hours). Before CF Round 464 we will actualize the registrations in such a way that Div. 2 will be officially registered, and Div. 1 participants — unofficially.

UPD2: We also have a message from our partners Harbour.Space:

We are excited to announce that some of the world’s strongest teams will come to our Hello India x Russia Programming Bootcamp: MIPT and all top India’s Universities that qualified to the World Finals!

As always, the boot camp isn’t only about the training — we’re in the process of getting renowned keynote speakers from all over the globe to come and speak about life and all the opportunities at your fingertips after ACM-ICPC.

We look forward to seeing you all there this spring! For those of you who haven't registered, there's still time.

Register here

If you have any questions we can help you with, please connect with us:

Phone number: +34 674 291 422 Email Address: hello@harbour.space

UPD3: Editorial is published

• +202

 » 3 years ago, # |   +34 sooo fast people, wait we're still in a contest
 » 3 years ago, # |   +7 lol
 » 3 years ago, # | ← Rev. 2 →   +1 Imagine if we have rated contest every day! That actually happened for three days. Actually four(Saturday contest)
 » 3 years ago, # |   0 Score distribution?
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 Will be announced later as usual.but when "later" is?UPD: Educational round!! nileshjha19
•  » » » 3 years ago, # ^ |   +9 Educational round. ACM ICPC style. All problems have same value.
 » 3 years ago, # |   +5 Hat-trick of Rated Contests! :O
 » 3 years ago, # |   +8 Wow! Rated educational rounds are really great initiative for div2 contestants. Just ❤️ it!
 » 3 years ago, # | ← Rev. 3 →   -26 Is it Rated?
 » 3 years ago, # |   +2 Will educational rounds normally have 7 problem from now on?
 » 3 years ago, # |   +1 A back to back series of contests continues.......
 » 3 years ago, # |   +30 Wow, four rated contests in four days. Keep it going Codeforces! :)
 » 3 years ago, # |   0 just like if we are in the heaven , Contests everywhere :D
 » 3 years ago, # |   +14 Maybe educational rounds should be rated for div 3 :) just like atcoder abc contests.
•  » » 3 years ago, # ^ |   0 I think div3 is a good idea
 » 3 years ago, # |   +12 many contests! it's a chance for me to rescue my rating.
•  » » 3 years ago, # ^ |   +27
 » 3 years ago, # |   +31 Let's see how many hacks halyavin takes in this round! XD
•  » » 3 years ago, # ^ |   +11 1e9+7
•  » » 3 years ago, # ^ |   +3 0x3f3f3f3f I think.
 » 3 years ago, # |   +1 Codeforces seems to be quite excited. 4 rated contests continuously. Wow !
 » 3 years ago, # |   +2 It's a week of "Love to Contests" !
 » 3 years ago, # |   +20 My life these days,Eat — sleep — codeforces contestREPEAT
 » 3 years ago, # |   +6 Our recursive routine these days : contest->upsolve->contest->upsolve->contest..........
 » 3 years ago, # |   0 Is hacking solution outside the room allowed during the contest time ?
•  » » 3 years ago, # ^ |   +14 Are there rooms in this contest?
 » 3 years ago, # |   +36
•  » » 3 years ago, # ^ |   +4 I really wonder who that person is.
•  » » » 3 years ago, # ^ |   0
 » 3 years ago, # |   0 Okkk.............
 » 3 years ago, # |   0 Help: what is the difference between an educational contest and an ordinary contest?
•  » » 3 years ago, # ^ |   +9 ER features trivial/classic problems, don't be surprised if you have seen some of them before
•  » » 3 years ago, # ^ | ← Rev. 2 →   +4 Ordinary contest: Different points on different problems Hacks in-contest (you can't hack after round) Educational contest: Problems have the same points (like ACM — ICPC rules) Hacking phase opened after round. Usually it's 24 hours (but it's 12 this time).
•  » » 3 years ago, # ^ |   +67 Ordinary contest: Computer is used to test solutions.Educational contest: a human named halyavin is used to test the solutions.
 » 3 years ago, # |   +9 halyavin is waiting for this contest.
 » 3 years ago, # |   +3 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 3 years ago, # |   +18 I'm getting codeforces crashes in the last 3 contests I've been participating, I cannot submit solutions...I'm getting: Ooops! Something has broken down in Codeforces. Do not panic, you can try to reload the page or return Home. Anyway we will carefully read megabytes of logs, analyze stacktraces and fix the problem.etc... and pictures of bug "ALL YOUR BUG ARE BELONG TO ME" — "I'd rather feel they're mine"...
•  » » 3 years ago, # ^ |   0 This has also been happening to me sometimes in contests
•  » » 3 years ago, # ^ |   0 clear your caches and cookies, maybe your csrf token is not refreshing
•  » » » 3 years ago, # ^ |   0 My friends lokpati and bitcyber face similar issue in almost all contests. Whenever they click submit button , it doesn't proceed to 'status' page. Also they do not get any error message like mihelifi . MikeMirzayanov can you look into the issue?P.S: They have pretty fast Internet connections.
•  » » » » 3 years ago, # ^ |   0 look for errors in console, also see post request in network tab, what do you see when you submit?
•  » » » » » 3 years ago, # ^ |   0 See the little spinning icon on the right side of submit button(which usually appears for a moment after you click submit) .In their case, it keeps spinning and this page does not proceed to 'status' page.Same happens even if they submit code via CF editor. I hope I've made the point clear.
•  » » » » » » 3 years ago, # ^ |   0 It happens to me when i go back and forth after putting a hack testcase for someone. To fix that, i copy url, close the tab. reopen in tab and paste url. on the surface it seems once a pub sub connection is opened in a tab, it doesn't allow new connections unless old one is closed. I havent investigated much though.
•  » » » » » » » 3 years ago, # ^ |   0 Will tell them to use this trick. Thanks
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   0 I faced a similar problem, here is a verified solution:It happens when you write like this:some code{}instead write this way -some code{}It may appear silly, but it works, see it for yourself.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 What???!!! :D Ok, we'll change the coding style too, if that's the issue. :D Thanks for your valuable suggestion.
•  » » » » » » 3 years ago, # ^ |   -6 Just try it once for the sake of it.Braces should be on seperate lines in your entire code.feel free to downvote if it doesn't work. Worked for me though :)
 » 3 years ago, # |   +11 How to solve C?
•  » » 3 years ago, # ^ |   +6 First, note that we are essentially just solving .So iterate over n, check if n2 - X is a square, and check whether m exists that satisfies the condition. The appropriate bounds for n are easy to find. Each TC will run in .
•  » » » 3 years ago, # ^ |   0 do we need to start the iteration from 10**9 ? Seems pretty large but maybe the loop doesnt run full?
•  » » » » 3 years ago, # ^ |   0 I used the bound mentioned below by barkingdog, so I iterated n from 1 to about . (Of course, after handling edge cases)
•  » » » » » 3 years ago, # ^ |   0 why do you need isqr method? doesn't casting double to ll just remove fractional part?
•  » » » » » » 3 years ago, # ^ |   0 To be absolutely sure, i think. Another example, when string has not more than 1e6 chars, many create char[100005];
•  » » » » » » » 3 years ago, # ^ |   +5 Do you mean char[1'000'005]? That's why I just use std::string.
•  » » » 3 years ago, # ^ |   +10 if we factorize the left side we can iterate over divisors of X
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 Can you explain the equation: n^2 - (floor(n/m))^2 = X? Why and how you derived it? rkm0959
•  » » 3 years ago, # ^ |   +6 Given x, first You have to find n, k such that n^2-k^2 = x, and second check and find whether n/m = k is possible.Since n^2 <= 4/3*x, the range of n is not that big, and you can easily match k for all n which satisfies x <= n^2 <= 4/3*x by check whether n^2-x is square. Then by calculate candidate of m = n/k, you can know whether n/m = k is possible
•  » » » 3 years ago, # ^ |   0 Sorry, but I didn't understand the n/m = k part. Also, can we say that find an m such that sqrt(n^2 — x) is a perfect square?
•  » » » 3 years ago, # ^ |   0 I want to ask u 1 thing that how do u have come to the conclusion that n^2<=4/3*x ?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +9 maximum number of zeros you can have is when m = 2, and it will be n^2/4.and x = ones ..so minimum value of x = n^2 — (n^2/4) (when m = 2) ; so x = 3/4 *(n^2) at least.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 minimum value of x or maximum value of x?
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 minimum value, x will be at least that much, in other cases when m = 3,etc. x will be even more
 » 3 years ago, # | ← Rev. 2 →   +18 How did you do D?
•  » » 3 years ago, # ^ |   0 Using Greedy & Priority queue, expand the routes by increasing order of cost of arriving concert.Since number of road is also small, you don't have to care about multiple visit.
•  » » » 3 years ago, # ^ |   +17 Essentially Dijkstra's algorithm starting with all vertices in the priority queue.
•  » » » » 3 years ago, # ^ |   +3 Doesn't that take too long? It's NlogM * all vertices.
•  » » » » » 3 years ago, # ^ |   0 You don't run Djikstra's on every vertex, you run it once but starting with every vertex in the priority queue. Initially every vertex is pushed with a weight equal to a[i], and then Djikstra's is the same from then on.
•  » » » » » 3 years ago, # ^ |   +6 You may create one "new" vertex and conect it with all other vertices puting the walue of the road equal to a[i]. Then run Dijkstra algo from it. And it will work N*logM.
 » 3 years ago, # |   0 https://pastebin.com/7f6WPztqCan anyone tell me why my code wouldn't work for D? It kept on failing on test case 3. :(
•  » » 3 years ago, # ^ | ← Rev. 2 →   +8 You can take a path through multiple cities that might be cheaper.Say the concert costs are 100 100 1 And the edges are 1 2 1 2 3 1Then it's cheaper to take both edges from city 1 to city 3. Your code only considers taking 1 edge.
•  » » » 3 years ago, # ^ |   0 Can anyone tell me what's wrong with my approach for D.link to my solution
 » 3 years ago, # |   0 Any idea of hacking yet ?
 » 3 years ago, # |   +10 is G using idea similar to solving dynamic connectivity offline.But now maintaining basis of cycles possible in that component also and maintaining components as dsu with weights on edges for maintaining xor distances. Or any other easy solution???
•  » » 3 years ago, # ^ |   +8 You may maintain the base of cycles by Gaussian elimination. Since the size of each base is not larger than 30, and each edge adds at most one number to the base, we can easily rollback the base in dynamic connectivity.
•  » » » 3 years ago, # ^ |   +5 How to solve F??
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   +8 There is a simple solution: dp[m][mask] — best answer if we considered first m characters of the string and a mask of erased substrings.Let's try to speed it up. If there are two states dp[m1][mask1] and dp[m2][mask2] such that the lengths of strings in these states are equal, but dp[m1][mask1] < dp[m2][mask2], then we are not interested in state dp[m2][mask2] at all. So let's change our dynamic programming to dp2[m][mask] = 1 if we can reach this state with optimal answer (and otherwise it's 0).To calculate it, you have to iterate on the ''layers'' of states (here by layer I call a set of states with equal length of resulting strings) and find the minimum character that allows to go to the next layer from the current one.Its complexity is , but in fact it's pretty fast since most states are unreachable.
•  » » » 3 years ago, # ^ |   0 Isn't it ?
•  » » » » 3 years ago, # ^ |   0 If we consider xor to have complexity O(1), then it's since checking if a number belongs to the base can be done in time .
•  » » » » » 3 years ago, # ^ |   0 Probably I need to wait for editorial. I don't understand how you are doing dynamic connectivity offline with gauss. For me it seems that when you merge two components you will need to do gauss in for numbers.
•  » » » » » » 3 years ago, # ^ |   +25 We don't have to store a separate base for each component. Since the graph always stays connected, we may instead store a base of all cycles in the graph (even if some of them are disconnected now, they will become connected later).
•  » » » » » » » 3 years ago, # ^ |   +6 That makes sense. Thanks.
•  » » » » » » » 3 years ago, # ^ |   +5 But if the graph is not connected. then we cannot do better than O(logC*logC) for merging two guass right?? Also in this question except to eliminate the logC in complexity,is there any other need of connected graph??
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 My (really ugly) code of that complexity passed in under 700ms. http://codeforces.com/contest/938/submission/35374477. It'd be fun if someone hacked it :D
 » 3 years ago, # |   -16 I have been trying 1 hour with this solution. Can someone plz tell me what is wrong with this solution https://ide.geeksforgeeks.org/s3ldY59oii
•  » » 3 years ago, # ^ |   0 I didn't completely go over your code yet, but using int for x seems a bit dangerous.You are calculating x * x sometimes, where x may run up to 105. Yet you used int for x...
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 I defined int as long and long. And i also checked for random 100 cases > 1e8. No time limet exceeded. I also compared 10 to 500 but no errors. But i cant find what is wrong. Ill again go to specialist. For the past few contests my rating are going down. But as i solve problems more and more my ratings are going down. Few contests back for some contests, i solved D, E etc but recdently im completely fucked up.
•  » » » » 3 years ago, # ^ |   +4 Excuse me but where did you define int as long long? I only saw you define ll as long long. Would you please point it out? Thx a lot.
•  » » » » 3 years ago, # ^ |   0 Few contests back for some contests, i solved D, E etc but recdently im completely fucked up its good to be frustrated. use that energy next time.
•  » » » » 3 years ago, # ^ |   0 #define f(i, x, y) for(int i = x; i < y; i++) #define all(X) X.begin(), X.end() why aren't you using templates, this can lead to bugs which will waste time at the least.
•  » » » » » 3 years ago, # ^ |   0 How it can be replaced by templates? 1) something like f(0, 100, [](int i){ //... }) imho isn't simpler than just for() 2) I have no ideas how to make same with templates(I don't use such macros, I don't think they give speedup)
•  » » » » » » 3 years ago, # ^ |   0 I was wrong. I think they are fine. Just need few more brackets to be sure.Personally i think it might give speed up to people who make typo when trying to type faster (like me). Those typos sometimes irritates and takes brain bandwidth.
•  » » » » » » » 3 years ago, # ^ |   0 template 2 isn't fine: vector> table; auto it = table.begin() + i; sort(all(*(it++))); //expected sort(table[i+1].begin(), table[i+1].end()) //after macro substitution sort((*it++).begin(), (*it++).end()); //which means sort(table[i+1].begin(), table[i+2].end()) //->ERROR 
 » 3 years ago, # |   0 could someone help me with problem B my code
•  » » 3 years ago, # ^ |   0 Try 2 600000 800000
•  » » 3 years ago, # ^ |   +1 Here's my code: https://pastebin.com/attptiBjBasically, the key thing for B is to Make sure that if you are moving simultaneously In order to make sure you don't over or undercount intervals, try each interval. Find the minimum distance from current start to the next interval greater, and current end to the previous interval smaller, then shift whatever is closer.This prevents you from moving a large interval and missing certain intervals.So for start = 1, end = 10^6. If the intervals are 1, 500000, 600000, you don't want to be double counting 400000+500000, because if you moved 400000 on both sides, then you only have to move an additional 100000 from start to get to 500000.Constantly update start and end with the new closest intervals to count correctly.You also want to break out of the program and return when start and end intersect, which signals that you have seen all the intervals so you should exit.
 » 3 years ago, # |   +9 In problem C,I wonder we can hack only with testcases equal to one, but how about those coder whose solution may got time limit exceed due to more testcases?
•  » » 3 years ago, # ^ |   0 Main tests will handle that issue.
 » 3 years ago, # |   +2 Problem C: I'm really confused by the case2,can anybody express it?thanks so much
 » 3 years ago, # | ← Rev. 2 →   0 What is the difference between these two solutions ?WAACHow priority queue works in both the cases?
 » 3 years ago, # |   0 What's "Unexpected verdict" when I try to hack others?
 » 3 years ago, # | ← Rev. 2 →   0 del
 » 3 years ago, # |   0 Idea for E?I find some equation but it is O(N^2)...
•  » » 3 years ago, # ^ |   +48 For E. First by sorting, compress the array as (number, occurrences). Now, we will calculate how much time each number will by added in our summation. Let's look at this number x — say there are u occurrences of x, and there are v numbers that are larger than x. Then, x appears in our summation if and only if the v numbers that are larger than x appear AFTER at least one x appears. The "probability" for this is , so the number of permutations that add x to our summation is . Now it's just some partial sums, easy calculation. Time Complexity just for sorting.
•  » » » 3 years ago, # ^ |   +3 Ohhh.. I see... Thanks!
•  » » » 3 years ago, # ^ |   0 But is there another way of calculating the number of ways for all v's to be after x? I don't know how probabilities work in this kind of cases so another solution would be clearer. This code seems very nice but i can't understand the part with binom(n,c) .
•  » » » » 3 years ago, # ^ |   0 That's because the numbers which are larger than x should appear after at least one x,but the numbers which are smaller than x could appear anywhere.So you have to location the smaller numbers,which're (c is the size of smaller numbers),and c! for every permutation,then the larger numbers(or equal numbers) should fill the last positions,which is (n - c - 1)!,and the position for x is settled.
•  » » » » » 3 years ago, # ^ |   0 Ohhh, ok, thank you very much!!! Now i got it.
•  » » » » 3 years ago, # ^ |   0 can u tell me what inv[] and ifac[] mean ?
•  » » » » » 3 years ago, # ^ |   0 inv[i] is the modular inverse of number i and ifac[i] is the modular inverse of i! (i factorial). You can learn about it on the internet. It is the way of calculating combinations for large numbers.
•  » » » » » » 3 years ago, # ^ |   0 Ok, thank u.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 why the "probability" for this is u/(u+v)? isnt it u!*v!/((u+v)!)?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   0 Since there are u+v numbers which are not small then x, x appears if and only if the first of the u+v numbers is equal to x. There are u numbers same as x, the probability is u/(u+v)
 » 3 years ago, # |   0 can i hack soultions if i haven't submitted any solution? Does it count for any rating changes?
•  » » 3 years ago, # ^ |   0 yes you can . no it won't be counted .
 » 3 years ago, # | ← Rev. 2 →   +14 Yazdan_ra is a genius cheat! lol!! he submitted multiple solutions for the same question from another account Double-D (owned by him) in which a specific case will fail and then he hacked all of them from his real account!!! ![ ]() isn't that totally unfair!
•  » » 3 years ago, # ^ |   +11 Yeah, that's definitely bannable.
•  » » 3 years ago, # ^ |   +6 Hacking doesn't benefit the hacker in educational rounds, apart from getting a green plus next to your name in the standings.
•  » » » 3 years ago, # ^ |   0 Is the prelim standing final for div2 rating changes? P.S. : I haven't participated in the contest.
•  » » » » 3 years ago, # ^ |   +6 No. Ratings will be updated after the 12 hours when after the actual system tests finish.
•  » » 3 years ago, # ^ |   +30 Poor fella doesn't know hacking will not affect his rating.
•  » » 3 years ago, # ^ |   +21 That is just stupid. One has no profit of hacking himself in this round.
•  » » 3 years ago, # ^ |   0 So in a way he hacked the hacking system ...lol
 » 3 years ago, # |   +3 Why does the meaning of the term "submatrix" in task C differ from conventional one? "A submatrix of a matrix is obtained by deleting any collection of rows and/or columns." https://en.wikipedia.org/wiki/Matrix_(mathematics)#SubmatrixHere "submatrix" means some square area of adjacent elements. That's misleading!
 » 3 years ago, # |   +22 There is no need for System test, we already have one halyavin :D
•  » » 3 years ago, # ^ |   0 Hahahahahaha
 » 3 years ago, # |   0 Can anyone tell me what's wrong with my approach for D. link
 » 3 years ago, # |   0 anyone can tell me the difference between GNU C++ 11 & GNU C++ 14?this one is my submission during the contest, which got tle on testcase 37.35369457 (C++ 11)and this one is my submission right after the contest, which is exactly same code with above, and got ac.35370185 (C++ 14)only difference between two submissions is the language i choose...got confused
 » 3 years ago, # |   +20 Lel, in my language vowels are considered to be 'a', 'e', 'i', 'o', 'u', and I didn't read that there was 'y' as well xD
 » 3 years ago, # |   0 What's with the time and memory limits in codeforces rounds? I find them way too harsh. Today I got TLE on F with an O(n2) solution (if we take that operations with integers take O(1) time), and memory limit exceeded on D using Dijkstra's algorithm. Of course, there may be something wrong with my code (Problem D, Problem F), but I don't see it. Do you? >:)
•  » » 3 years ago, # ^ |   0 Maybe it won't help you, but try to add ios_base::sync_with_stdio(false); cin.tie(nullptr);to your D submission. My solution is using Dijkstra to, and it passed tests and is not hacked yet. Also, recently I have TL due to missing io boost
•  » » » 3 years ago, # ^ |   0 That sped it up quite a bit, but it didn't reduce the memory consumption. :/
•  » » » 3 years ago, # ^ |   0 If I use "ios_base::sync_with_stdio(false); cin.tie(nullptr); " what is the benifit of this ???
•  » » » » 3 years ago, # ^ |   0 By default, you can mix c++-style io (cin cout) with c-style(scanf printf) without any problems (it should work as expected), but results in performance. ios_base::sync_with_stdio(false) — disable this sync-tion. cin.tie(nullptr) disable sync-tion of cin and cout.
•  » » 3 years ago, # ^ |   +3 Not sure, but in F it seems (for * (for auto) * (for .. state.second) might be n3.
•  » » » 3 years ago, # ^ |   0 I see now.
•  » » 3 years ago, # ^ |   0 use normal array for dist[] and link list for edges instead of vector?
•  » » 3 years ago, # ^ |   +3 It took me a while but I found the mistake. In the edge loop inside the while you put the weight into a variable that is declared as int, that makes it overflow and possibly means an negative loop so it makes sense that it is MLE. http://codeforces.com/contest/938/submission/35380385
 » 3 years ago, # |   0 In problem C,can anybody explain why the answer is 999954147 when n=36514,m=2? thanks so much
•  » » 3 years ago, # ^ |   0 you need to write one zero in four squares.i mean, you can write zero in (x, y) if x and y are both even, otherwise write onethen you can write 36514*36514*0.75=999954147 one(s).
•  » » » 3 years ago, # ^ |   0 yeah thank you ，i was stupid
•  » » 3 years ago, # ^ |   0 I think it should be 36514*36514-[36514/3]*[36514*3]
•  » » » 3 years ago, # ^ |   0 why?i think you mean you will put only one zero(0) in 3*3 square,but you can find 2*2 square which doesn't contain any zero(0)s.
•  » » » » 3 years ago, # ^ |   0 yeah i just see ，thanks
 » 3 years ago, # | ← Rev. 2 →   0 how to hack person ?
•  » » 3 years ago, # ^ |   0 For example, you can open submission page (like this) and press "hack it"
•  » » » 3 years ago, # ^ |   +12 Spasibo !)
 » 3 years ago, # |   +6 In C answer for 48 is 8 2 for many people but for 8 2 maximum possible ones are 55. Can someone tell where I am wrong. Thanks in advance.
•  » » 3 years ago, # ^ |   0 i think so，8*8-3*3，why is this wrong？
•  » » 3 years ago, # ^ |   0 maximum possible 1's = n*n-(n/m)*(n/m)
•  » » » 3 years ago, # ^ |   +8 yeah you are right，i was stupid
•  » » » 3 years ago, # ^ |   0 What is the max possible value of n and mIn question it is given 1e9 but can it ever reach 1e9?
•  » » » » 3 years ago, # ^ |   +3 max possible N will be sqrt((4*x)/3)
•  » » » » » 3 years ago, # ^ |   0 Thank you. Could you please tell how to find the maximum value. I was thinking something like this n*n*(1 — 1/(m*m)) = x so n*n = x if I assume 1/(m*m) to be small enough so n = sqrt(x).
•  » » » » » » 3 years ago, # ^ |   +3 n will be maximum when m=2 hence n*n-(n/2)*(n/2)=x therefore (3*n*n)/4=x hence n=sqrt((4*x)/3);
•  » » » 3 years ago, # ^ |   0 ok got it
 » 3 years ago, # |   0 Can anyone tell me if my approach for D is correct? The contest ended before I got to finish it..For each component of the graph, I will construct it's MST, because no answer for any node will contain an edge not present in the MST(needs proof).Then, I choose a root for each tree and start traversing from root to leaves(dfs2), and for each node I will update it's answer as following: ans[current]=min(ans[current],ans[child]+2*edge(current,child))The initial answer for every node is it's concert price.Then I will do another dfs(dfs3), this time; I will update the answer of the child with the answer of it's parent(going up).
•  » » 3 years ago, # ^ |   +1 It needs: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm And using MST doesn't help, because you need to use the sum of the weights, not the max.
•  » » » 3 years ago, # ^ |   0 MST for MinimumST. I still don't see where it doesnt work.Anyway, can you elaborate more? How do I apply Dijkstra on the graph?
•  » » » » 3 years ago, # ^ |   +1 cmon, i know you can do it by yourself, don't spam :) It is a simple algorithm, easier than Kruskal's or Prim :)
•  » » » » » 3 years ago, # ^ |   0 No no I know the algorithm very well, I also thought about using it in the contest, but I have no idea HOW to do it for every nodeI'll find out..Thanks a lot, you've been very helpful :D
•  » » » » » » 3 years ago, # ^ |   +2 Let's say a concert is a vertex. Create the graph that the problem gives to you but with weights doubled. Also, create edges from the concert to vertex i with weight a[i]. The distance between the concert and vertex i is exactly what you want so just start from the concert.
•  » » » » » » » 3 years ago, # ^ |   0 Very elegant solution! Thanks a loot.
 » 3 years ago, # | ← Rev. 2 →   0 I have been trying 1 hour with this solution. Can someone plz tell me what is wrong with this solution https://ide.geeksforgeeks.org/s3ldY59oii. No TLE . I also compared 10 to 500 but no errors. But i cant find what is wrong. Ill again go to specialist/pupil. For the past few contests my rating are going down. But as i solve problems more and more my ratings are going down. Few contests back for some contests, i solved D, E etc but recdently im completely fucked up.
•  » » 3 years ago, # ^ |   0 Your output for 3 is -1, but correct output should be 2 2. Don't be upset if u can't solve much problems. You do your best, and try to upsolve them after contest. Rating really doesn't matter, whether you are pupil or expert. (Sorry for bad english)
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Yes, Rating doesnt matter, but i cant find the simple error and i make many silly mistakes and if a new problem comes, only if i ve already seen it previously, i can solve it, else i cant. I dont know how many problems i need to see. I ve already seen more than 1500 to 2000 problems, and still not a CM or even expert, as i ll go down now.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 more problems you solve, more you will able to find the logic behind a problem. Again don't think that you are not CM or expert.
 » 3 years ago, # |   0 Do successful hacking attempts provide the challenger with extra points in educational rounds? I was lucky enough to make my first successful hack in an educational round, and wanted to learn about this since the scoreboard does not show any points, or changes in my standing. (i.e. rank)
•  » » 3 years ago, # ^ |   +2 No, hacking in educational rounds doesn't increase nor decrease your points.
•  » » » 3 years ago, # ^ |   0 Good to know. Thanks!
 » 3 years ago, # | ← Rev. 2 →   0 Can someone hack my solution for D?I sort edges, then I look at every edge and try to improve answer for every verticle:If I have an edge from a to b which costs d, and ans[a] > ans[b], I make ans[a] = min(ans[a], ans[b] + 2 * d); ans[b] = min(ans[b], ans[a] + 2 * d) otherwise.I do this stuff 50 times, then output the ans array.Sorry for my english btw.
 » 3 years ago, # |   0 who can explain dotorya's C? link
•  » » 3 years ago, # ^ |   +15 We should find such n and m, that It means , or t1 * t2 = X in his notation.It means that and and .Then check if condition holds and print n and m
 » 3 years ago, # |   0 When we'll be able to see tests on which solution was hacked?
•  » » 3 years ago, # ^ |   +4 Tests are visible after the end of hacking phase.
•  » » » 3 years ago, # ^ |   0 Thanks :)
•  » » » 3 years ago, # ^ |   0 hi, could you explain your solution for C? i see many solutions that use % 2 but can't understand their logic
•  » » » » 3 years ago, # ^ |   +7 I need to solve x = u^2 — v^2 = (u — v) * (u + v). So I factor x into 2 factors. But not all factors produce integer u and v. I can restore integer u and v from factors f1 = u — v and f2 = u + v if and only if f1 equals f2 modulo 2. Since the answer of the problem equals n^2 — [n / m]^2, I have n = u and can restore m from v.
•  » » » » » 3 years ago, # ^ |   0 thank you very much
 » 3 years ago, # |   0 The last was a bit difficult
•  » » 3 years ago, # ^ |   0 Well I don't think so. It's super easy, especially compared with round #462...
 » 3 years ago, # |   0 In problem D, why my solution that uses SPFA got TLE in the last test(test17), is it a requisite to use dijkstra to calculate the minimum route in this problem?
•  » » 3 years ago, # ^ |   +1 Of course,SPFA is always unstable.
 » 3 years ago, # | ← Rev. 2 →   +3 http://codeforces.com/contest/938/submission/35361791Can i know why i got hacked in TLE (prob.D) ? with dijkstra?PS. What a newbie's mistake !! everybody thank you !!
•  » » 3 years ago, # ^ |   +7 You can check the single vertex up to n times. If this vertex has degree n, you have O(n2) operations.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Your solution does't work with two components. Try this test4 21 2 13 4 11 10 1 10 Answer must be 1 3 1 3 P.S. Sorry,false alarm. Didn't read code correctly.
•  » » 3 years ago, # ^ | ← Rev. 4 →   +3 NoTalentBug you make unnecessary vertex run(n^2), look my solveExample: was g[k].cost = 9, you updated it g[k].cost = 8, but you RUN EDGES CYCLE for old value and new (Sorry for bad english) void Solve() { while (!pq.empty()) { auto top = pq.top(); pq.pop(); int64 v = top.second; int64 cost = top.first; if (g[v].cost != cost) continue; // it important !!!!!!! for (const auto& it : g[v].e) { int64 to = it.to; int64 costEdge = it.cost; int64 newCost = costEdge + cost; if (g[to].cost > newCost) { g[to].cost = newCost; pq.push({ newCost,to }); } } } } 
 » 3 years ago, # |   0 Waiting for rating?? SubSpring
 » 3 years ago, # | ← Rev. 2 →   +8 Where is the system testing?
•  » » 3 years ago, # ^ | ← Rev. 2 →   -20 There is no system testing. These are the final results. Now we are just waiting for the rating.(THE ABOVE INFO IS WRONG !!!)Sorry for that!
•  » » » 3 years ago, # ^ |   +9 There will be system testing brother. All the hack cases will be added and the solutions will be rejudged.
•  » » » » 3 years ago, # ^ |   0 Ahh the hacks will be added to everybody ? Sorry I did not know that. Good to know !
 » 3 years ago, # |   +31 Will the system testing and rating update happen before the next contest starts?
 » 3 years ago, # |   +37 Where is the system test?Where is the tutorial?
•  » » 3 years ago, # ^ |   +4 You can usually expect tutorial no later than 24 hours after the end of the contest (coding phase in this case).
 » 3 years ago, # |   +29 emmm..when will the rating change? Next contest will come.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +18 But the bad news is that the system test hasn't begun yet... There are still only two test cases for problem C. According to the rules, all the hacks will be added into test data and rejudge. I'm wondering why it's called final standings instead of current ones...
•  » » » 3 years ago, # ^ |   +16 AFAIK In every educational rounds after Hacking phase it says Final standings, open hacking phase finished  But after that System test starts.
 » 3 years ago, # |   0 when will be the tutorials be published for this contest?
 » 3 years ago, # |   +46 Here comes "Codeforces Round #464 (Div. 2)" and the ratings haven't been updated yet. So what will happen if some 1800-rating person who should gain +200 rating in the last round takes part in the #464?
•  » » 3 years ago, # ^ |   +19 If the ratings aren't updated before the contest, one possible solution is to evaluate the ratings of Education CF Round and then make it unrated for the people who became Div 1 in that round.
•  » » » 3 years ago, # ^ |   +10 that's a solution, but that would consume people's time and then after that make it unrated. Like I wouldn't want to participate if it's unrated for me, but it's hard for me to decide now, since I don't know whether it would be rated.
 » 3 years ago, # |   +35 So when will the rating change?The next contest is coming soon.And the editorial hasn't been published either.
 » 3 years ago, # |   +5
 » 3 years ago, # |   0 When will the editorials be published ?
•  » » 3 years ago, # ^ |   0 I do want the editorials too.
 » 3 years ago, # |   0 Can u write the tutorial for this Ed.Round pleaseI don't understand in which moment I should stop search the answer and write "-1" (938C - Constructing Tests). Could somebody help me with it?
 » 3 years ago, # |   0 what about the rating for div2?
 » 3 years ago, # |   +6 When will the system test begin?
•  » » 3 years ago, # ^ |   0 seems it is working now...
•  » » » 3 years ago, # ^ |   0 Yes,I see.
 » 3 years ago, # |   0 Holly Dijkstra, nobody hacked my D! For one second I did dijkstras from the cheapest cities, and in the other second I did iterations of bellman ford.
•  » » 3 years ago, # ^ |   0 You are a litter bit unlucky,bother. :D
 » 3 years ago, # |   0 is it rated??
•  » » 3 years ago, # ^ |   0 yes, only for div2
 » 3 years ago, # |   +4 If you try to use a case in which t=100 and all x=1000000000 in CUSTOM INVOCATION, then you will find an amount of solutions in problem C will get time limit at the last of sorted by Execution Time
•  » » 3 years ago, # ^ |   +1 The system test is really weak and we are forbided to hack with t over 1.I think that shall be a point for hacking
•  » » » 3 years ago, # ^ |   +4 Why are those solutions slow, are they doing more than sqrt(10**9) operations?
•  » » » 3 years ago, # ^ |   +5 If we can hack with t over 1,we have to wait much more time for the system test.
 » 3 years ago, # |   0 In Question C, for input = 21, why isnt "5 4" a valid solution?Suppose we have a 5X5 square with all 1s except on the 4 corners where we have 0s, then if I have to select a 4X4 squares, there are 4 squares of 4X4 I can choose and each of them would contain a 0.Please correct me if I'm wrong, help is appreciated.
•  » » 3 years ago, # ^ |   0 then if I have to select a 4X4 squares not "a" but all such 4X4 squares should be with atleast 1 zero
•  » » 3 years ago, # ^ |   0 Because we need to maximise the number of 1s.Therefore, the input 5 4 will likely generate a matrix like this 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 which have 24 1s.Indeed, if the problem asks for 24 instead, then 5 4 will be a correct solution.
•  » » 3 years ago, # ^ | ← Rev. 5 →   0 I think you misunderstood the task:You are given two integers n and m. You have to construct an m-free square matrix of size n × n such that the number of 1's in this matrix is maximum possible. Print the maximum possible number of 1's in such matrix. meaning that values in matrix must be arranged so that the number of 1's is maximum.For example, for n = 5 and m = 4 the maximum would be 241 1 1 1 11 1 1 1 11 1 0 1 11 1 1 1 11 1 1 1 1So, your solution is undermining the word "maximum". For 21 one of the answers might be n = 5 and m = 21 1 1 1 11 0 1 0 11 1 1 1 11 0 1 0 11 1 1 1 1
•  » » » 3 years ago, # ^ |   0 Thanks for your time. Got it. :)
 » 3 years ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).