Hello everyone,
FBI and JuicyGrape are very exited to invite you to Codeforces Round 943 (Div. 3)! It starts on May/02/2024 17:45 (Moscow time).
The format of the event will be like any Div. 3 rounds:
- 6-8 tasks;
- ICPC rules with a penalty of 10 minutes for an incorrect submission;
- 12-hour phase of open hacks after the end of the round (hacks do not give additional points);
- after the end of the open hacking phase, all solutions will be tested on the updated set of tests.
Only trusted participants of the third division will be included in the official standings table. This is a forced 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 (or you are a newcomer/unrated), then the round will be rated for you.
We would like to thank:
- MikeMirzayanov for creating Codeforces and Polygon;
- Vladosiya for coordinating the round;
- feeder1, Umanity, barbie, Ryougi-Shiki, MAKMED1337, EyadBT, purinliang, waipoli, ksu_, _Dragon_, royayaha, OAleksa, AlphaMale06, cherryk, Acanikolic73, Sheikh_Sady for testing the round and making it better.
Good luck and have fun!
UPD: Editorial.
I hope everyone have a great time with this Div.3!!!
And I wish my positive delta. I'm 1599 now...
Interesting. 0 rating change last round, and since rating update delayed,
I think this div3 is gonna be a clash of experts and ex-experts.
Update : I don't know why heavy downvote. I noticed codeforces converted all experts, even those who registered as specialist/pupil to unofficial participation
But they updated the ratings?
delayed != didn't happen. But people who became expert last contest, had a chance to register for div3 for a good amount of time before ratings were updated
Update : Thanks to admins. I noticed codeforces converted all experts, even those who registered as specialist/pupil to unofficial participation
wouldn't they be considered out of the competition still?
That's my point. Since, rating delayed so they had been specialist and could click register, so they registered as specialist or pupil and now are experts and hence a clash of experts and ex-experts xD
Update : I don't know why heavy downvote. I noticed codeforces converted all experts, even those who registered as specialist/pupil to unofficial participation
All luck for you.
As a tester, the problems are cool!
As a tester, I agree.
As a contribution farmer, I disagree
I saw that you have one piece pfp and got curious. Did you name yourself after wapol ?
no, the story with waipoli is more strange than you think)
Did anybody say one piece :)
Yes)
yess!
Hi bro :)
Hi)
As a tester, I want some contribution!
As a participant I also want some.
Good luck to everyone! Enjoy thi Div3 :) Hope to have a good time in this round.
I wish you all good rankings!
I hope I can solve ABCDE after having exam in the morning. Good luck to everyone!
Good luck in your exam and in the round!
Good luck with the exam! (Actually I
ll also have one in the morning so Im supposed to be studying)I overslept.
so you skipped the exam or what?
Basically yeah.... I think I'll be able to rewrite it.
My planned post contest discussion stream
It is a sarcastic comment!!!
As a tester, I can already discuss the problems. So you can start your stream rn and don't waste any time.
As a tester I don’t know what to say.
Wish you Rating+=♾️
I'm out of competition
I forgot the name of this meme what’s the name??
Time to reclaim my title as specialist.
Summon Mahoraga and get him to adapt to all the problems.
Oh I wish. But first he's gonna have to adapt to my massive skill issue , and that will kill him like a 200% hollow purple.
Nah You'd win
Always bet on ABC.
you'll need more than only ABC in div 3 to reach specialist.
Hope to the best div3 ever
I hope to be a good div3. <3 But,I wonder how can i solve at least 3 problems? Consider that I practise continuously about div3.
The problems from Div.3 rounds and Educational rounds are classical (= common) and useful. It means that you can always easily utilize the skills and techniques you learned from these rounds, and there are numerous problems are just derived by such classical problems. In contrast, there are creative and mathematics-required problems in those non-educational rounds and Div.1 rounds from time to time, so I believe that it is hard to earn higher rating since 2100.
So what you need to do is just to try your best to learn more techiniques (including how to analyse the problem and how to bug-free code). The amount of those traditional techiniques is limited, you can eventually complete that in 30 days if you try to solve the first 4-5 problems in one Div.3 Round everyday.
Thanks for your usefull feedback Im so grateful for ur comment <3 <3 . I actually do that I'm trying everyday to solve atleast 2-3 problems div3 but I think that the progress is very slow and I see my friends are climbing so fast and that makes me disappointed. I have a question : "Is there any yt channel that give tips how to be faster and how to be better at greedy problems . I consider your tip to solve 4 problems every day <33
To be honest, I learned how to solve greedy problems by reading some textbooks written in Chinese. Maybe I can give you some keywords to help you to search for those materials.
Observe which is constant: after doing some operation, some numbers/relationships remain unchanged. For example, to minimize the amount of pair (i, j) that satisfies certain condition (e.g. i < j and a_i > a_j). You can switch the adjacent elements, and only the relationship between the two elements will change. It means that you can do the swap operation to optimize each pair of adjacent elements to reach the goal. This thinking method may also be called as "Swapping adjacent"?
Do it first, and regret in the future: You can do the operation first, and record the operations you have done in some data structures (e.g. a heap/priority_queue), when you meet a better choice to do a operation, you just delete the worst operation recorded by the data structures (e.g. priority_queue.top()) and replace the old operation with the new and better one.
Try to predict whether can make a greed operation: Just like a lot of binary-search-liked methods (e.g. to find the k-th element in a data structure) which are common-used in data structures like SegmentTree or BBST. You can also learn the skill in 01-Trie (to greed from the most significant bit, check that whether can take a 0 or an 1 in the next, until the lowest bit)
The aboving are the common idea in greedy solutions. Besides you can also just improve your mathematical skills and instinct.
Looks like its time for another Speedforces round.
During our previous round you solved 3 tasks out of 8, lol.
Hehe, I was only newbie back then . Hope to do better this time.
Good luck!
Thank you sir!
This didn't age well.
hoping to return back the blue handle
Does anyone have guesses what kind of round it would be? I mean what kind of problem is contained in the problem set?
problems will be all solvable in a programming language. I can bet on that if you want.
Yeah there is always a solution that will be accepted. This if there won't be a problem that is mission impossible :)
It is a sarcasm!!!
As a tester, I would say that there will 10 output only tasks, and it will be a heuristic contest.
What's output only tasks?
Sure, I think that my guesses are correct, but we`ll see.
You can never be sure for 100%
Yeah,like that time when I got ill because we couldn't choose a place where to eat,lol.
Both Setters: Expert, Both Max: Candidate Master, Both From: Ukraine, Both Authored: 891 Div-3, All Setters(891): Expert, Rated till: !Expert;
Both setters: UOI medalists. One of the setters: codechef 2198. Both setters: UJGOI problemsetters.
Congratulations for the medals! I really liked UOI 2023 problems.
Hope I can reach 1550
Hope to solve 5 problems
Good luck!
last round organized by SashaT9 i turned from gray to green I wish I can turn from cyan to blue today !
Hoping for a colour change ( to green)
Good luck
ICPC rules with a penalty of 10 minutes for an incorrect submission;
what does this mean? Do i get time deducted if i submit an incorrect solution? and after i solve it do i get my minutes back.
Sorry im not really familiar on how the contests work here
So basically your final rank is based on comparing the number of problems you solved with everyone else. Now among the people who've solved the same number of problems as you, the ties are broken based on the sum of the submission times for each of your problems. Now if you submit say three incorrect solutions, but later submit the correct one for a particular problem then 10 * 3 mins are added to your total submission time for that problem.
Hope this clears things!
Do not be afraid, but be careful.
Hopefully this competition will be able to break through
Hope to solve A-E.
I hope to reach at least 1450 in the contest
one refresh costed me 10 mins ._.
delayforces...
Ten-minute delay in start time?
Why are u using the same avatar as me? ~
Why the time was delayed?
could be some server issues due to a lot of requests!
weak samples of B, literally passed it while misunderstanding statement of problem
not a chance. your solution was correct.
Hope there will be plagiarism checking for this round
Unexpectedly solved A — F. Still don't know how i did, but i did. I am very proud of myself.
E needs pre knowledge or it can be solved even if you know nothing about Manhattan distance ?
It is just observational problem. I spent quite a time to find the arrangment that will always work.
Same here. Had to visualize potential arrangements for n up to 6 to spot a pattern.
I saw that [1, 1] [1, 3] [1, 4] ... [1, n-1] [2, 1] [n, n] was an answer, and I have no idea what Manhattan distance is.
Maybe you can do better in the next time since that you already know what is Manhattan distance now.
what's testcase 2 for problem F.
spent almost an hour debugging it, still not able to find the mistake.
look at my code bro — 259236083
got it bro. forgot to initialize.
Thanks for the contest! Problems were quite good!
After solving D for like 20 minutes, I realized that I was solving the wrong problem since I did not notice that the player may also stay in the current position and not move to
p[i].last minute i couldn't submit F, i am tilt :(
I submitted problem F on the last second. The server were very laggy
E is very nice
Yes, I agree with you. The task is very interesting. I really like this kind of task. Unfortunately, I was unable to solve this problem during the competition, if you solve this problem, can you explain your solution?
Thanks!
Sure broski. What I first noticed is that we can make the set contain values from 1 to n — 1 just by putting all of the dots on the first row. For n = 4 it'd look like this:
oooo
. . . .
. . . .
. . . .
Then, what would happen if, instead of putting the final dot on the first row, we put it on the last row?
ooo .
. . . .
. . . .
. . . o
Then our set will contain {1, 2, 4, 5, 6}. In general, if we do this for any n > 3, our set will contain all values from 1 to 2n — 2 except for n — 1 (of course we can't have a Manhattan distance beyond 2n — 2). How can we get it to contain n — 1?
Well let's remove the dot at (1, n — 1) for now and see what changes:
oo . .
. . . .
. . . .
. . . o
Now the set does not contain the distances of n, n — 1, and n — 2.
Place it at (n — 1, 1):
oo . .
. . . .
o . . .
. . . o
Now our set will have the distances of n — 2, n — 1, and n. That is a construction for n > 3. For n <= 3, the set can't contain {1, 2n — 2} because there aren't enough pairs. You can just hard-code these cases.
I spent an hour while coding wrong codes on D :(
seriously code once Think twice
LOL. Why E was not an A problem? I read the task at the end of contest.
How to do it?
Just fill the diagonal. You'll get all possible pairs with even distances. Just shift one bubble by one and you get all odd distances.
There are solutions and there are beautiful solutions.
Fill $$$(1, 1)$$$ and $$$(N, N)$$$. Then fill $$$(1, i)$$$ & $$$(N, i)$$$ $$$\forall$$$ $$$i$$$ $$$\in$$$ $$$[2, N-1]$$$.
As a tester I reckon problem E is 1700-1900, because my solution to E is so complex. I believe that a 1700 problem can be placed on problem E. (Well, to be honest problem E is harder than G2 for me)
I used the Manhattan distance list to construct:
n = 1, [], [0, 0] // n = 1, Manhattan list is [] (empty), can represent all integers in range [0, 0] n = 2, [1], [0, 1] n = 3, [1, 2], [0, 3] n = 4, [1, 3, 2], [0, 6] n = 5, [1, 3, 2, 2], [0, 8] n = 6, [1, 3, 2, 2, 2], [0, 10]
I discovered this solution using 40 minutes, so I give it an 1700-1900 estimation. Why I used so much time because that I tried to represent the range [0, 2*n-2] by using the classical list [1, 2, 4, 8, 16, ...]. So I was far away from the right solution at the beginning.
The constructive problems require a really high-level math instinct. Maybe you are talented. I believe that some skillful competitors will also struggle with solving it.
Ye, I very much like constructive and pattern problems :)
P.S. A has also very simple solution, so I was wrong about difficulty comparison.
BTW E was nice problem.
I wish I could downvote this contest multiple times. Pathetic problem statement for E
welp, did you solve it? did you try to at least draw the matrices?)
I couldn't solve it but I think statement was clear
any hints for E?
Think about when you can have a set with all values from 1 to 2n — 2. When can you construct this? Is there a special case where you can't construct this?
The maximum distinct distances will always be <= min(n(n-1)/2,2n-2) since the possible distances are 1,2,...., 2n-2. So, for n>=4 its enough to find a construction such that |H|= 2n-2. Select (1,1) and (n,n) first and try to find this construction.
makes sense so I was thinking in the right direction after all. But wouldn't 0 also be a possible distance? so possible distance would be from 0 to 2n-2
Yup,doesnt really matter though
May be its just me but the reloading of this site is too slow, I had 2 minutes and I wanted to submit E, but couldn't as it got stuck on reloading page. Please do the need full please.
Anyone did G1 with string hashing??
A good try, mister hash-hacker.
Got it right just the index to string was getting out of the length of string.
No need for hashing, just one line in rust:
Actually thats pretty impressive
btw you can solve G2 by caching binsearch results
I wanted to, but wasted 1.5 hours debugging F and still messed up somewhere, barely got G1 at the last seconds.
In case anyone interested: 259263295
This did work for me in C++, but not in python. Always get TLE in python.
looks nice!
I did)))) but random hashes.
yes
upd: Hacked
Patta_gobhi_ Check this submission 259262278 (Hashing + Binary Search)
Why am I so bad at construction problems. I always get stuck at problems like E. Tips? Anyone??
i cant prove it, but
n = 1 => 1 1
n = 2 => 1 1, 1 2
n >= 3 => previous + (n, n)
nice pfp with kings gambit)
n = 3 => 1 1, 1 2, 3 1
n >= 4 => previous + (n, n)
Proof:
The goal is to get every possible path distance. This is possible for all n>3. All the path distances are the range [0:2n-2] (shortest: they are at the same position, longest: two opposite corners).
Starting with
(1,1)and(1,2)gets you the first 2 distances:d=0andd=1.Say we have solved for n=3. (It is given that a solution is
(1,1),(1,2),(3,3)Now, everytime n goes up by 1, we need to find two more distances, but with only one new position.Since we already have
(1,1)and(1,2), we simply need to find a position that has manhattan distance2n-3and2n-2from these two points, at the same time.This new position is the bottom right corner, a.k.a.
(n,n): manhattan distance from(1,1)to(n,n)is2n-2manhattan distance from(1,2)to(n,n)is2n-3It is clear that we can simply repeat this process
n-2times, after having placed the original positions(1,1)and(1,2).Hope this helps :)
Solve F.
practical advice
I totally agree with you! I got stuck at problem E when I tested it. And I even spend 40 minutes to solve it! Why I spent too much time on solving it, it was because that there is another classical problem: To express all the numbers in range [0, n], we can always choose [1, 2, 4, 8, ..., 2^(k-1)]. So I just tried this "solution" first. Well, I failed.
After a while, I noticed that I don't need to minimize the elements I use. What I mean is that by using [1, 2, 4, 8, ..., 2^(k-1)] there is just O(log(n)) elements. But for this problem, we can use O(n) elements. Then I notice that I can just contrust the solution for n = 7 by adding one more elements in the solution for n = 6.
That is the definite breakthrough, just add a new element in (n, n) is ok. This problem gave me the new idea that is not to solve the problem using the O(log(n)) thinking at first, just try to discover how to construct a new solution by the previous n. I think in constructive problem we should try to utilize different ways to analyse the same problem, and explore the protential solution by reading other users' code.
How does the 10minutes penalty work, does it only give penalty for problems that passed the first testcase cause I got a few wrong submissions but didnt get any penalty.
if you failed on tc 1 then it will not give penalty . but thats bad that you are not checking your code locally.
No penalty for wrong answer of testcase 1.
Why in problem e it was counting every cell with itself?
in Problem F, any idea why this code is giving idleness limit exceeded?
https://mirror.codeforces.com/contest/1968/submission/259209395
P.S. IDLENESS LIMIT EXCEEDED, NOT TIME LIMIT EXCEEDED
Same happening with me... Time complexity is O(n*(4logn)) That is acceptable but still I'm getting TLE
I have used segment tree to find the XOR of ranges
my Submission Link
i had the same problem its probably because of using a map and copying a long vector which is O(n) so when there are a lot of similar prefix xors (like in test 17 where there is a lot of 1s and 0s) each of those vectors is gonna be long and cost a lot my solution is using compression to store the vectors in an array of vectors instead so there is no need for copying them for each query but didn't have enough time to implement it, might try it later
Got your point bro...copying a vector will take O(n) time in worst case.. So overall complexity will become O(n*n) in the query processing loop
Taking it by reference will work !
Thanks for pointing this out
sarthakswarnkar, There is a version of your code that passes code.
FBI won't give me positive delta when he saw my pfp :sob:
nice pfp. but i prefer Makise)
Hints For F , (when we have odd k ?(for even xor its 0))
Let xor of block = Y, then pref[r] ^ pref[l-1] = Y. Look it inside l..r and check that after it comes even number of blocks.
what comes even times? How will we know its good if y!=0?
Ended up with the correct solution soon after the round ended.
Take cumulative XORs at indices right before (p) and right after (q) the subarray. If equal, it can be split into 2 parts. If not, look for q and then p in between (sequence p...q...p...q). If found, it can be split into 3 parts.
Now, iterating through the subarray to find the q and p in the middle is worst case (edit: O(n) per query, O(nq) in total, where q = # of queries) and ended up TLE'ing. Had to use a dictionary (cumulative XOR value -> list of indices) and BS through the lists. The time it took to get the index calculation right was why I couldn't submit on time.
Didn't read E until the last minute but
between any pair of cellsis confusing when reading the notes, probably need something likebetween any pair of cells (including each cell with itself)Even if we exclude pair containing a cell with itself, the answer stays the same. |H| will just be reduced by 1 for every n.
Yeah but like if it doesn't even matter then I guess it's best to just not include each cell with itself in the notes lol.
"...confusing when reading the notes..." Well, I don't recommend what I'm about to say, but maybe don't read the notes when the problem statement is pretty clear and has almost no room for ambiguity? And even if you do and discover some extremely weird ambiguity (which happened in this case, I agree with you), maybe gather yourself and cancel out that thought quickly, like "well it doesn't matter cause if I generate any answer it will have the distance 0 anyways so let's ignore this bullsh* and solve normally"?
Also, the notes section of construction problems usually helps only to find any patterns. I "read" the notes, but only saw the figures and tried to understand what might a good strategy be. Really didn't look at the $$$\mathcal{H}$$$ set in the notes until I saw this comment.
I mean I didn't complain because I didn't solve it
I only mentioned it in this comment, because well it literally is a comment for the problem statement itself that it shouldn't be confusing
Right, agreed. It shouldn't have been calculated or worded like this.
Problem C. Assembly via Remainders ***** this is my solution, it is correct i guess but the test case says failed . dunno why :
include
using namespace std;
void solve() { int n; cin >> n; int arr1[n-1]; for (int i = 0; i < n — 1; i++) { cin >> arr1[i]; }
int arr2[n]; arr2[0] = arr1[0] + 1; for (int i = 0; i < n - 1; i++) { arr2[i + 1] = arr2[i] + arr1[i]; } for (int i = 0; i < n; i++) { cout << arr2[i] << " "; } cout << endl;}
int main() { int t; cin >> t; while (t--) { solve(); } return 0; }
example: 2 499 21
you may try to fix your code by add another 505(for example), to make sure your
arr2[i+1]is greater thanarr[i+1]Why is my G1 fails on test case 2
link: https://mirror.codeforces.com/contest/1968/submission/259244119
s = "aaaaaabaaa"
s1 = "aaaaabaaa"
using your algorithm, s1 didn't exist as substring of s
got it thanks
E is awesome, costing most of my time on it but still, stuck:( Nice Round indeed, but sad negative delta for me:((
E Good Job. I live this.
any hint for F??
if subarray xor is even it is always possible
for odd, if answer exists, then it is always possible to break subarray into exactly 3 segments , each one of them having the same xor as whole subarray
You only need to split the subarray into either 2 or 3 subsegments, since you can compress any way of splitting into 4, 5, ... into just these two cases.
If the subarray was to be split into 2, there must exist l<=i<r so that xor[l..i]==xor[i+1..r]. Doing some algebra magic, we get that xor[1..l-1]=xor[i..r]. So we just need to check the equivalence of these two prefix xors (O(1)), without any need for iterating!
If the subarray was to be split into 3, similarly, there must exist l<=i<j<r so that xor[l..i]==xor[i+1..j]==xor[j+1..r]. Using a bit of rearranging, we get xor[1..l-1]==xor[1..j] and xor[1..i]==xor[1..r]. We can maintain a map/unordered_map of sets to keep track of the indexes where each value appears and greedily choose i and j so that the two conditions above hold in O(log(n)) time.
Wow I was able to figure out we only need 2 / 3 splits but went nowhere from that. I am so stupid..
same couldn't figure out afterwards
wasted 10 mins in D thinking that each player k/2 turns
could anyone please tell me a counter test case to my solution on G1, i could not find one by stress testing as well
https://mirror.codeforces.com/contest/1968/submission/259246021
unrelated but by selecting all code and pressing shift+tab you can delete the spaces at the start of the lines
This was my first contest. I was able to solve only 2 questions. I am not running after rating but can someone tell me what rating will I get? I am really excited about it
+300 something
When will the rating get updated?
Got updated. Check it out
I think approximately 300-400
you can download codeforces predictor on google — it will show you your rating change
Very nice contest with very nice problems :) Thanks a lot for the round FBI JuicyGrape and all testers!
Weak tests again....
259139777
$$$N^3$$$ for $$$N = 1000$$$ works well if it has a small constant. Your solution doesn't have a big constant. Worst case is test t = 1000 x = 1000, your solution works well there
unbelievable. so corrupt constraints. and for what? to give c++ coders another advantage. in div 3 round...
Wow.... Weak tests.... For the easiest problem of the round.... For the problem where there are at most 1000 different possible tests... Wow....
Sure you guys did your best. But why it is 1000 but not 100 or not 10000 we will never know...
because x values can be only up to 1000 (actually because x is only in range [2,1000] there are not 1000 but 999 possible tests)
What is the intended solution for G2? I used string hashing and set to solve it in worst case O(N * (log N)^2), but average case would be better than this.
Do you have any proof for the upper bound when using hash? I did with zfunc worst case O(N* (logN)^2)
Yes I have proven it. My algorithm is that for every length of prefix I have a set called candidate that stores the starting indices which have the same substring as the prefix for until the previous length.
Now for the current length I can find the count in N log N/ len. So the complexity will be N log(N) ^ 2.
You can check this submission: 259254423
Ya got it, so you are removing the candidates which don't have prefix of length l same so they wont be checked ever again, and in the worst case if no candidate are removed then its the same as nlog^2n when all char are equal. Great!
Yes perfect! You described it better than I could :)
problem E be like WA on pretest 1 🤡
For Problem G1 I wrote this code
Tried with many custom cases still couldn't figure what's wrong here. Can anyone please look and point out the mistake here.
Here i am just trying to find number of partitions where all partitions contains a string "t" (as declared in code) as prefix and check whether number of partitons is greater or equal to the asked partitions defined in question.
same i also applied the same logic but wrong answer on 2
You can use KMP to check the condition instead of pointers.. Refer here:
https://cp-algorithms.com/string/prefix-function.html#:~:text=%C2%B6-,Search%20for%20a%20substring%20in%20a%20string.%20The%20Knuth%2DMorris%2DPratt%20algorithm,-%C2%B6
Code:
Can you please tell a mistake here. I have been trying to find the counter case but not able to find one. This is eating me up now. Still couldn't figure out what's wrong here.
Here is my submission: https://mirror.codeforces.com/contest/1968/submission/259250481
Update: Found one TC here
Here answer is 4 but above code will give 3.
Thank you for tasty problems. I enjoyed.
today's contest as expected as this was div3 so solutions to problem A,B,C,D all soon were available by 21:00 , i tried very much in finding the cheated ones which many tried modifying: the cheated solution readily available for problem D from 21:00(UTC+5.5) https://ibb.co/Rph74Qd https://ibb.co/f2rx42K . please ban these cheaters : i already mention about some of them before. 259222711 259219713 259230136 259217156 259228528 259227463 259228698 in fact some of them also tried the later problem solutions from some sources. like for problem F i will share what i find later . MikeMirzayanov Vladosiya
Video Editorials for Questions C, D, E
C : https://www.youtube.com/watch?v=oEx5rR4wAKw
D : https://www.youtube.com/watch?v=XBUN4LwolEM
E : https://www.youtube.com/watch?v=DObsk_Rlhg8
language => Hindi
in problem G1, isn't your check function running in O(n^2). How is it passing the test cases
As a tester, I was only sending the correct solutions and not the wrong ones.
Shame
Got hacked :(
Superv Div3..it was exciting
please don't make problem like E again.
Why? Because it forces you to think in a different way?
Enjoy the problems, thanks! Wondering what is the other solution for G2 other than the memoization with binary search approach. I feel like it had a different intended solution.
G1 should be banished to the shadow realm. 99.99% of test cases can be solved with a binary search + interation. So, I coded that up expected a full solve. I got WA on TC2 number 384. Brvh. Then I figured out my mistake after 1 hour of stoopid grinding out bullcrap testcases. Then, the implementation of this edge case fix became harder thaan the actual problem itself. So, basically thsi problem is so easy to fall into a stupid trap and it will take hours of your life to get out of it. For those of you that do this contest as practice. GIVE UP ON G1 if you get WA2, not worth the effort to try to fix.
sorry for the rant. I am not saying that G1 was a bad problem per say but incredibly deceptive. DO NOT RECOMMEND IT.
For problem G1,
I use a binary serch for answer and brute force judging if there is so many substrings exist.I think my solution is O(nlogn),while it was hacked and turned to be TLE
My code is here.I'm really curious about why.259250187-
Oh,I find that my brute force can be n*n,so I'm hacked.
I'm confused. Was G2 simply bruteforce with extra steps...?
I'm not sure if my solution is hackable or not, and if not, was it under intended complexity? (it seems like $$$\mathcal{O}(n \log^2{n})$$$, but I'm not too certain).
It isn't brute force actually, the while loop runs for nlogn, it's the same pattern as n+n/2+n/3+..n/n, also the lower_bound call adds another factor of logn making it nlog^2n
Thanks for the complexity analysis, it makes sense.
For the brute force part, I meant for the whole problem, yet I think I mistakenly coined it. It's more like a provable greedy with lower_bound to speed up the probing :D
... I take part in only 4 rated contests, this is first contest where I solve more than 2 problems and this is without rating for me ..
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600 (or you are a newcomer/unrated), then the round will be rated for you.
It will be rated for you for sure
Nice...
when will this contest rating be updated..........any idea ?
After system testing ends.
Hello Vladosiya may you please check my previous comment in this blog post ? No cheaters were caught at all from the list i shared above from the system testing .I hope so in later future rating roll backs those will get punished.(because some of them are consistent in not getting detected by plagiarism checker)
very educational round! rk11 in official rank list ^_^
thx for very amazing contest. It was very cool!!!
The problemset was nice !
G2:
I repalced the Z_function with Double Hash, but it's TLE, Can someone explain?
259385157
It's seems O(n*sqrt(n)*log(n))
I LOVE DIV 3
Can anyone tell why simple binary search on the answer from 1 to n won't work ? Can anyone suggest any string which don't follow this. 265440846.
UPD : Got my mistake..