Educational Codeforces Round 115 Editorial
source link: https://codeforces.com/blog/entry/95890
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Idea: BledDest
Idea: fcspartakm
Idea: fcspartakm
Idea: BledDest
Idea: BledDest
Idea: BledDest
1598G - The Sum of Good Numbers
Idea: BledDest
The easiest solution for C(in my opinion): 131432277
P.S. sum * (n-2) = (sum — a[i] — a[j]) * n => we can find for every a[i] all a[j] in O(n log n) using binary search
-
If you simplify that equation, you would get (a[i] + a[j]) = (2 * sum) / n, so basically this is just a 2-sum problem where the target value is (2 * sum) / n,
-
-
Can you please check my soln. I have used 2-sum approach but it is giving me WA on test 2. 131563369
-
I also tried the same way and getting wa on 78th in 2tc..LostCoder16 can you pls tell me why it's wa.
solution: 131653903
-
I havent looked at the correctness of your algorithm but
ans = ans + c * d;
line has int overflow for sure.-
XD. Thanks, for mentioning this. now, after using it long it still showing wa on that tc. Can you please tell me why is it so?
-
Changing
ans = ans + c * d;
toans = 1LL*ans + c * d;
doesn't fixes anything.ans
is alreadylong long int
. Over flow is in multiplication ofc*d
, change this toans = ans + c*1LL*d
.Also
ll val = (n * (n - 1)) / 2;
has int overflow. Just havingval
of typelong long int
doesn't do anything.n
andn-1
are still ofint
type. Change this ton*1LL*(n-1)/2
.Also, next time just uses C++ 64 bit and
long long
everywhere.Also,
if (st.size() == 1)
is incorrect fix. You will still get WA onSpoiler
-
-
-
-
-
-
2 days ago, # |
IDk why but my solution for C gives TLE on Test 17 even though it's the exact same solution as the tester's : https://codeforces.com/contest/1598/submission/131542518
2 days ago, # |
Why using unordered_map gives TLE in this question... searching elements using hash map should be faster than the map which takes log(n) time to search instead.
131514464
Also I don't get it... how by adding just these 2 lines which where on a blog,mp.reserve(1024);
mp.max_load_factor(0.25);
solves the problem of TLE and my soln gets accepted.
131524838
Then I tried a custom hash function rather than the built-in hash function. Which also got accepted. Also the same solution gets accepted in python using dictionaries which also uses hashmap.
Does this mean that the C++ built-in hash function is not good ?
131520347
I tried to find but didn't get some concrete answers when to use map or unordered_map ?
Or using custom hash is better not ?
Please if anyone can help it in.
-
As you mentioned that solution with python dictionary got accepted and Thallium54 suggessted in reply that c++'s hash function is deterministic, so I searched for python's and found this here, python uses a hash function which is deterministic within a single run.
Also the custom hash function which you are using in c++ solution is also deterministic within a single run.
-
Note to self: ALWAYS use custom hash function when dealing with unordered map no matter how unnecesary in a codeforces contest
They seemed to be difficult during the contest,but now,I think them is not really tricky.Why I have feelings like this?How can I deal with it?
2 days ago, # |
Nice solution for D!
2 days ago, # |
I suppose that the time complexity of F should be O(n2n+AlogA)O(n2n+AlogA) instead of O(2n+AlogA)O(2n+AlogA). (:
Could someone tell me if there are some mistakes?
2 days ago, # |
Any other solution for problem D?
2 days ago, # |
In Problem D, I don't understand why the only bad triples are (xa,ya),(xb,ya),(xa,by). Isn't there a possibility of having three same topics, such (1, 1), (1, 2), (1, 3)? I've been looking at the explanation for so long but still can't figure it out :(
For D, can someone explain to me why there can't be a triple of the form [(Xa, Ya) , (Xb , Yb) , (Xa, Yb)] ? EDIT: I figured it out, it's actually the same thing except that the third pair is the central one, instead of the first.
46 hours ago, # |
For 1598C:
No, you don't have to use map in such a hacky way (or in another word, full of patches).
======================================
Instead of keeping a map of all elements, we keep a map for number of first i items ([0, i-1])
So the core logic can be much more easier:
in C#:
for (int i = 0; i < n; i++){
// update the answer
if (cnt.ContainsKey(target - data[i])) answer += cnt[target - data[i]];
// update the cnt map, for (i + 1) to use.
if (!cnt.ContainsKey(data[i])) cnt.Add(data[i], 0);
cnt[data[i]]++;
}
or in C++:
for (int i = 0; i < n; i++){
// update the answer
answer += cnt[target - data[i]];
// update the cnt map, for (i + 1) to use.
cnt[data[i]]++;
}
i tried to add photo for my comment but the comment become empty any one can help me
25 hours ago, # |
In problem D can anyone please explain why we won't be overcounting in the editorial solution?
15 hours ago, # |
Regarding problem D, I have a question, and I want a simple answer The first is where the values in this equation (n — 1) * (n — 2) / 6 come from. I know it's about knowing the number of ways to choose, but I don't know where the division by six came from and why we subtracted it from one and two
-
You can have an overview of basic combinatorics. It is like NC3,that means you have to select any three out of N so when we apply this , it becomes N!/(3!*(N-3)!) , you can expand N! as N*(N-1)*(N-2)*(N-3)*(N-4)... and so on, you can see that (N-3)! which is in denominator will cancel the numerator from (N-3)*(N-4)*(N-5)........., and that last you will be left with (N*(N-1)*(N-2))/3! and 3!=3*2*1=6, so at last it becomes N*(N-1)*(N-2)/6.
5 hours ago, # |
Alternative solution for 1598D - Training Session. I did see restriction that all problems pairs of parameters are different, but I had no idea how to use this fact. My solution doesn't rely on this fact at all. Solution turned out to be much harder so I wasted a lot of time to implement it during round.
Here is main idea. Think of how to calculate all triples with different topics.
Apply the same idea to problem's difficulties. We count something twice. What to do?
4 hours ago, # |
Detailed description how to implement 1598E - Staircases in O((n+m+q)log(n+m))O((n+m+q)log(n+m)) time and space.
3 hours ago, # |
A slightly different solution of 1598F - RBS.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK