By awoo, history, 4 weeks ago, translation,

Hello Codeforces!

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 the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. 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 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

• +324

 » 4 weeks ago, # |   0 plz be good round plz be good round plz be good round
•  » » 4 weeks ago, # ^ |   +87 You can be sure that the problems will atleast be original.
•  » » » 4 weeks ago, # ^ |   -15 lmao yes
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +35 awoo is one of the great authors , problems will be original and creative surely(in my experience).
•  » » » 4 weeks ago, # ^ |   -13 Of course, I find educational round problems very good, however I feel like the round is a bit unbalanced
 » 4 weeks ago, # |   -15 Hoping for Creative round
 » 4 weeks ago, # | ← Rev. 2 →   +33 Educational Rounds always have original problems. I Love Educational Rounds Update: Although EDUs have repeated problems, still I Love Educational Rounds
•  » » 4 weeks ago, # ^ |   -10 I also like
•  » » 4 weeks ago, # ^ |   +26 bro... sorry
• »
»
»
4 weeks ago, # ^ |
+15

that's why the title includes the word

# "Educational"

•  » » » 4 weeks ago, # ^ |   0 what is this ?
 » 4 weeks ago, # |   -20 Finally a Rated,Original round. Hoping for a fair and creative round.
 » 4 weeks ago, # | ← Rev. 2 →   -19 +1
 » 4 weeks ago, # |   -13 Hope that that incident will be the last, forever.
 » 4 weeks ago, # |   -47 Are they all original? I don't want to waste two hours and then unrated:(
•  » » 4 weeks ago, # ^ |   +42 The most important thing isn't rating. It's the experience and the algorithms or approaches that matter. Only cheaters cheat themselves by their ratings, and I'm sure that you aren't that people:)And I believe theft will disappear in Codeforces, at least in a period of time.
•  » » » 4 weeks ago, # ^ |   +12 The least important thing is rating.
•  » » » 4 weeks ago, # ^ |   +2 The CodeForces match basically started at 22:35 in my country and I had to stay up late for the match, so I was looking forward to the rating:(.
•  » » » » 4 weeks ago, # ^ |   0 Then what about me?And I believe that one who sits into midnight is more likely to pay attention to their ability, not rating:)
•  » » » » » 4 weeks ago, # ^ |   0 I totally agree with you, but I think I can go to bed early and write the next day without rating, instead of staying up late and hurting myself
•  » » » » » » 4 weeks ago, # ^ |   0 That's up to you to decide:)
 » 4 weeks ago, # |   +12 Great way to start long weekend. Happy moon festival to all!
 » 4 weeks ago, # |   -25 I hope this won't be a waste of time.
•  » » 4 weeks ago, # ^ |   +1 Bro no contest is a waste of time lol
•  » » » 4 weeks ago, # ^ |   +4 right bro,we should pay more attention to which we learn from the round but not the rating.
 » 4 weeks ago, # |   -11 ⣿⣿⣿⣿⣿⣿⣿⢿⠟⠛⠿⠻⠿⠿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⣿⡿⠛⢙⣨⣥⣶⣶⣿⢿⣿⣿⣷⣦⣅⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⠟⢀⡴⠟⠋⢉⣀⣠⣤⣤⣤⣀⠉⠻⣿⣧⡈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⠀⠁⣠⣴⣾⣿⣿⣿⣿⣿⣿⣿⣷⠀⢻⣿⣇⠝⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⡀⣼⡿⠟⠀⠙⣛⣬⠱⣿⣿⣿⣿⣿⣿ ⣿⣿⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⠿⠋⢀⠄⠁⣠⣶⣾⣿⣿⣿⡆⣼⣿⣿⣿⣿⣿ ⣿⣿⠀⣀⠙⣛⣛⣻⠛⠋⣉⣢⣤⣾⠃⣰⡄⠸⣿⣿⣿⣿⣿⣷⠘⣿⣿⣿⣿⣿ ⣿⣿⣤⢹⣷⣶⣶⣶⣾⣿⣿⣿⣿⣿⡄⠸⣷⠀⢻⣿⣿⡿⠟⠛⠡⣿⣿⣿⣿⣿ ⣿⣿⣿⠄⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠄⠻⠇⢈⠁⠀⠀⠲⠠⠞⠿⣿⣿⣿⣿ ⣿⣿⣿⣷⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣶⣶⢤⠀⠀⢲⣿⣿⣿⣷⣤⡉⣻⣿⣿ ⣿⣿⣿⣿⣧⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣳⡀⢻⣿⣿⣿⣿⣷⠐⣿⣿ ⣿⣿⣿⣿⣿⣯⡈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⡇⡆⣿⣿⣿⣿⡟⣀⣿⣿ ⣿⣿⣿⣿⣿⣿⣷⡀⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⢃⡿⠿⠛⡋⣀⣾⣿⣿ ⣿⣿⣿⣿⣿⣿⣿⣷⣀⠹⣿⣿⣿⣿⣿⣿⣿⠿⠋⢁⣠⣿⡦⠐⠀⢈⡙⢿⣿⣿ ⣿⣿⣿⣿⣿⣿⣿⣿⠋⢀⣿⣿⣿⣿⠟⢃⣤⣤⡀⠻⣿⣇⣠⣴⡿⠄⠹⣧⡸⣿ ⣿⣿⣿⣿⣿⣿⡿⠃⢠⣾⣿⣿⡿⢋⣤⣿⣿⣿⣿⣄⠈⢿⡿⠋⣠⣤⣀⠈⣡⣿ ⣿⣿⣿⠅⣀⣈⠁⣰⣿⣿⡿⠋⣤⣾⣿⣿⣿⣿⣿⣿⣷⣵⣂⣽⣿⣿⣿⣿⣿⣿ ⣿⣿⣿⣄⠘⢿⣿⣿⠟⠋⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⣿⣿⣷⣤⣬⣅⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
 » 4 weeks ago, # | ← Rev. 2 →   +176 Comments in codeforces.. 2020Is it rated? 2022Is it original?
 » 4 weeks ago, # |   0 Good round or Bad Round? It's a problem.
 » 4 weeks ago, # |   0 gl everyone. I'm sure it's original unlike the previous one ;D
 » 4 weeks ago, # |   +10 Codeforces Language Picker -- chrome extension to fix codeforces language picker.
 » 4 weeks ago, # |   +24 Good Luck to all Coders ! Never give up the CodeForces ! ! !
 » 4 weeks ago, # |   +12 Hope to perform best in this contest
 » 4 weeks ago, # |   +35
•  » » 4 weeks ago, # ^ |   0 meh not so many upvotes i guess i lost my touch
 » 4 weeks ago, # |   +4 Very good round ❤❤ Thanks for all the authors and testers!(✿◠‿◠).
 » 4 weeks ago, # |   0 How to solve D?
