Hello! Codeforces Round 867 (Div. 3) will start at Apr/24/2023 17:35 (Moscow time). You will be offered 6-8 problems 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 a rating of 1600 or higher, can register for the round unofficially.
The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.
You will be given 6-8 problems and 2 hours and 15 minutes to solve them.
Note that the penalty for the wrong submission in this round 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 participant of the third division, you must:
- take part in at least five 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, and Vladosiya for coordination of our work. Problems have been created and written by: diskoteka, pavlekn, playerr17, isosto.
We would like to thank: pashka, purplesyringa, Alexdat2000, I.Gleb, Serik2003, TkachDan, maksimb2008, _--, 74TrAkToR, Gornak40, ut-k8g, Rudro25, Jostic11, yorky, tolbi, AhmetKaan, Splatjov, BF_OF_Priety, vrintle, KoT_OsKaR for testing the contest and valuable feedback.
Good luck!
UPD: Editorial
Problem A: find missing space
Really excited for this contest. Don't know why.(◠‿◠)
as a tester, I can assure that problemset is perfectly balanced , all problems are interesting and I recommend to read all the problems
Sure.
As a participant, I will appreciate the work of authors and testers. Thank you for the contest!
As a !non-Tester, I tried to solve problems and give proper feedback. glhf
Can You AK ?
such an aesthetic looking as a tester comment !! cool
As an author, I wish all <1600 participants getting their free expert this round!
practically and theoretically not possible
:D
Bro, That's surely a joke. No need to take everything serious in life. Chill out and enjoy every bit of it.
:D :D :D From the downvotes, I think you're right.
Lesson learned: Laugh at every nonsense on codeforces
Don't think because of downvotes. I mean in general you should be not be serious all the time. It's not related just to codeforces. It applies to your daily life activities too. Just be chill and not serious all the time.
1) You are saying not to take things seriously. but your username(handle) tells different story.
2) I am 90 % sure, your spelling for LOSER is wrong.
xD
this is gonna be my first contest! wahoo!
welcome
Hope you are feeling better.
not 100% but better
Yes Sir.
As a participant, I will achieve a 4 long streak of losing rating in div3
it's not related to this blog :
can some one give me the list or easy to medium problems for DP to kickstart my learning ( like any difficulty wise or something ) for beginner level to medium and you can share any resources or suggestions ....
Thanks in advance!
DP contest at Atcoder
Is it for beginners?? Because one's i solve basic questions then i can move to contest problems
It is a collection of most of all basic types of dp and there is a basic problem of each type
i believe the first few are easily solvable by beginners in dp
here is a list of category wise dp problems : https://leetcode.com/discuss/general-discussion/1000929/solved-all-dynamic-programming-dp-problems-in-7-months
Really excited for this contest. Looking forward to becoming a pupil soon:)
How can we be a tester? Plz don't downvote.
As a non tester....... how to be tester? (I thought only purple+ can test).
you can contact with the co-ordinator
hope to become an expert
You will.
Seeing by the graph you have been grinding lately when people were sleeping. That will surely pay off my Friend. See you after blue colour Sir.
Thx bro
Give me contribution
How to hack a solution during contest?
You can't in div3 or edu rounds. They have their seperate period of time for hacking after the contest.
But for Div2 you can try that. Just lock the problems and go to room section. And start watching other people solution if you found some counter-testcase hack it.
When the contest ends in some of them there is a phase called: The Open Breaking Phase. And it is in this phase that you must enter someone's solution and press the "Hack!" Soon you are given a choice on how you will hack: with a generator or a manual hack? For the generator you write the code for the test. For a manual one, you write the test by hand. But you can't hack during the contest, only after it.
yayyy my first contest!! let's so how it goes
Welcome to the community on the behalf of specialist community Sir. Hope you have great time and learning.
Please provide hints and proofs for the problems along with editorials
It helps in upsolving and understanding concepts for beginners instead of directly jumping to solutions :)
Thanks
This is my first round in Codeforces. I really want to get more ratings.
hoping for 160 + Delta. feels like mission impossible... xD
Same here.
well, Mission Failed. https://codeforces.net/contest/1822/submission/203346533
AC submission right after contest.
Finished my F question 2 minutes after contest... Suuuucks.
I solved F before 2 min left.
I'll try my best, wish me luck
glhf
Hope everyone after this contest will change color:)
*positive change
sure, Did you have a good contest?
yes :), wbu?
I have AC A,B,C,D . A good contest :)
congrats! 1st account?
Thank you! I have an another account but its performance is not good so I use unrated account :) And, how about you? How many problems did you accepted? (and Why can you go to Specialist :))
Ohh good to hear. Yesterday, mine 1st 6 questions were accepted :). I got to specialist because I practice C questions a lot :)
I've participated in more than 5 rated contests and my rating is <1900 why I'm not in the official standings table?
This is a div 3 contest which is rated only for accounts having less than 1600 rating.Your rating is greater than 1600,so you're not an official participant.
The blog mentioned 1900, right? 2nd bullet in 5th paragraph?
That just mean that your are a trusted participant
You are a participant of the third division if and only if you currently have rating less than 1600. This can be seen in the fact that only < 1600 rated participants are rated in a Div.3 contest.
If you are a trusted participant of the third division, it is assumed that you must be a participant of the third division (i.e. have rating < 1600). The two constraints are extra for determining if you show up on the official leaderboard.
Here "do not have a point of 1900 or higher in the rating" means that if you have reached 1900 rating and then dropped back to < 1600 rating, you will not be considered a trusted participant of the third division and you will not show up on the official leaderboard. But the contest will be rated for you.
You are not a participant of the third division; thus you don't show up on the official leaderboard.
I agree that the wording is quite unclear.
Got it. Thank you
is there anyone else who did not read the problem C properly and just guessed the solution from sample test cases?
did g and f leak? Sudden increase in submissions for both
When can you submit in practice?
How to do G2?
Trick : number of factors of a number (10^9) that are perfect squares is less than 100
Somehow iterate over those factors...
I really should start learning number theory :(
$$$a[i] \cdot b \cdot b=a[k]$$$
if $$$a[i] \leq b$$$ then $$$a[i]^3 \leq a[k]$$$
if $$$a[i] > b$$$ then $$$b^3 \leq a[k]$$$
So you can solve problem in $$$O(N \cdot M^\frac{1}{3} \cdot logN)$$$
My solution works ~1200 ms.
what is M?
$$$M = MaxA = 10^9$$$
Wow that's quite simple
You need no fancy algorithms. Casework on if the common ratio is greater than the first term. For each $$$a_i$$$, enumerate the common ratio from $$$2$$$ to $$$(a_i)^{\frac{1}{3}}$$$ to count the number of triples where the common ratio is less than the first term where $$$a_i$$$ is the greatest term, and then if $$$a_i\le 10^6$$$, enumerate the first term from $$$1$$$ to (and excluding) $$$(a_i)^{\frac{1}{2}}$$$ to count the number of triples where the common ratio is greater than the first term and $$$a_i$$$ is the middle term. Remember to add the case of three equal terms.
This runs in $$$O(MAX^{\frac{1}{3}}n)$$$ using a custom hash unordered map. Implementation at https://codeforces.net/contest/1822/submission/203344438
Can u elaborate more on your explanation? I didn't get the common ratio part
My bad, the common ratio refers to $$$b$$$.
Thanks a ton for such a contest. Getting to Expert in style :)
Congrats bro.
Thanks a lot, mate :)
hey, please explain how you arrive at the solution for problem C.
Tbh, just observation through TCs.
Is G2 based on the fact like finding all unique GPs of common ratio upto 30 then doing some trick(no idea) to find GPs of ratio greater than 30 also using the GPs of common ratio upto 30?
Div.3: The contest where you can literally ask WolframAlpha to solve C, without reading description at all
Need to learn and know: Is it legal (fair) to search in a browser something like this during the contest?
yes (just read the contest rules if you are in doubt)
Finally Expert this time.
Such a great contest, really loved it, Problem F was the nicest and cute problem!
Thanks! We are glad that you enjoyed the contest!
As a pupil I'm becoming a newbie
Congratulations for the color change
What was the logic in problem C? I guessed from the test cases.
for D also, I found the pattern, but couldn't solve it
...
Same i just copy pasted from oeis.
For C, I saw that:
There are 4 edges with length $$$n$$$, which are the edges of the square as well.
In the square, the length of each adjacency edges is decrease from $$$n - 1$$$ to 1, and $$$n - 2$$$ to 1.
In the middle, there is an edge with length 1.
In conclusion, the formula I used without simplifying is: $$$4 * n + sum(n - 1) + sum(n - 2) + 1$$$ (Note that $$$sum(k)$$$ is the sum of the sequence from 1 to k).
n * (n + 1) + n + 2 I reached at this after a lot of rough work but its sad to see people directly guessed the test cases or used WolframAlpha/Oesis to guess the pattern.
Personally I also used WolframAlpha, because I didn't remember how to solve recurrence relations. I think this is a weakness of CodeForces, maybe especially in the lower ranks: a lot of problems are really math problems more than coding problems.
Incidentally, the problem could also be solved by brute-force without finding a closed-form solution.
it seems to me it gets compiler optimized, because otherwise this would be O(max) which is too high.
The compiler has optimized it somewhat (in a pretty impressive way actually) but it has not eliminated the loop, so it is still O(max). You can see the optimized code here: https://gcc.godbolt.org/z/K413jocrE
The inner loop is still present but it's very compact:
This is fast enough to do a billion iterations in 3 seconds on a reasonably modern CPU.
Is wolframalpha a math formula solver website? And Oesis is for finding sequences?
OEIS is the Online Encyclopedia of Integer Sequences: https://oeis.org/
Wolfram Alpha is a solver for mathematical functions in a very broad sense. For this problem you could feed it
26 + sum x=5..n (2x + 1)orf(4) = 26, f(n) = f(n - 1) + 2n + 1and it would calculate a closed-form expression for you.I saw problem E before in codechef but with minimum difference prob
Why TLE?
There are two problems here:
a check like
mp[v[j]*r] > 0is relatively costly because it will insert an element into the map if it didn't exist before. It would be better to use map::count() or map::find() to check if an entry is present without modifying the map contents.you should probably break out of the inner loop when
v[j]*r*ris larger than the maximum value in v, otherwise you end up doing 1000×N = 100 million iterations in the worst case.AC Thanks A Lot. 3900 ms.
Problem G1 :
when I use vector freq((int)1e6 + 1);
I got TLE
after replace it with int freq[(int)1e6+1];
I got Acc
How can this happens?? If I use array by luck I got Acc!! it's bad tests
Array allocation works in O(1) because it doesn't set the value. Vector allocation works in O(N)
but I allocate the array in every test to make it 0
memsetis faster than allocating a vector every time. But your solution might still be hackable.A: If a[i]+i-1<=t we can choose the i-th video.
B: First we can choose (i, j) where a[i]*a[j] is the maximum product and remove all other elements. We sort all non-zero elements in a[i] and consider the maximum non-zero product. If there's less than 2 non-zero elements, the answer is 0. If there's 2 non-zero elements, the maximum non-zero product is their product. Otherwise, there must be 2 elements with same sign, and their product will be positive. We need to pick 2 elements with same sign and maximum absolute value to get the maximum product.
C: The answer is (n+1)^2+1 (by looking at examples), but how to prove it? Well, if we change the size of a cinnabon roll from n-1 to n, we need to add 2*n+2 chocolate outside, add 1 chocolate and remove 2 chocolate inside, so we have ans(n)=ans(n-1)+(2*n+1). Therefore we can get answer by induction.
D: First if i>1 and a[i]=n, we have b[i]=(b[i-1]+n)%n=b[i-1], so b[i] cannot be a permutaion, then we have a[1]=n. If n is odd, (n+1)/2 is integer, then we have b[1]=a[1]%n=0, b[n]=(1+2+...+n)%n=(n*(n+1)/2)%n=0, so b[i] cannot be a permutaion. If n is even, let a={n, n-1, 2, n-3, 4, n-5, ...}, then b={0, n-1, 1, n-2, 2, n-3, ...} is a permutaion.
E: If n is odd there's no solution. If there's any char c that there are more than n/2 occurences of c, there's no solution because by the piegonhole principle, there are n/2 pairs of symmetric positions and there are more than n/2 occurences of c, so there must be a pair of positions occupied by c. Otherwise, solution must exist. To calculate the minimum number of operations, let's see what can we do in one operation: For something like ..a..b..|..b..a.. (where '|' denotes the axis of symmetry), we can swap (ba) to turn it into ..a..b..|..a..b.. and remove 2 bad pairs; for something like ..a..b..|..b..c, we can swap (bc) to turn it into ..a..b..|..c..b and remove 1 bad pair. In other words, we can remove 2 different bad pairs or 1 bad pair in one operation. So we can calculate the number of bad pairs of chars from 'a' to 'z' and then we can get the answer.
F: Let ecc[i]=max(1<=j<=n)(dist(i, j)), then the cost of the tree rooted at i is k*ecc[i], and the cost of moving root from 1 to i is c*dist(1, i), so the answer is k*ecc[i]-c*dist(1, i). We can calculate dist(1, i) by BFS, and to find ecc[i] we can find a diameter of the tree, if (u, v) is a diameter, then ecc[i]=max(dist(u, i), dist(v, i)).
G1: The number of good triples where b==1 is sum(cnt[t]*(cnt[t]-1)*(cnt[t]-2)) where t iterate over all values of a[i], so we assume b>=2 for other good triples. For each possible value of k, we can see the maximum possible value of b is not greater than sqrt(a[k]), so the contribution of k is sum(cnt[a[k]/b]*cnt[a[k]/(b*b)]) where 1<=b, b*b<=k. The complexity is O(n*sqrt(A)).
G2: To optimize the solution of G1, we can see that if a[k]/(b*b) is integer, let c=a[k]/(b*b), we have a[k]=b*b*c, then we have b<=cbrt(a[k]) or c<=cbrt(a[k]), so we can find all possible combinations of (b, c) in O(cbrt(a[k])). We can solve the problem in O(n*cbrt(A)) using Hashmap or O(n*log(n)*cbrt(A)) using Treemap for checking cnt[t].
I don't really get the difference in ACC between G1 and G2, the difference in difficulty does not seem that big.
Because many people thought it would be related to some advanced topic like convolution and left
For E, I did i = [0, n/2] and if ( s[i] == s[n-i-1] ) count++; Now, return ceil(count/2). What's wrong with this?
try aaabcdefgaaa
really nice solution for G2!!
Hi, for G2, isn't O(n*log(n)*cbrt(A)) around 1e9? I tried the method and it indeed passes, which is really weird to me. Another weird thing is I used std::map in G1 initially and it TLEed (complexity is O(nlogn sqrt(A)), so should be same, as in G1 A=1e6 and in G2 A=1e9), so I guess the test cases are built such that O(n*log(n)*1000) passes for G2 (and only in G2)?
deleted
True.
Can someone explain why my solution to G1 is timing out? https://codeforces.net/contest/1822/submission/203347556
Basically I check all possibilities for the middle element. For each distinct element a, I go through all factors x of a and add up (# of a/x)*(# of a)*(# of xa). This should take O(120n) since each number in [1, 10^6] has <=120 factors, which should pass; however, it TLEs. Can someone help? Thank you.
This code block will be executed for each testcase, and there can be 10^4 testcases, so the code will run for 10^10 times.
Problem statement C was very hard to understand. At least for me.
I just solved it by guessing the pattern in the samples.
check out YocyCraft solution above in comments. He's explained it pretty well.
Could someone explain problem D?
There is to cases : n is even or odd, if it is odd the answer will -1, odd numbers will give two same numbers in mod operation so there is no solution, the corner case of odd numbers is 1 because it has legnth 1, the second case : if it is even the answer will begin with n then n-1, and flip between odd and even numbers from 2 and n-3, this is a valid solution like test case 4.
For the case that n is even, I can't figure out the way to assign the permutation with $$$n, n - 1, 2, n - 3, 4,...$$$ like that. Is there any trick to come up with it?
You want to sum up in a way that you go through all remainders $$$mod\, n$$$ exactly once. You have to start with $$$n$$$, otherwise you would not ever have a chance to use $$$n$$$ again, since $$$ (x+n)\, mod\,n = x\, mod\, n $$$. One way I saw to do it was to having two cursors for the remainders $$$l = 0, r = n - 1$$$ and iterating with $$$l$$$ frontwards and $$$r$$$ backwards. For example:$$$ n = 4 $$$, you want to have these remainders $$$\begin{bmatrix} 0,3,1,2\end{bmatrix}$$$, and the construction would be $$$\begin{bmatrix} 4,3,2,1\end{bmatrix}$$$. I'm not exactly sure why this construction works yet, just felt right to me. I'll try to update when I figure it out. my submission
I want to ask why the problem G1 my code's time complexity is (2e5*ln1e6) , but I get several times Time Limit Exceed? Can someone help？Thank you very much! This is my code:
If $$$b = [1000000, 1, 1, ..., 1]$$$, then $$$mx = 1000000$$$ and $$$mx / b[i] = mx$$$ for every $$$b[i] == 1$$$ which means that the inner for loop iterates from 2 to $$$mx$$$ on every iteration. Your complexity is $$$O(n * mx)$$$.
But I have the code' if (c[b[i]]!=-1) continue' to skip the repeat b[i],so every b[i]==1 just can operate one time.
Oh, I missed that line. But the complexity of your code is still at least $$$O(test cases * mx)$$$ though. Consider $$$1e4$$$ test cases of the array $$$b = [1000000, 1]$$$. Your inner for loop would make $$$mx$$$ iterations every time since you are resetting $$$c$$$ in every test case.
hacked :(
Excpected rating of 1822E - Making Anti-Palindromes is 1615, according to CLIST:
During the last 20 Div.3 contests, the rating of Div.3 E has always been in range [1400, 2000] according to CFTracker
During the last 20 Div.2 contests, the rating of Div.2 D has always been in range [1600, 2500] according to CFTracker
Wonderful div3 round,i learned new things this round.Thanks to problemsetters!
Any hint or idea for problem D ?
for i > 1; let a[i] = n; thus, b[i] = (b[i — 1] + n) % n = b[i — 1]; not possible since b is permutation; thus a[1] = n and b[1] = 0;
if n is odd : b[n] = (n*(n + 1)/2) % n; n + 1 is even; b[n] % n = 0 but b[1] = 0; thus no "-1" if n is even : b[i] — b[i — 1] must be unique; here i think you need to use pen paper to observe or just check the last sample case;
Why does G1 has to have so tight constraints I submitted it in python and got that question hacked. Please make it fair for all languages. Atleast try to make in python and c++ many beginners use python.
Actually it's not about python speed. In fact, pypy3 is fast enough to pass this problem. it is because someone generate a special test case to make python code that use dictionary to be TLE.
You can sort the array before putting them into the dictionary, and it will be accepted. Here is your accepted code: 203372619
A rated round should not have had problem F. Its a blatant copy of the general standard problem of finding max distance of a node from each node of a tree. https://cses.fi/problemset/task/1132.
I highly doubt setters were unaware of this since its literally in cses. Please unrate the round in the future before pulling such schenanigans. Contest is not meant to copypaste submission and modify 2- 3 lines to get AC. (I say this as someone who got the problem in under 4 mins due to this exact reason)
is not wanting cses problems to appear in cf rounds bad? :(
It is not a good problem, but there is no reason why the round should be unrated, espically since div. 3 rounds are supposed to be educational anyways. The problem is also not a copy of the cses problem and no evidence suggests that.
I didn't say the round should be unrated, rather such a problem shouldnt ever show on rated rounds, a minute difference being that i dont call for this round to be unrated, just any future ones trying to use cses problems.
As for the copying part, cses problem : find max distance from each node, div3 problem : find max distance from each node, call it dist, and output max(k * dist — c * depth) instead
Adding one extra step makes it non copied? (I do not joke when i say i only had to change 3 lines in my cses code aside from clearing global arrays due to this being multitest)
Educational rounds can manage without having problems directly from cses, im sure div3 can too.
This problem had same thing https://codeforces.net/contest/1805/problem/D.
My solution which uses the cses questions code https://codeforces.net/contest/1805/submission/200411445.
that problem required many other observations, div3F was more of a direct copy.
I dont agree actually, yes that problem had a subpart which was basically that cses problem, but reducing it to that was a step, and not a small one to me.
This problem is just directly asking for the ezact same thing as the cses one.
It is quite standard, but not a direct copy, so there should be no reason to be unrated
Could please someone explain why this submission of G2 TLE's
I keep everything in map, which takes $$$log(n)$$$ operations to access value. So it would take $$$F = log(2 * 10^5) < 18$$$ operations in the worst case.
Our triple is $$$a, a * b, a * b * b$$$
$$$a * b ^ 2 <= 10^9$$$
$$$b <= 31623 / \sqrt{a}$$$
So, for each $$$a$$$ we have no more than $$$31623 / \sqrt{a}$$$ options for $$$b$$$
For each distinct $$$a[i]$$$ in the array I visit all the possible $$$b$$$.
Array of elements $$$a[i]$$$ has at most $$$2 * 10 ^ 5$$$ elements. And the smaller the $$$a$$$ the bigger is $$$31623 / \sqrt{a}$$$.
It means at worst it would take
$$$\sum_{i=1}^{2 * 10 ^ 5} 31623 / \sqrt{i}$$$
visits of pairs $$$a, b$$$
For each $$$b$$$ I make $$$2 * F$$$ operations to check whether we have $$$a * b$$$ and $$$a * b * b$$$. And $$$F$$$ operations for each $$$a$$$.
In total
$$$F * 2 * 10 ^ 5 + 2 * F * \sum_{i=1}^{2 * 10 ^ 5} 31623 / \sqrt{i}$$$
$$$ \le F * 2 * 10 ^ 5 + 2 * F * 31623 * \int_{1}^{2 * 10 ^ 5} 1 / \sqrt{x} \,dx$$$
$$$ = F * 2 * 10 ^ 5 + 2 * F * 31623 * 2 * \sqrt{x}|^{2 * 10 ^ 5}_{1} $$$
$$$\le 18 * 2 * 10 ^ 5 + 2 * 18 * 31623 * 2 * 448$$$
$$$ = 36 * 10 ^ 5 + 1 020 031 488$$$
$$$\le 2 * 10 ^ 9$$$
First of all, $$$2 \cdot 10^9$$$ operations may TLE regardless due to the high constant factor of std::map. The reason why your solution gets TLE is due to multitest cases, which your calculation does not take into account. The test that your code failed on is just $$$10000$$$ copies of this test:
20
1000000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Thank you, I think I get it now
My current rating is 401. I've submitted solution of 5 problems of Codeforces Round #867 (Div.3), and all submissions was accepted. a This is my 2nd contest, but still my rating is not increased. Can anyone tell why?
It takes time for edu and div3 rounds. Atmost 2 days.
To be honest ,I still do not understand Problem C,but just by observing the test cases,I came out to the solution
check out YocyCraft solution above in comments. He's explained it pretty well.
Just add 4n (outer layer), Σ(n-1), Σ(n-2) and 1. You can observe the pattern of the chocolates. But yes, it was decipherable from the test cases.
On the other hand, I got problem-D AC by guessing the pattern from test cases. Odd numbers dont have solutions, and for even, start by placing n at the beginning, and n/2 in the middle, and on both sides of n/2, place the numbers n-1, n-2, n-3, etc, but in alternating order on left and right sides
Is there anyone like me who like Div 2 rounds more than the Div 3 ones?
Yeah, me. I was able to solve A-D in this contest, out of which A,B were very easy, and C,D were guesswork from testcases. I got good rating change, but didnt teach me anything.
On the other hand, altho I usually lose rating in Div 2 rounds, There's always something I learn, either during the contest or after it.
I'm new in contestant in Codeforces. I wanna clear that is Codeforces Round 867 (Div. 3) was a rated contest? I solved two problem(A & C) but my rating/rank is looks like that...
It is a rated contest. Since the rating change is not completed yet, it doesn't show the rank. It will be updated as soon as the rating change is completed.
This is the first time ever I solve a div3 F instantly. I can't believe that there was a time when I struggle to solve div3 E. It feels pretty amazing
no way,i think e is harder than f and g1 XD
no way,i think d is harder than e and g1 XD
a was the toughest
Hello friends, I have uploaded the video editorial of this contest from A to F. Editorial. If want, You can watch it!!!
I feel like problem C and D are just "guess correct solution" problems / see pattern. Is this kind of problems okey for you guys?
Hello! I'm kinda new here so please don't be soo critical T_T for the first problem this works fine on my codeblocks but for some reason it gives different outputs when submitted https://codeforces.net/contest/1822/submission/203327103
and what is more confusing is that the output change when I change the variables type from int to ll Can someone please help me T_T
This line -
for(int i=0;i<n;i++) { cin>>b[n]; }should be-for(int i=0;i<n;i++) { cin>>b[i]; }I don't know why i am unrated even though it's division 3 and I'm a newbie who participated first contest in Codeforces. can someone explain why for me?
It's not unrated for you. You are just not a trusted participant yet. You need to participate in atleast 5 contests to be a trusted participant. The round will still be rated for you, it's just that you will not be in the official standings for the contest.
Is the round unrated? I am below 1600 and have participated in a lot of CF contests, still it is unrated for me, anyone know why?
Can someone explain why my code got accepted in the contest, now after system testing it's showing TLE there weren't any pretests as far as I remember.
New test cases created/generated by participants during the hacking phase are added to the original set of test cases. During system testing, the solutions are rejudged with this new set of test cases. Your code might be failing on the new test cases.
after the contest ends hacks and more test cases are added to the original test cases
Why I did not get contest rating points despite solving 3 problems?
rating is not out yet
when
Updated
when will updated??
Pretty bad systests for G2 O(sqrt(a[i])*n*log(n)) with some small constant optimisations is AC
[upd] all hash tables(with custom hash also) instead of map give TL, which is quite funny
Yeah the tests are really weird.
Edit: Wait you mean sqrt instead of qbrt? That would be roughly 1e11 right? How on earth can this pass.
Yes, that is the point. Constant optimizations)
Has anyone solved Problem F using Rerooting?
Yes you can see my submission
203331728
Can someone hack these solutions? solution1 solution2
They both failed on this test case:
UPD:Thank's pavlekn for hacking them
This is my code for problem G2, it got Accepted. But if I use a
std::vectorto traversal all numbers,itget TLE 203456289. Why
std::vectoris so slow andstd::mapis efficient?and if I don't use
std::map.count(), it will get TLE too[submission:203459839]. Why?Because you use
std::unordered_mapin your solution which can be hacked without using custom hash function post about thisThanks a lot:)
For problem F, I only considered one endpoint of the diameter and didn't consider the other one, but it still passed tests. Why does that work? The endpoint I considered was the furthest node from 1.
If you are already on the diameter then the cost to get to the closer end will be <= to the cost to get to the furthest end (and it's obviously optimal to stay on the diameter).
If you aren't on the diameter every move will change the distance to both ends of the diameter by the same amount until you reach the diameter (at which point you move to the closer end).
I think i have used ideone in public mode by mistake and I was absolutely unaware that someone can see my solution there because of which my solution has been copied by somebody/ or it can be an absolute coincidence! Sorry for this but I will take care of it from next time while using ideone. Please have a look into this . MikeMirzayanov . Question F of the recent div3 round caused this issue :( . Please revert back my ratings . 203313670 Submission ID for the question . Please revert back my ratings
System please do look into the matter too :(
So my solutions for B and C have been reported as cheating, since they are too similar to others (from https://codeforces.net/profile/KudoConan) B: Mine: https://codeforces.net/contest/1822/submission/203276161 His: https://codeforces.net/contest/1822/submission/203330555 C: Mine: https://codeforces.net/contest/1822/submission/203281804 His: https://codeforces.net/contest/1822/submission/203329843
As you can see they are almost excactly the same. I don't know what to do now, since i have not shared my code with anyone and as you can see my submissions have been an hour before his. Since the solution are very "easy" and there isn't much room for different approaches in Python it feels like there should be a lot of similar solutions for these problems.
Well I guess the only evidence I have is that his A is different from mine and that I also solved D and E, still I am not sure what to do, if there is anything I can provide please let me know.