•  » » 4 weeks ago, # ^ |   0 My approach was just recursive DP + memoization. Make a function for Alice's turn with arguments for left index and right index of the remaining string. Make a function for Bob's turn with arguments for left index and right index of the remaining string AND the latest character that Alice picked (important for tie-breaks). Check base cases (length 2 for Alice, length 1 for Bob), check if this case was encountered before (use two maps to store results, one for Alice, one for Bob), and if neither of those hold, then recursively check the two choices (pick first or pick last character). Obviously pick the winning choice if you can, but otherwise try to force a draw. My submission: 171425586 (sadly, it was uploading right when the timer hit 0, so it didn't count ;~;)
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Why did you use map? Are you trying to save memory?Is it better to use maps instead of arrays in these type of problems?
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   -14 The map is for memoization. If any recursive call revisits the same case, the map indicates what the answer is and it is immediately returned.Without this, each step would always invoke two recursive calls until it reaches the base case, which leads to a time complexity of $O(2^n)$ (you can imagine the recursive calls forming a binary tree, with base cases as leaves, and each level removing only one character from its parent). This would get time limit exceeded. However, there are only $O(n^2)$ substrings, so those $(2^n)$ nodes involve a crapton of repeated calls to the same substrings, which can be avoided by saving the answer in a map after you compute it the first time (instead of rebuilding the same subtree every single freaking time).This technique of "check if you solved the case before and only recurse if you didn't" is called memoization. There are other ways to achieve this, but I'm just personally comfortable with using a map for it, since it can adapt to whatever your case is described by (e.g., since Bob's case involves both Alice's character and the substring endpoints, the corresponding map also has these three parameters for the key).
•  » » » » » 4 weeks ago, # ^ |   +12 Bro i know that much.I think code looks pretty with arrays anyways your choice
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 3 →   -44 (please don't assume genders)To each their own, but I prefer maps for various reasons: Arrays require the scenario to be described by an index (possibly multi-dimensional), but maps can adapt to any type of scenario. The size of the map is equal to the number of cases encountered, whereas the size of the array would be based on how large the value gets. This is notable for problems where the scenarios may involve very large values but you don't actually encounter too many different scenarios within a single test case. For a scenario that was not encountered, the default for a map is that the scenario simply doesn't exist in the map, and you can check this with the count function. But for an array, every scenario begins with a default value (0, false, "", etc), which might, in some cases, actually be legitimate possible answers, so you're forced to come up with some impossible value to fill up your array before each test case, or make a second boolean array to distinguish between encountered and non-encountered. The only real downside to maps imo is that checking and retrieving values takes $O(\log (\text{map size}))$ time (as opposed to $O(1)$ time with an array), but this is generally fast enough for the vast majority of problems, especially since the map size only scales with the number of reachable scenarios. EDIT: As later replies demonstrated, the time constraints and input sizes would not actually have accommodated the additional logarithmic factor. The acceptance of my submission was due to how successive map lookups involved keys in close proximity, so there were fewer cache misses and the worst-case runtime was not invoked as often. I would not recommend relying on this kind of approach to achieve the runtime. I do still stand by my general opinions on the advantages of maps, but I agree that its use in this particular problem is not justified due to the time complexity disadvantage.
•  » » » » » » » 4 weeks ago, # ^ |   +24 Your condescending tone is so cute, although it is nice that you actually explained your approach. this is generally fast enough for the vast majority of problems Is it though? I'm actually very surprised that your solution did not get TLE. It sounds like almost $10^7$ operations with maps, which I wouldn't expect to fit in 5 seconds, not to say 2.
•  » » » » » » » » 4 weeks ago, # ^ |   +75 Don't be very surprised, it is actually quite easy to explain!Maps are slow, and can't do $10^7$ random access operations in 5 seconds, because of one reason — cache misses. When you search for an element in a map, you need to look at $O(\log n)$ random memory locations, which is slow, if you haven't accessed it recently.But if you search for an element, which is located near the element you already searched, it should work pretty fast as most memory locations of the tree path to that node should be in cache.In the case of the LightBrand99's code, to calculate dp for $(l, r)$, first $(l+1, r)$ is calculated recursively, and then $(l, r - 1)$.If you write down the actual order in which dp states are calculated, in most situations we don't go to the $(l+1, r)$ child, because it is already calculated, and just go to the $(l, r-1)$, then to $(l, r - 2)$, then to $(l, r - 3)$, and so on.And such elements are located close to each other in the map, so access is fast.For example, if instead of storing pair $(l, r)$ in the map, we use $(r, l)$, it gets TL: 171450551.Or if we first calculate $(l, r - 1)$ instead of $(l+1, r)$, it also gets TL: 171451903.
•  » » » 4 weeks ago, # ^ |   0 What is the time complexity for this solution ?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   -7 It takes $O(n^2 \log n)$ time because there are $O(n^2)$ substrings, and we'd look for them in the map at most twice. The memoization ensures that revisiting the same case will take $O(\log n)$ time to return the past answer (saved in a map). For $n = 2000$, this is actually really risky and I would not recommend this (see other related comments for why my submission was fortunately accepted despite appearing to be too slow).
•  » » » » » 2 weeks ago, # ^ |   0 Is it not $\Theta\left(n^2\log n\right)$ due to the use of maps?
•  » » » » » » 2 weeks ago, # ^ |   +5 Yes, you're right, sorry about that. I'll edit it, but idk if anybody would see it. My approach was already demonstrated as being unsuitable for the time constraints, with the AC verdict being a fortunate outcome of how the specific sequence of map lookups resulted in fewer cache misses than a worst-case estimation (due to the close proximity of successive key lookups), and it is not recommended to attempt this kind of risk in general. I agree with the assessment and would not advise anyone to follow my approach (I guess I sorta assumed that the downvotes would take care of the visibility, but that might not be the case).
•  » » » » 3 weeks ago, # ^ |   0 marajuana
 » 4 weeks ago, # |   +2 I couldn't solve C, and felt its implementation would be pretty tough. This is a me issue though, great contest anyways.
•  » » 4 weeks ago, # ^ |   0 Me 2 bro :(((
 » 4 weeks ago, # |   0 how to solve C?
•  » » 4 weeks ago, # ^ |   0 Hint: use a heap.
•  » » 4 weeks ago, # ^ |   +25 I did the following Greedy:Pick the biggest element in each array. If they are equal, they are a match, ignore them. If they are different, apply f to the biggest one.Keep doing until every element has a match.
•  » » » 4 weeks ago, # ^ |   0 Great Approach
•  » » » 4 weeks ago, # ^ |   0 This kind of simulation with a priority queue might be called a trial tree?
•  » » 4 weeks ago, # ^ |   0 Use a map and compare the frequency
 » 4 weeks ago, # |   0 How did you solve C?
•  » » 4 weeks ago, # ^ |   +3 I maintained 2 multisets corresponding to each array, and in each iteration I compared their largest elements. If equal remove them. Otherwise replace the larger one with its reduced version, as it cannot be obtained by any other reduction.
•  » » » 4 weeks ago, # ^ |   0 Very simple approach, a multiset didnt come to my mind in the moment, I did weird stuff with a map, thanks a lot, ill give it a try
•  » » 4 weeks ago, # ^ |   0 Video Solution for Problem C. Will upload D in the morning.
 » 4 weeks ago, # |   0 Great contest. Solved till D after a long time. 499 Rank. Got stuck at E. Learnt diophantine equations mid-contest, but did not get how to answer queries in O(1).
•  » » 4 weeks ago, # ^ |   0 queries in O(1) seems a little crazy, think on ternary search, to the n+1 possible ways of buying pepper
 » 4 weeks ago, # |   +39 Is it ever possible for Bob to win in D? I have the conditional in my code, but I don't think it is ever actually hit.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   -13 sorry, seems like I misread the question.
•  » » » 4 weeks ago, # ^ |   0 String should be even as per the question.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   -8 sorry, seems like I misread the question.
•  » » » » » 4 weeks ago, # ^ |   +5 baab gives me Draw on running my code
•  » » » 4 weeks ago, # ^ |   0 The length of the string $s$ is even.
•  » » 4 weeks ago, # ^ |   -28 bacd
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   +11 my logic was: they're all different. It doesn't matter what the first two moves are in this example cuz at the end they're gonna be two different characters and A just has to pick the smaller of the two, leaving B to pick the biggest and thus the first string is smallerAfter that I sketched a proof using induction that the string HAS to be a palindrome for B to have a draw, apparently it's wrong tho LOL
•  » » » » 4 weeks ago, # ^ |   +8 aabb isn't a palindrome but is a draw. Alice and Bob both end up with ab if they play optimally.
•  » » » 4 weeks ago, # ^ |   0 Gives me Alice on running my code
•  » » » 4 weeks ago, # ^ |   +11 Alice takes 'd'. Doesn't matter whether Bob takes 'b' or 'c': Alice will take 'a' and win, right?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +4 bruh wtf, I didn't noticed it was they were prepending the char, I thought they were appending instead
•  » » 4 weeks ago, # ^ |   0 Seems like no? I mean if Alice can just be greedy and pick something at least as good as Bob every step, so Bob can't win?
•  » » 4 weeks ago, # ^ |   +9 If the first letter and last letter are the same, Alice must take one of them while the optimal move for Bob is to take the other. If they are different, draw comes if and only if all continuous segments have a length of even, like "aabbbbaaaa". Otherwise Alice wins. Poor Bob.
•  » » » 4 weeks ago, # ^ |   0 Why?
•  » » » 4 weeks ago, # ^ |   0 I don't think that draw is iff all continues segments have even lengths. Take abccba for example, it's clear that Bob can just "mirror" the Alice's turn and therefore they end up with the same string. Did I misunderstand your condition?
•  » » 4 weeks ago, # ^ |   +5 Nope. If my solution is correct then he can never win since this observation is the sole basis for my solution lol
•  » » » 4 weeks ago, # ^ |   0 but for s="baab". bob will win. beacuse no matter which 'b' alice picks, bob will get an 'a'. right ?
•  » » » » 4 weeks ago, # ^ |   0 The character being picked is prepended to the string, not appended. If Alice picks b and Bob picks a, then Alice picks a to get a final string of ab, leaving Bob to pick b to get a final string of ba. In this case, Alice wins.It would actually be optimal for Bob if, after Alice picks b for the first move, Bob also picks b, so they both end up with ab, which is a draw.In any case, it's always impossible for Bob to win if Alice plays optimally.
 » 4 weeks ago, # |   -11 My answer for B, I think, is correct, but I got WA.
•  » » 4 weeks ago, # ^ |   0 ...that means it wasn't correctTry $n = 5$. Your sequence generates [3, 2, 1, 4, 5]. The 3 raises $x$ to 3. The 2 resets $x$ to 0. The 1 raises $x$ to 1. The 4 raises $x$ to 5. The 5 resets $x$ to 0.Your idea of ending with $(n - 1)$ and $n$ was correct, but what's critical is that the element before $(n - 1)$ must cause $x$ to reset to 0. If $x$ ends up increasing instead, then it's impossible for $x$ to accept both the $(n - 1)$ and $n$. Constructing the first $n - 2$ elements is the second challenge here (which is still easy, but it's not as trivial as you thought).
•  » » » 4 weeks ago, # ^ |   0 Thanks; I still keep making silly mistakes, gotta be more careful.
 » 4 weeks ago, # |   +2 The hardest Div.2 round I've seen.
•  » » 4 weeks ago, # ^ |   0 believe me it's not
•  » » 4 weeks ago, # ^ |   +17 Don't think so, at least E is easier than normal, it's pretty trivial if you know exgcd.
 » 4 weeks ago, # |   +5 Probelm A.can you please point out why this submission in wrong. 171352491
•  » » 4 weeks ago, # ^ |   0 you reset the initial maximum value before the input. you'll get AC after you fix this.
•  » » 4 weeks ago, # ^ |   0 Int ma=v[0] called before input
•  » » 4 weeks ago, # ^ |   0 Dear rezidentura, you should put ma = v[0] after the line of cin.
•  » » 4 weeks ago, # ^ |   0 ma = v[0] after cin >> v[i] loop;
•  » » 4 weeks ago, # ^ |   0 try reading the input before the line you give value to ma
•  » » 4 weeks ago, # ^ |   0 Hhhhhhh so stupid. Anyway thank you.
 » 4 weeks ago, # |   0 multiplying my memory just by 2 killed me on D &_& got AC just by deleting that extra parameter
 » 4 weeks ago, # |   0 How to solve D ?
•  » » 4 weeks ago, # ^ |   -13 My solution#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef long double ld; typedef pair p32; typedef pair p64; typedef pair pdd; typedef vector v64; typedef vector v32; typedef vector > vv32; typedef vector > vv64; typedef vector > vvp64; typedef vector vp64; typedef vector vp32; double eps = 1e-12; #define forn(i,e) for(ll i = 0; i < e; i++) #define forsn(i,s,e) for(ll i = s; i < e; i++) #define rforn(i,s) for(ll i = s; i >= 0; i--) #define rforsn(i,s,e) for(ll i = s; i >= e; i--) #define ln "\n" #define dbg(x) cout<<#x<<" = "< void swp(T&a,T&b) { T temp=a; a=b; b=temp; } // Useful Funcs // smallest prime divisor // int smp[100001]={0}; // void calcPrimes(){ // forn(i,100001){ // smp[i]=i; // } // ll ct=2; // while(ct*ct<100001){ // if(smp[ct]==ct){ // for(ll j=ct*ct;j<100001;j+=ct){smp[j]=ct;}} // ct+=1; // } // } ll ceil_div(ll a, ll b) {return a % b == 0 ? a / b : a / b + 1;} // Recursive function to calculate gcd long long gcd(long long a, long long b){ if(b==0) return a; return gcd(b,a%b); } /* Iterative Function to calculate (x^y)%p in O(log y) */ long long modex(long long x, unsigned int y, long long p) { long long res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p if (x == 0) return 0; // In case x is divisible by p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res*x) % p; // y must be even now y = y>>1; // y = y/2 x = (x*x) % p; } return res; } int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; // If the element is present at the middle // itself if (arr[mid] == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); } // We reach here when element is not // present in array return -1; } // STL binary search functions // binary_search(start_ptr, end_ptr, num) // returns true if element present, // otherwise returns false. // upper_bound(start_ptr, end_ptr, num) // returns the first index having value // greater than num. // If there is no such index, then returns // length of array. // lower_bound(start_ptr, end_ptr, num) // returns the fiirst index having value // not less than num // Subtract v.begin() or a(in case of array) to get index. // Pointers // for array-> a, a+x // for vector-> v.begin(), v.begin()+x, v.end() const ll MOD = 998244353; const ll mod = 1e9+7; void solve(){ string s; cin>>s; ll n = sz(s); vv64 dp(n,v64(n)); for(ll l=2;l<=n;l+=2){ for(ll i=0;i<=n-l;++i){ ll j = i+l-1; if(l==2){ if(s[i]==s[j]) dp[i][j]=3; else dp[i][j]=1; } else{ ll res1=0,res2=0; //a[i] ll r1=0,r2=0; //a[i+1] if(dp[i+2][j]!=3) r1=dp[i+2][j]; else if(s[i+1]s[j]) r2=1; else r2=3; if(r1==2 || r2==2) res2=2; else if(r1==3 || r2==3) res2=3; else res2=1; if(res1==1 || res2==1) dp[i][j]=1; else if(res1==3 || res2==3) dp[i][j]=3; else dp[i][j]=2; } } } if(dp[0][n-1]==1){ cout<<"Alice\n"; } else if(dp[0][n-1]==2){ cout<<"Bob\n"; } else{ cout<<"Draw\n"; } } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif fast_cin(); ll t; cin >> t; for(int it=1;it<=t;it++) { solve(); } return 0; } 
•  » » » 4 weeks ago, # ^ |   0 What if the importance of DP here?
•  » » » » 4 weeks ago, # ^ |   0 dp[i][j] gives answer only for i to j part of string. 1 if Alice 2 if Bob 3 if Draw
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 Hint 1Did you see the constraints? Hint 2Try DP!My Submission
•  » » » 4 weeks ago, # ^ |   +1 Always try to add explanation otherwise your comment is pointless.You added hints but its also important to add explanation.Can you add it in a spoiler?Like this Explanation... Your explanation here
•  » » 4 weeks ago, # ^ |   0 My approach was just recursive DP + memoization. Make a function for Alice's turn with arguments for left index and right index of the remaining string. Make a function for Bob's turn with arguments for left index and right index of the remaining string AND the latest character that Alice picked (important for tie-breaks). Check base cases (length 2 for Alice, length 1 for Bob), check if this case was encountered before (use two maps to store results, one for Alice, one for Bob), and if neither of those hold, then recursively check the two choices (pick first or pick last character). Obviously pick the winning choice if you can, but otherwise try to force a draw. My submission: 171425586 (sadly, it was uploading right when the timer hit 0, so it didn't count ;~;)
 » 4 weeks ago, # |   0 Why I always solved out the last problem I've tried just a minute after the ending ?
 » 4 weeks ago, # |   +8 Any hints on E?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +8 I think you may precalculate $dp[i] (0 \leq i \leq n)$, where $dp[i]$ represents the max taste you can get using $i$ red peppers and $n-i$ black peppers. The key observation is $dp$ could be decomposed into two parts, the ascending part $A$ and the descending part $B$ such that $A \cap B = \emptyset,\,A \cup B = \{0, 1, 2, ..., n\}, 0 \leq |A| \leq n+1, 0 \leq |B| \leq n+1$. For example, $dp$ could not increase, decrease, then increase. So you only have to search around the peak point.Here is my submission: 171418858. Welcome to hack me!Update: Hacked!
•  » » » 4 weeks ago, # ^ |   0 I did the same. Just use exgcd to find a particular solution so you don't get TLE, and then get it close to the peak point. My submission: 171477615.
•  » » » » 4 weeks ago, # ^ | ← Rev. 9 →   0 The 171418858 is written in a hurry. After being hacked, I review my code and find it is potentially flawed. The problem lies in the following two lines:for(; lp >= 0; lp -= xj) -- line1for(; rp <= n; rp += xj) -- line2If yj > xj, These two steps may execute up to $O(n)$ steps. So we need to swap xi and yj if yj > xj. If xj >= yj, then:(1) line1 executes at most O(peak/xj) <= O(n/xj) steps.(2) line1 executes at most yj <= xj steps to find a lp such that (n $-$ lp)%yj == 0.So the complexity is min(O(n/xj), O(xj)) <= O($\sqrt n$). This is sufficient. Similar idea works for line2.Devil is in the details. In Chinese words, 细节决定成败. I write this code really in a hurry. Reading the problem takes me too much time. Anyway, thanks hacker @robostac!
•  » » » » » 4 weeks ago, # ^ |   0 That's cool, I got it. And I think you wanted to write min(O(n/xj), O(xj)) instead of max.
•  » » » » » » 4 weeks ago, # ^ |   0 Yes, typo. Exgcd is a better choice.
•  » » » » » 4 weeks ago, # ^ |   0 O(Nsqrt(N)) is not enough unless you add a lot of cutoffs, at which point it is easier to write the O(log A) per query solution and not try to fit in anything else. If anybody has a good O(sqrt(N)) solution which fits in TL, please show. I could not fit it in during the contest.
•  » » » » » » 4 weeks ago, # ^ |   0
•  » » » » » » » 4 weeks ago, # ^ |   0 That's a cool solution! I was too lazy to precalc all factors, but that seems to be the missing part in my solution. Thank you for sharing.
 » 4 weeks ago, # |   +3 I can't find a case where Bob wins. Alice always wins right?
•  » » 4 weeks ago, # ^ |   +9 I modified my submission to call Bob a loser if he somehow wins and it still got accepted: 171428919So the only question is whether Alice wins or Bob forces a draw. Kinda like tic-tac-toe.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 baccabsorry ,misread the question , i thought that character should append at last
•  » » » 4 weeks ago, # ^ |   +1 Alice picks a b. WLOG, let's assume it's the first b.If Bob picks a b, we're at acca, which is a forced draw (identical to second test case). If Bob picks the a instead, we're at ccab. Here, Alice can pick c. Then no matter what Bob picks next, Alice can claim the a and get a string starting with a, which will beat whatever Bob picks. So Bob can only force a draw at best.
 » 4 weeks ago, # |   +7 How many got a +1 in D because of appending and not prepending?PS: Me even after reading that
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 i realised it now after trying that question for 1 hour.
•  » » 4 weeks ago, # ^ |   0 Yup realized it after the end of the contest. FML :(
•  » » 4 weeks ago, # ^ |   0 I got +2 for misreading the same :(
 » 4 weeks ago, # |   0 How to solve B?
•  » » 4 weeks ago, # ^ |   0 you need to output the biggest two number last so you make it reset every two number For example : n=15 7 8 6 9 5 10 4 11 3 12 2 13 1 14 15
•  » » » 4 weeks ago, # ^ |   0 can you tell me whats wrong in my solution? https://codeforces.com/contest/1728/submission/171372656
•  » » » » 4 weeks ago, # ^ |   +3 $1$ does not forcefully reset the value, it can in fact change the value to $1$ if it is currently $0$. you need a different way.
•  » » » » 4 weeks ago, # ^ |   +2 It doesn't guarantee that the (n — 2)-th element will reset $x$ to 0. For example, consider $n = 6$, where your code generates [2, 3, 4, 1, 5, 6].2 increases $x$ to 2.3 increases $x$ to 5.4 resets $x$ to 0.1 increases $x$ to 1 (!!!)5 increases $x$ to 6.6 resets $x$ to 0.You need to generate the first $(n - 2)$ elements in a more intelligent manner that guarantees that the $(n - 2)$-th element triggers a reset. Hint: handle even and odd cases separately.
•  » » » 4 weeks ago, # ^ |   0 Hey thanks I got it now feelin stupid :(
 » 4 weeks ago, # |   -22 Congratulations awoo with my last educational round in which I participated from any account.
•  » » 4 weeks ago, # ^ |   0 Why bro? what happend?
•  » » » 4 weeks ago, # ^ |   +8
 » 4 weeks ago, # |   +4 so many constructive >:(
•  » » 4 weeks ago, # ^ |   +10 Just a glitch of Codeforces (
 » 4 weeks ago, # |   +42 Is there something wrong with G?I tried to hack with a testcase with $m=18$, but I received Invalid Input because it said $m$ should be in the range $[1,16]$.
•  » » 4 weeks ago, # ^ |   +9 Yes, there is. About 40 minutes before the contest, I've noticed that one specific version of model solution runs too close to TL, so I decided to drop the constraints to $16$, but totally forgot to update the statement. I am sorry for this issue.Since I don't want to affect the people who got AC during the contest, I will change the problem statement, so it coincides with the validator.
 » 4 weeks ago, # |   -8 In problem C In one operation,1.pick some integer i from 1 to n; 2.assign either f(ai) to ai or f(bi) to bi.What should I select, only one index? or some indices?if it is only one index.Then, what does it mean by some?or Am I thinking in a wrong way?
•  » » 4 weeks ago, # ^ |   0 The problem means you can do the operation as much as you want and in each time you should select only one index
 » 4 weeks ago, # |   0 if I hacked a solution and my hack was unsuccessful will my standing be down?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +14 No, educational rounds and div3/4/5/6/7/8/9/10 rounds don't have any scoring hacking phase!
•  » » 4 weeks ago, # ^ |   0 No.
 » 4 weeks ago, # |   0 What is the test case hackers are using to break a lot of solutions on Problem C?
•  » » 4 weeks ago, # ^ |   0 I want to know, too. It hack successfully to my O(n) solution.
•  » » » 4 weeks ago, # ^ |   0 Probably the python dictionary hack ? https://codeforces.com/blog/entry/101817
•  » » 4 weeks ago, # ^ |   0 They hack unordered_map by selecting specific numbers that would lead to hash collisions and make each operation O(n) instead of O(1) and the whole solution to be O(n^2)
 » 4 weeks ago, # |   0 So is the C question today again facing the dictionary hack in python that happened a few contests ago? Makes me wonder about the extent of this disadvantage for python users. BTW I guess this can be fixed by taking random XORs to reduce collisions while hashing.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 How to hack hash tables and how to prevent hacks on hash tables is a very important discussion topic on Codeforces. Now that you learnt this time, you can either salt the hash or otherwise not use the hash table at all from now on.
•  » » » 4 weeks ago, # ^ |   0 Well i didn't use it because i am aware of it. I agree this is an important topic and everyone should be aware of this
 » 4 weeks ago, # | ← Rev. 2 →   0 Code is giving correct output for "ba" on local but wrong on CF. Please someone help. last tells Alice made previous move on l-1(last = 0) or r+1(last = 1) or nowhere and win tells in the suffix where both alice and bob has put characters who was dominating recentlystores 0 -> loosing, 1-> winning 2 -> draw state
•  » » 4 weeks ago, # ^ |   +3 you should access dp after checking if l > r because r might be -1
•  » » » 4 weeks ago, # ^ |   0 Thanks a lot. Why the verdict wasn't Runtime error.
•  » » » » 4 weeks ago, # ^ |   +1 Out of bound is not a runtime error but undefined behavior.
 » 4 weeks ago, # |   0 I could not solve Problem B in the contest But I like it because it teases my Brain to think over it ?
 » 4 weeks ago, # |   0 Very nice problems A B C!
•  » » 4 weeks ago, # ^ |   0 After looking at the solution of C, it looked pretty standard and reminded me of some greedy problems I solved some time ago. I am actually curious about the proof though.
•  » » » 4 weeks ago, # ^ |   +1 dk if this might help but look at it this way First remove anything in a that’s in b and remove anything in b that’s in a , then turn apply operations on all number that’s greater than 9 in both a and b, let the number of operations be ans , now do the same as step one where you remove elements, now the remaining ones HAVE to be converted to 1 so just count the number of remaining number of numbers greater than 1 and add it to ans , this is your answer
•  » » » » 4 weeks ago, # ^ |   +1 yeah, I noticed this, but I am looking for a formal proof (why applying from biggest is optimal)
•  » » » » » 4 weeks ago, # ^ |   +1 Hmm I’m bad at formal proofs , so , sorry , can’t help you there , maybe that’s why I’m still a pupil haha
•  » » » » » » 4 weeks ago, # ^ |   +1 maybe tomorrow you will become specialist
•  » » » » » » » 4 weeks ago, # ^ |   +1 Cf predictor is saying only +30 so I doubt it , I took wayyy too long to solve A , idk I was being dumb
•  » » » » » » » » 4 weeks ago, # ^ |   +1 oh, let's look forward to the Div.3 contest coming soon then
•  » » » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 8 months back cf-predictor always underestimated my delta but now it always overestimates it
•  » » » » » » » » » 4 weeks ago, # ^ |   0 Yea, i also feel cf predictor is giving more than actual delta nowadays. It says 15 for me i just hope its not negative at this point lol.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 It doesn't have to be the biggest, but you do need to deal with multi-digit numbers before the single-digit numbers.My approach was to first remove elements that appear in both arrays, so now the two arrays have no overlaps. Now that there are no overlaps, we now apply the operation on every number that's $\geq 10$ (contains 2 digits or more). As proof of why this is always required, note that the values are only as high as $10^9$, so there is no number with 10 or more digits. Therefore, the operation can only produce numbers from 1 to 9. So if you have a multi-digit number $x$ in the first array while the second array has no $x$, then it's impossible to produce $x$ in the second array through operations, and it is therefore necessary to apply the operation to $x$ on the first array. After these operations, the arrays have only one-digit numbers. We can remove overlaps once more (no operations performed) until there is no element appearing in both arrays. At this point, we have to transform everything into 1, so we count the number of non-1s, applying that many operations to turn them all into 1, after which we are done.
•  » » » 4 weeks ago, # ^ |   0 Note that the operation is individual for each number and the operation will make a number smaller. So let's just consider the biggest number and assume it is in A. If there's a number in B that equals to A then alright remove them all. If not, it's clear that we should apply operations on it or we won't find a number to match it.
•  » » » » 4 weeks ago, # ^ |   0 As for the time complexity, considering we can make all the numbers to 1, and the numbers of operations is not more than 2, so the total number is mot more than 4n.
 » 4 weeks ago, # |   -24 Did you know that adding more samples is totally free?
 » 4 weeks ago, # |   0 Any hint for E? I know how to precompute the best answer for $i$ red peppers for all $i$, but I don't really know how to deal with the queries fast enough. I guess I'm missing some observation.
•  » » 4 weeks ago, # ^ |   +8 Probably the diophantine equations and the extended euclidean algorithm are what you are missing.
•  » » » 4 weeks ago, # ^ |   0 I actually knew about that but I was just thinking how should I iterate all possible solutions to find the maximum. I just noticed I only needed to check the 3 closest solutions to the global maximum since after sorting the peppers by difference, the tastiness function is a parabola.
•  » » 4 weeks ago, # ^ |   0 exgcd
 » 4 weeks ago, # | ← Rev. 3 →   0 Is there anyone can hack my C problem?
•  » » 4 weeks ago, # ^ |   0 Can you briefly describe your approach? I'm having a hard time understanding what you're doing...
•  » » » 4 weeks ago, # ^ |   0 Frstly,if there are some pairs of numbers which are same to each other,we could ignore them.Secondly,all the numbers'lengths are under 9,so if some numbers'lengths are beyond 9,we can only converts them into numbers beneath 9 so that they have chance to be the same to another number.
 » 4 weeks ago, # |   0 For C, what is the proof that if you have a match, you always want to pair them immediately?
•  » » 4 weeks ago, # ^ |   0 Suppose you have $x > 1$ an even number of times (and you already dealt with bigger numbers). Suppose you change one of them to $f(x)$. Now the amount of $x$ would be odd, which means one $x$ would have no pair, so you must actually change both of them to $f(x)$. But both $f(x)$ are equal, so you just did two unnecessary operations, because you could just match them when they were $x$.
 » 4 weeks ago, # |   0 Can anyone please help me where I am wrong? Talking about problem C.My submission : https://codeforces.com/contest/1728/submission/171436863
•  » » 4 weeks ago, # ^ |   0 Can you please briefly describe your approach? It's hard for me to figure out exactly what you're doing.
•  » » » 4 weeks ago, # ^ | ← Rev. 4 →   0 Yeah sureI made 2 vectors a and b initially. Then I made a vector a1 and map m1.a1 contains elements of a that are not matching with elements of vector b. similarly m1 contains element of b that are not matching with elements of vector a.then I iterated over a1:let e be element of a1 if(e>1&&e<=9)then I tried finding any element in m1 that is of e length, example for e=3, I will find for any element between 1,000 and 9,999 inclusiveif any such element exist (let say we got 867) then I increased my answer by 1 (because 867 takes 1 operation to be equal to 3) and then we remove found element from the map m1.else answer+=1 because this element is now converted to 1 e>9lets say e=13 now firstly I calculated the digits in element e (lets name it as d)case 1 : if d is present in map m1 then we decrease one occurrence of d in m1 and increase our answer by 1(because e is of length > 1)case 2 : if any d digit number is present in m1 then we decrease one occurrence of that number in m1 and increase our answer by 2(because e is of length > 1 && number found in m1 is also length > 1)else : ans+=2 because we are not able to match this element with any of the element with b and it should be made 1 for further matching.now we iterate over remaining element in m1 (lets name this element as p) if(p==1)continue; if(p<=9)ans++; else ans+=2Code link : https://codeforces.com/contest/1728/submission/171436863 Giving WA on TC2 Revision 1 : AC now!
 » 4 weeks ago, # | ← Rev. 4 →   +83 I think I have an $O(n)$ solution for Problem D. 171446061If the string has following structure: $ABC$Where $AC$ is a palindrome and $B$ is made out of pairs of equal letters (e.g. aahheeiiwwmmyy), then it is a draw. Else Alice wins. ReasoningIf the string has the structure $ABC$ then bob can always pick the same letter as Alice picked. This forces a draw. The other direction seems not so obvious. As long as the last $2$ remaining letters are different, alice just picks the smaller one and wins. If Bob somehow forced the last $2$ letters to be identical, then alice had to pick the smaller one out of the penultimate $2$ letters, (or force the last two to be different). This reasoning can be extended I guess, but I have no formal proof.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +18 Nice structure! I think I have some argument. Suppose we have a string of minimum length that Bob can win, denoted by a1 a2 X a3 a4. Bob must pick smaller letter than Alice at the first turn, since the best outcome afterwards is a draw. Hence, we have three posibilities:(1) a1 > a2 and a4 > a3i) a1 = a4X a3 a4 must be a draw, and a1 a2 X must be a draw, so X = a4 a3 Y a2 a1. We now have that Y a2 a1 and a4 a3 Y must be draws. This repeated chain can't end, contradiction.ii) wlog a1 > a4a1 a2 X must be a draw, so X = Y a2 a1, where Y is a draw. Hence, when Alice pick a1 in a1 a2 Y a2 a1 a3 a4, neither a2 Y a2 a1 a3 nor Y a2 a1 a3 a4 can't be a draw, contracdiction.(2) a1 > a4 and a4 > a3 (and thus a1 <= a2 by excluding (1)), i.e., a2 >= a1 > a4 > a3.If Alice pick a1, Bob should choose a4. a2 X a3 must be a draw. Since a2 != a3, X = a2 Y a3 where Y is a sequence of pairs of identical letters. Now, Alice pick a4, Bob should choose a3, and a1 a2 a2 Y a3 can't be a draw, since a1 != a3.(3) a4 > a1 so a1 > a2, which is symmetric to (2)
•  » » 4 weeks ago, # ^ |   +8 Great solution! Could you share your logic on deducing ABC template for draw scenarios? It took me significant amount of time to do it, perhaps your way is faster?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Bob wants to force a draw by always picking the same letter as Alice. There are only two possible answers to Alices moves. Either pick on the same side as Alice or on the other side. In the palindrome situation Bob needs to pick always the other side as Alice did pick. In the $B$ situation Bob always needs to pick on the same side as Alice picked. Transition from palindrome to $B$-situation works out for Bob. Transition from $B$ to palindrome does not work out. Alice can start picking on the palindrome before the $B$ part is finished, so one side of the palindrome won't be reachable. So the structure needs to be $ABC$.
 » 4 weeks ago, # |   0 I messed up this round and got a rank in the 8000s. I hope to perform well in the upcoming contests <3
•  » » 4 weeks ago, # ^ |   0 Same, will lose green after the ranks are updated. I don't think I've gotten a positive delta in an Edu round, but generally I always learn something so it's worth the drop in points.
•  » » 4 weeks ago, # ^ |   0 In my experience, messing up in a manner that is not reflective of your skill level is usually not a problem (unless it happens a lot). Even if your rating decreases by a lot, it would quickly climb back up when you do later contests at your consistent skill level. The initial drop means you'll generally gain more rating in the next contest, so you should quickly catch up. More importantly, I hope you actually learned more from doing the contest and improved, even if only slightly. Improving your personal skill level would eventually lead to consistently maintaining a higher rating, despite the occasional drops from randomly choking.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Nice thought! One of my problems is that I get stuck in a problem, and then struggle with it for 45 mins or even an hour. Then during upsolving I realise that the problem was not that difficult and could have solved it within 15 mins. In short, I think I can solve problems, but I take so much time that my rating doesn't increase as much as it should, or even decrease. Can you advice me on this?
•  » » » » 4 weeks ago, # ^ |   +4 Each person is different, so my advice may not necessarily be the best for you. However, my suggestion is that, when you find yourself struggling with a problem that you are able to easily upsolve later, try to think carefully about what was the crucial observation you missed that prevented you from solving it faster. I then recommend writing this down physically on paper. In my experience, this helps to avoid missing similar observations in the future.If you find that a particular issue arises frequently for you, then make a special note of this and try to make arrangements to remind you of this for future problems, e.g., adding it to your code template as a comment, placing a sticky note on the corner of your screen, etc. Eventually, you should get the hang of dealing with these issues quickly on your own.
•  » » » » » 4 weeks ago, # ^ |   0 I’m gonna try this thank you
 » 4 weeks ago, # |   0 B is a good question
•  » » 4 weeks ago, # ^ |   0 yes it is. First I tried to solve it using backtracking, but that approach didnt give answers fast wnough for n more than 10.
 » 4 weeks ago, # |   0 in problem D. if the string is baab the answer will be Bob right?? or is it a draw??
•  » » 4 weeks ago, # ^ |   +4 In each turn, the player add a character to the beginning of their string, not to the end. You probably miss this
•  » » » 4 weeks ago, # ^ |   0 Ohh shit I just wasted 5hours reading the question wrong. I was adding at the end of the string. Thanks man.
•  » » » » 4 weeks ago, # ^ |   0 Happened to me during the contest. Luckily, not much modification was required.
•  » » 4 weeks ago, # ^ |   +1 It's a draw, like following: 1. Alice chooses 'b' 2. Bob either chooses 'a' or 'b' 3. Alice choose 'a' 4. Bob choose the last one. So Alice has "ab" and Bob has "ab" or "ba", it's a draw.
 » 4 weeks ago, # |   +8 It seems that Bob can't win in problem D. I got the AC during the contest but still can't come up with an elegant proof to back it up. Any suggestions?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 in the test case "baab" Bob will win right??Update : sorry i read the question wrong. Please ignore.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +10 Nope he doesn't in this caseI had an inductive proof for that but it is too long still anyway: Base case: we will have a string of length 2. if the characters are different Alice wins, if the characters are same we'd have a draw. Recursive case: Suppose we have a string of length l where Bob wins. Since Alice can always pick the lesser of the first and last characters we'd skip the case where Alice and Bob pick characters from the opposite side. Consider the case where Bob and Alice pick the characters from the same side. For the recursive case we have made the assumption that Bob can't win for any string with length < l. Let the string be c1.c2.s(some string).cn-1.cn. If Bob wins then cn > cn-1 and c1.c2.s will result in a draw and c1 > c2 and s.cn-1.cn will result in a draw. Since the frequency of each character in a string which is a draw, is even, we get c1 = cn, c2 = cn-1. Now, we have c1.c2.s.c2.c1. Since, c1.c2.s is a draw string, if Alice decides to pick c1 then, s has to end with c1. In a similar way, s also has to start with c1. We keep on repeating this process, build s and we arrive at a contradiction at a position in s.
•  » » » » 4 weeks ago, # ^ |   0 Proof: As the length of the string is even. The deciding factor will be the last 2 remaining characters. Now the 2characters can be same or different if different then as alice gets the first pick she wins. If the characters are same then both of them have the same first letter in their own string. So the deciding factor will be the 2 characters picked before the last ones. Same logic here those 2 character can be same or different if different alice wins as she gets the first pick. If same then deciding factor will be the 2characters picked just before. And this will continue. So you can see that Bob can never win.
•  » » » » » 4 weeks ago, # ^ |   0 This line of thinking is not correct. In your own testcase baab. Either way, for the first pick Alice gets to pick b and Bob gets a, though Alice wins in the end.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 I just got the problem accepted. I read the question wrong and spent 5hours on the wrong question. I was adding the characters to the end of Alice and Bobs string.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I understand the pain.In many AC solutions I saw that people had recursions for the case where Bob wins and had print statements for Alice, Bob and Draw. But Bob doesn't win any game. So basically the cases where Bob wins are a contradiction among themselves and the code execution doesn't reach those lines. Yours too had provisions in case Bob wins. https://codeforces.com/contest/1728/submission/171455329
•  » » » » » » 4 weeks ago, # ^ |   +1 Even i did the same as it is a dp solution i dont need to waste time thinking if bob can ever win. Just check all possible ways and print who ever wins. If bob can never win "Bob" will never be printed anyways.
•  » » » » » » » 4 weeks ago, # ^ |   +1 Yepp true, I mistakenly believed that Bob can't win and ended up handling only Draws and Alice wins. It worked magically. Then I first realized I had the wrong idea which was actually correct but yeah I still don't have a more elegant proof for why.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I think you can look at a problem backwards. At last 2 letters Alice goes first and can choose lesser letter and win. So Bob can only hope for draw so last 2 letters should be the same.It means optimal strategy for Alice is choose at any step lesser letter, strategy for Bob is to choose the same letter as Alice for getting draw.I feel like problem can be solved in O(n) though I didn't solve itUPD. https://codeforces.com/blog/entry/106726?#comment-951491 found comment with O(n) solution. Looks like I missed a piece of observation with combining palindromes and pairs of same letters :(
•  » » » 4 weeks ago, # ^ |   0 Alice is not gauranteed to have the lesser letter at each move. Consider caac
•  » » » » 4 weeks ago, # ^ |   0 I did not say about guaranteeing. Only strategy
 » 4 weeks ago, # | ← Rev. 3 →   +13 In problem F, how to prove that the number of useful values is $O(n)$? I've added lots of trivial optimizations but still got TLE. Or is it maybe I need a faster max flow template?
 » 4 weeks ago, # |   0 awoo is one of the great authors. Problems will be original and creative undoubtedly (in my experience). Already happened this!
 » 4 weeks ago, # |   +16 Would appreciate if Educational rounds could release the editoral soon after the contests :) Most other contests have been doing so, and I think it would help for learning about unsolved problems while it is still fresh in our minds.
 » 4 weeks ago, # |   +1 Codeforces becomes Mathforces in these days
•  » » 4 weeks ago, # ^ |   0 Always has been
•  » » » 4 weeks ago, # ^ |   0 but when i solve c2j problems i see old contest qusestion that questions are some algo orieneted but now in live contest i see questions are mainly from numbertheory
•  » » » » 4 weeks ago, # ^ |   0 Well, math and algorithms are strongly interconnected, so there is nothing special about that. Some problems are from numbertheory, but in this round C and D were not
•  » » » » » 3 weeks ago, # ^ |   0 actually i am beginner so i am never get a opportunity to meet c and d question can u tell what topic is neccesary to become speclist ?
•  » » » » » » 3 weeks ago, # ^ |   0 As I remember you can get to specialist just by solving a and b very quickly. For that just solve 800-1100 problems, they usually don't require anything hard. Might be an easy dp, but that is learnable. If you find a problem with a dp tag, just look through the code of the solution, maybe do some research on CF/Google. As for C they usually require great understanding of STL data structures and/or constructives. C is most of the time around 1500, sometimes can get up to 2000, but that's a rare thing, and usually has such high rating because of a cringy solution. That's mostly it for the specialist
•  » » » » » » » 3 weeks ago, # ^ |   0 currently i am doing 1000 rated problem from c2j but see my profile i am consistant but my growth is nothing
 » 4 weeks ago, # |   0 I'm a newcomer in Codeforces.That's my 5th contest... But i have noticed it takes really long to update ratings on codeforces.. Why is it so?
•  » » 3 weeks ago, # ^ |   0 Because of the open-hack phase, it is for Edu and Div 3 (maybe also 4) rounds, lasts 12 or 24 hours. That's the main reason why it took so long
•  » » » 3 weeks ago, # ^ |   0 Thanks for the info mann.
•  » » » 3 weeks ago, # ^ |   0 Hey, Can you give me some guidance on how you reached expert so quickly..?
•  » » » » 3 weeks ago, # ^ |   0 I'm an 8 grader who learns AnDS in different school clubs + actively solving CF problems on different topics, also try CF EDUhttps://www.youtube.com/c/pavelmavrin this channel is cool.And finally I think there should be a website where there are most of the topics for CP
 » 4 weeks ago, # |   -8 When will the editorial be done, any idea anyone? Looking forward to it
 » 4 weeks ago, # |   +5 Is my Solution to A good? I feel like I wasted time to write such a solution, and could have written a much simpler solution in less time.https://codeforces.com/contest/1728/submission/171356537
•  » » 4 weeks ago, # ^ |   0 Yeah!, just print the index of highest element.
•  » » » 4 weeks ago, # ^ |   +5 Shit that was easy. Thanks
•  » » 4 weeks ago, # ^ |   0
 » 4 weeks ago, # |   -11 why are ratings still not published, is this round rated or unrated?
•  » » 4 weeks ago, # ^ |   +1 Edu round take time to update rating
•  » » » 4 weeks ago, # ^ |   +5 How long usually ? And why? Why different times to update ratings for different types of rounds ?
•  » » » » 4 weeks ago, # ^ |   0 There is no fix timing but it take long to update rating, the reason is after hacking phase they add hack test cases to thier test case file and then multiple times system testing
•  » » » » » 4 weeks ago, # ^ |   0 That's the kind answer that one expects from a competitive programmer
•  » » » » 4 weeks ago, # ^ |   +1 Because there is the 12 hour hacking phase and after that all the solutions need to be re-judged on the successful hack testcases. Oh and also Mike needs some rest too :)
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 mike Orz
 » 4 weeks ago, # |   +8 Via debugging E, I'm surprised to find out that -54/15=-3 (in c++) and -54//15=-4 (in py)
 » 4 weeks ago, # |   +15 When will the rating update?I cant wait to get a positive result.
•  » » 4 weeks ago, # ^ |   +3 Become specialist.Winwinwin!
 » 4 weeks ago, # |   0 If I solve any question even though I am div 4, will my rating go up??
•  » » 4 weeks ago, # ^ |   0 I think you will gain rating.It is easy to gain rating in your first six contest.
•  » » » 4 weeks ago, # ^ |   0 I’m in luck then :)
 » 4 weeks ago, # |   +6 I completed 2 problems in yesterday's contest still i am unrated. When does it gets updated?
 » 4 weeks ago, # |   +17 When will the ratings get updated and tutorial get released for this round?
 » 4 weeks ago, # |   +11 Why rating hadn’t changed yet isn’t it supposed to be after 2 or 3 hours just after open hacking phase?
 » 4 weeks ago, # |   0 I have read the problem B. It's clean but i can't solve. Help me! p/s: i just have solve as brute force thank you
•  » » 4 weeks ago, # ^ |   0 ok here is the idea u will notice that you can at most get the sum of the two largest numbers in the sequence that because each two consecutive positive integers must be greater than to the following number to them this is the case for n > 3 so if i give you n = 5 then max you can get is 4 + 5 which equals nine and if n = 8 then the result will be 7 + 8 and so on the problem comes is that how i make sure that when i start to count the two largest numbers the current res is 0 so if it is even n like this case n = 6 then the sequence will be like 4 3 2 1 5 6 which if you trace will get 0 4 0 2 0 5 11 so if it is even print from n-2 to 1 then print n-1 and n if n is odd like n = 7 then just replace n-2 with n-3 so it will be like that 4 5 3 2 1 6 7 which by tracing gives 0 4 9 0 2 0 6 13 and you can generalize this on any n.
•  » » » 4 weeks ago, # ^ |   0 nice explanation bro thx alot
•  » » » 3 weeks ago, # ^ |   0 thank you very much! Im clear
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Well,the basic idea is that the max ans in every case will be n-1 + n therefore the last two numbers will be n-1 and n, so we just have to arrange the rest numbers i.e from 1 to n-2 in an order such that it'll give zero after applying the given operation for those n-2 numbers. So there will be 2 trends one when n is even and other when n is odd.Just observe carefully you'll figure it out on how to arrange in both cases.
 » 4 weeks ago, # |   +13 when will be the rating changes?
 » 4 weeks ago, # |   +1 uhh... when will the rating update?
 » 4 weeks ago, # |   0 I started giving contest from the previous round. Its ratings were removed :( And now this round is not publishing ratings What's the problem with me universe???
 » 4 weeks ago, # |   +4 why haven't the rating changes appeared yet?
 » 4 weeks ago, # |   +1 I guess the rating will be updated after the #820 starts to register to prevent some bugs of rating calculation.
•  » » 4 weeks ago, # ^ |   0 No I believe it’ll happen on 20:05 IST
 » 4 weeks ago, # |   0 Why is my code giving tle on problem C(digital algorithm) using unordered_map but getting ac using map?
•  » » 4 weeks ago, # ^ |   0 In worst case, unordered_map can be O(n), but ordered map remains O(logn). Also memory usage is more as compared to ordered map.
•  » » 4 weeks ago, # ^ |   0 Why?Anti-Hashing Hacks Check this out for more. Tip: Always try to avoid unordered_map
•  » » » 4 weeks ago, # ^ |   0 Thanks a lot! Really helpful information.
 » 4 weeks ago, # |   0 sorry if this sounds non-sense question but i am really suck at solving div2c problems in generl can someone share his thinking process during this contest in order to get c? i knew the answer from the comments but i really can't imagine how could i get it in the contest
 » 4 weeks ago, # |   0 Why does the rating appear so late in Educational Rounds?
 » 4 weeks ago, # | ← Rev. 3 →   +5 My intuitive reasoning to D :First, because Alice play first and the length of the string is even, Alice can force Bob to take any particular character in the string by simply never take it. After Bob take this character either the string become empty and the game end, or it become a shorter string with even length, then we use this strategy again for the shorter string. By take advantage of this, when play optimally Alice will never lose.The only way for Bob to draw is to always take the same character as Alice. Now we reverse the game from the end to begin to see what the original string would look like :For each double turn of Alice + Bob, we add 2 identical character to the same side or different side of our string (for example : $aa \rightarrow aabb, bbaa$ or $baab$)The critical point is that if we add to the different side, we can't add to same side anymore. Take the example $baab \rightarrow baabcc$, here Alice can take $b$ and Bob can't take any $b$ so he will loseSo the form of our string is : half palindrome + some pairs + other half palindrome, the 1st and 3rd part form a palindrome
 » 4 weeks ago, # |   0 guys , When will each competitor points be determined?
 » 4 weeks ago, # |   0 In problem D why using global recursive function link gives AC whereas converting it into a recursive lambda link is giving MLE ?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 define int long long? Please comment this line and test it again yourself.
•  » » » 4 weeks ago, # ^ |   0 Oh, thanks!! I never thought this line could be nasty.
 » 4 weeks ago, # |   0 Hey everyone... is this round rated? I don't see my rating changes for 1 day (mostly, it takes under 1 day) so I just ask in curious.
•  » » 4 weeks ago, # ^ |   0 Yep, the round is rated, system testing has been done few minutes ago we may expect rating change soon!
•  » » » 4 weeks ago, # ^ |   0 Thank you so much!
 » 4 weeks ago, # | ← Rev. 2 →   0 Problem C was like a brainstorm for me but, I find it iconic OwO.Cant anyone provide me with problems with nearly same idea?
 » 4 weeks ago, # |   0 Can anyone explain me non-dp (greedy) solution for D? i.e. $O(n)$ solution?
•  » » 4 weeks ago, # ^ |   0 You can get an inductive/recursive proof for the type of string, once you get that code is fairly simple. Sketch/ApproachYou can uses the below steps as hints/ideas. First see the answers for n=2, n=4; try to see observations. Step 1Note that Bob never wins, use induction to prove it. Step 2Try and go recursively, note that after both players make 1 move, there are only 3 possible strings that be the remaining string. Step 3Note that a palindromic string = Draw, furthermore, if s[0]=s[n-1], and the substring in between them is a string that gets a Draw, then Bob gets a draw. This is one type of solution. Step 4If s[0]!=s[n-1], there is only one way Bob can get a draw, s[0]=s[1] and s[n-1]=s[n-2], with remaining substrings in both cases must get draw for bob. Step 5Use observations in hint 4 to prove that s[2]=s[3], s[n-3]=s[n-4], and similarly s[4]=s[5], s[6]=s[7] and so on. This is second type of solution.Combine both types of solutions and you will get the criteria for strings where Bob can get a draw, its easy to see confirm that Bob will always manage to get a draw in this. AnswerIf the string s is of the kind s = (a1,a2,...,a(n-1),an), then if for some 0<=k<=n, ai = a(n+1-i) for all 1<=i<=K, and a(k+1)=a(k+2), a(k+3)=a(k+4),..,a(n-k-1)=a(n-k), then the answer is a draw, otherwise Alice wins.Link to the code: https://codeforces.com/contest/1728/submission/171419727.
 » 4 weeks ago, # |   0 https://codeforces.com/contest/1728/submission/171513494https://codeforces.com/contest/1728/submission/171383658Does that small change actually speed it up by that much?
•  » » 4 weeks ago, # ^ |   0 What exactly is the meaningful change? It's hard to tell with how you also adjusted indentation and brackets and such
•  » » » 4 weeks ago, # ^ |   0 Oh it's because I used .count() which can be O(n) worst case.
•  » » » » 4 weeks ago, # ^ |   0 Uhh, I think .count() on a map would have runtime logarithmic to the size of the map, in the worst-case. If that's the only change, I'd be surprised if that led to the time limit exceeding. Then again, I suppose the check happens quite a lot in here...
•  » » » » » 4 weeks ago, # ^ |   0 Nah I used count on a multisrt
 » 4 weeks ago, # |   -28 Why did you skip my d? Do we have to ask everyone to use different ideas to solve the same problem? I don't understand
•  » » 4 weeks ago, # ^ |   +21 Because 171399055 vs 171411235.
 » 4 weeks ago, # |   -36 https://codeforces.com/contest/1728/submission/171413965 https://codeforces.com/contest/1728/submission/171404066 can you tell me why my code skipped look at my code it OBVIOUSLY not the same plz look at the two codes MikeMirzayanov
•  » » 4 weeks ago, # ^ |   +35 Absolutely same. Just stop cheating.
•  » » » 4 weeks ago, # ^ |   0 True. Heisenberg_2001 you just changed the variable names and thought that you are clever enough, but the Codeforces cheater-catching machine outsmarted you.
•  » » » 4 weeks ago, # ^ |   0 can you tell me when will the rating be updated, please.
•  » » » 4 weeks ago, # ^ |   +2 Hello mike, sorry to bother you here, can you please take a look at this aswell link
•  » » » 4 weeks ago, # ^ |   -24 it's natural there's a lot of people solve it with the same idea but the two codes are obviously different but if you open the two codes and still see it cheating Nevermind:)
 » 4 weeks ago, # | ← Rev. 2 →   +2 Why the rating hasn't been updated yet!?(┬┬﹏┬┬) MikeMirzayanov and where is the editorial? ◑﹏◐
•  » » 4 weeks ago, # ^ |   +7 Thanks , the rating is now changed !!❤
 » 4 weeks ago, # |   0 Hey, yesterday I had 3 accepted solutions and today I have only two. I've got TLE on this submission: 171386970Is it an error or is my solution bad?Can I download a test to check on my own?
•  » » 4 weeks ago, # ^ |   0 TLE because you used unordered_map, which can be hacked using anti-hashing. Just use map instead and try again.
•  » » » 4 weeks ago, # ^ |   0 Oh, thanks. I didn't know that.
•  » » » » 4 weeks ago, # ^ |   0 Check this link for more.
•  » » 4 weeks ago, # ^ |   -8 I think you can see the test cases for every submit now. Just look for "link" in bottom left corner of you submission link
•  » » » 4 weeks ago, # ^ |   0 I can see a "Click to see test details" but there are only like 70 of 200000 numbers followed by ellipsis in the test input. Am I missing anything?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Oh no, my bad. You can't download the tests it seems. But even if you download I don't know how would you evaluate TLEs. Do you know some hacks for it?
•  » » » » » 4 weeks ago, # ^ |   0 What do you mean by "evaluate TLE"? I would have executed my program and typed in the test. 2 seconds is a lot for a program that was supposed to be O(n) time complexity. Earlier, I thought I got TLE due to, for example, a lag of the CodeForces server.
•  » » » » » » 4 weeks ago, # ^ |   0 I mean the server running the tests might be having different configurations than your personal computer. So I was curious to know how would you identify TLEs because of this configuration changes.But surely O(n) solution should take less time than 2 seconds unless the built-in libraries used take O(n)
•  » » » » » » » 3 weeks ago, # ^ |   0 As far as I know, the configuration of compiler is available here. I'm not sure if there is no newer one.
 » 4 weeks ago, # |   0 Problems were amazing. hatsoff
 » 4 weeks ago, # |   -35 Hi, MikeMirzayanov.The submission 171396201 and 171412747 of 1728D - Letter Picking are just coincidencesI am sure I didn't copy the code or send it to others.Obviously, we have the same idea of this problem, and coincidentally, our code styles are similar.My submission is at 23:33(UTC+8) and the other one's submission is at 00:09(UTC+8). And this problem is simple for me. This ruled out the possibility that I copied his code.By the time he submitted his code, I had already came up with the solution to 1728E, so I am sure I can become yellow after this contest. I have no reason to send my code to others and cause me to be skipped.Moreover, solutions to 1728D are all very similar, except dfs and the O(n) solution. If necessary, I can find more submissions similar to mine.So I just have the same idea and similar code style with a stranger coincidentally.Thanks!
•  » » 3 weeks ago, # ^ |   +3 dont worry i had the samehe just ranomly does this to take the piss out of us at this point :|
•  » » » 3 weeks ago, # ^ |   0 sad:(
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 4 weeks ago, # |   +1 How to become pupil as soon as what topic really need to solve 1000 1100 and 1200 1300 rated problem ?
 » 4 weeks ago, # |   0 I am finally an expert. Thanks to this contest :)