By awoo, history, 2 months 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!

Our friends at Harbour.Space also have a message for you:

Hey, Codeforces!

We are thrilled to announce an amazing work & study opportunity with Vodafone.

Vodafone Group has partnered with Harbour.Space University to offer Bachelor's and Master’s degree scholarships in Computer Science, Data Science, Cyber Security and Front-end Development as well as MBAs and work experience in one of the leading UK telecommunication companies.

Vodafone Group is opening a new technological HUB in Malaga, an international center of excellence dedicated to research and development of technical solutions, such as Secure Networks, 5G and 6G development, Open RAN, IoT, MPN & MEC and UCC for Vodafone Business, platforms and enterprise solutions.

We are looking for various junior to mid level positions (or senior) to fill in different fields such as:

• Front-end Development
• Full-stack Development
• Backend Development
• Technical Architecture
• Enterprise Architecture

APPRENTICESHIP REQUIREMENTS

General Requirements:

• High School Diploma or Bachelor's Degree with prior work experience
• Proficiency in English (Spanish is a plus)

Requirements for Frontend Developer:

• At least 1-3 years of experience in Angular.
• At least 1-3 year of experience working in React.
• Strong knowledge of web platform fundamentals: HTML, JavaScript and CSS.
• Design and implementation of low-latency, high-availability, and performant applications
• Definition / construction of CI / CD pipelines using tools such as Jenkins, Sonar, Kiuwan.

Requirements for Full-Stack Developer:

• Minimum 3 years of proven experience in platform development (CDI/DevOps based environment). With one or more of the following:
• Java SE/ Javascript
• Scripting languages, i.e. python, perl, shell scripts.
• Proven experience in backend & frontend software systems & web applications.
• Proven experience with HTPP, MQTT, LwM2M, Kafka, various databases (SQL and non-SQL).
• Proficiency in cloud-native development.
• Hands-on experience with CDI tools.

Requirements for Java Developer:

• Industry experience with Software Platforms in Linux, on-premises and cloud
• Solid understanding of server technologies
• Strong academic knowledge and professional experience of software development: Java Enterprise, Oracle, Linux, Windows
• Good understanding of system monitoring tools and automated testing frameworks
• Experience with SQL, XML, JSON and CSV
• Experience of providing and maintaining transformations and APIs for customers and partners
• Good understanding of Databases – Oracle, MongoDB, ElasticSearch.
• Good understanding of java frameworks, SpringBoot, Spring technologies
• Good understanding of container systems (docker) and orchestrators (docker compose, Kubernetes) and messaging technologies, kafka, rabbitmq
• Good understanding of Unix shell, Perl, python to perform automation and maintenance tasks and CI/CD environments
• Educated to BSc degree level in telecommunications or related discipline with Software Development experience
APPLY NOW →

Good luck on your round, and see you next time!

Harbour.Space University

UPD: Editorial is out

• +150

 » 2 months ago, # |   +53 Good luck for Everyone
•  » » 2 months ago, # ^ |   +97 :(
•  » » » 2 months ago, # ^ |   +35 :)
•  » » » » 2 months ago, # ^ |   +15
 » 2 months ago, # |   +14 Finally a Div2 Edu Round :)
•  » » 2 months ago, # ^ |   +21 Sometimes the Codeforces community is crazy. Why is this normal comment being downvoted so many times? Can we stop this kind of "insane downvoting"?
•  » » » 2 months ago, # ^ |   +33 People just downvote / upvote like sheeps. If there is a single downvote they start downvoting it more. I dont care about Upvotes and Downvotes anymore :)
•  » » » » 2 months ago, # ^ |   +5 Fun fact, a single downvote doesn't show. You need at least 5 for it to show, which is meant to deter sheep-like behavior. Ig your post just didn't resonate with a bunch of people, no clue why.
•  » » » » » 2 months ago, # ^ |   -10 Yet another Fun Fact: his all down-votes are gone now :)
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 You're right ! Agree with you
 » 2 months ago, # | ← Rev. 3 →   0 Maybe I am gonna be a pupil this time! Hope a nice problems.
•  » » 2 months ago, # ^ |   0 NO way . Only solving 1 / 2 question can't make you green
•  » » » 2 months ago, # ^ |   +1 Same for you ;]
•  » » » » 2 months ago, # ^ |   0 I know :3
•  » » » 2 months ago, # ^ |   0 It can, if you solve them fast
•  » » » 2 months ago, # ^ |   +1 but eating some sus mushrooms can,
 » 2 months ago, # |   +24 I don't know why I like educational rounds so much.
•  » » 2 months ago, # ^ |   +33 I tend to do worse on educational rounds for some reason, probably because I have trouble with 'classical' problems. I think edu is very high quality, and I'm impressed how many good problems they can come up with in such a short time frame.
 » 2 months ago, # |   +31 hope for a good contest, not speedforces .
 » 2 months ago, # | ← Rev. 2 →   0 Good luck everyone! Удачи всем! Hemmäňize üstünlik!
 » 2 months ago, # |   +2 All the best Everyone!
 » 2 months ago, # |   +1 Good luck for Everyone
 » 2 months ago, # |   +4 Geez, they dont expect much out of the candidates, do they?
 » 2 months ago, # |   -29 Yet, Another speedforces round!
 » 2 months ago, # |   0 Hope to become BLUE at least today.
•  » » 2 months ago, # ^ |   0 +1
•  » » » 2 months ago, # ^ |   0 Good Luck !!!
 » 2 months ago, # |   0 Do we get solutions of these questions after contest is over anywhere??
•  » » 2 months ago, # ^ |   +1 Yeah! ...Editorial will be released after the end of contest where you can find the solutions to all the problems!
•  » » » 2 months ago, # ^ |   0 thankyou!
•  » » 2 months ago, # ^ |   0 Yes, Editorial will be released after the contest :) It will have hints and explanations to each problem, along with the implementation.
 » 2 months ago, # | ← Rev. 2 →   -30 It's annoying when you passed the given test and it fails on some other test case which you can't even see!!!
•  » » 2 months ago, # ^ |   +38 Is this a joke or what
•  » » » 2 months ago, # ^ |   -15 Well that depends on how good are you at CP T_T.
 » 2 months ago, # |   0 problem A is very easy but B I can't solve it XD!
•  » » 2 months ago, # ^ |   0 same here i unable to solve problem B
•  » » 2 months ago, # ^ |   0 same happened to me, but i used long long instead of int. Got accepted.
•  » » 2 months ago, # ^ |   0 Thats intended :)
 » 2 months ago, # |   +8 I'll die doing C
•  » » 2 months ago, # ^ |   0 I am already dead! :'
•  » » 2 months ago, # ^ |   0 US :)
 » 2 months ago, # |   +32 C was annoying but D was very great and nice
•  » » 2 months ago, # ^ |   0 I got C Idea in 30 minutes, then I spent 1:15 hours thinking of D but In vain.Could you give me a hint?
•  » » » 2 months ago, # ^ |   0 Spoilerfirst you have to know the number of different letters in every prefix there are at most 26 different response you will get
•  » » » » 2 months ago, # ^ |   +4 I've already calculated this during the contest, what is the next step?
•  » » » » » 2 months ago, # ^ | ← Rev. 4 →   0 for every index ask2(1,i-1)
•  » » » » » » 2 months ago, # ^ |   0 Wouldn't this exceed the limit of questions if the string is like this?abcd...xyzabc...xyzabc....xyzabc...xyz..... and so onThe generated string after the questions will be abc...xyz????????????.... and more '?' to n which will cause you to search for the 26 possibilities at each time of the n-26 letters.How did you overcome this problem?
•  » » » » » » » 2 months ago, # ^ |   +27 interactive = binary search
•  » » » » » » » » 2 months ago, # ^ |   0 I have used kind of similar approach but getting nlogn complexity that is around 9000 query of type 2 which is not allowed how you overcome that.160345223: My submissionThank you
•  » » » » » » » » » 2 months ago, # ^ |   0 I think he meant to binary search the 26 steps not the whole string
•  » » » » » » » » » 2 months ago, # ^ |   0 Just binary search on indices of already existing characters. (26). So take last index of each character, then your binary search will run with an upper bound of log(26)=4.7. so making (log(26)+1)*1000 == 5700 queries is enough. One extra query for checking if there is a non repeating character or not.
•  » » » » » » » » » 2 months ago, # ^ |   +4 Oh okay thanks I don't know why but I have a bad habit that I just think of approach and implement if it works okay if not then I can't think more about the problem. I will try to improve it.Once again thanks
•  » » 2 months ago, # ^ | ← Rev. 3 →   +32 C is not annoying if solve it the right way:1) Initially drop all 'b' from both strings – if resulting strings are not equal then answer is NO.2) In initial strings find all occurrences of 'a' – k-th occurrence in first string should be less or equal to k-th occurrence of 'a' in second string. And similar to 'c' but it should be more or equal.
•  » » » 2 months ago, # ^ |   0 this is exactly the idea i used
•  » » » 2 months ago, # ^ |   0 I did exactly the same.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +6 My solution for C has O(Nlog(N)) complexity and it gives tle but some O(N^2) are also passing.
•  » » » » 2 months ago, # ^ |   +3 I believe I can help you, I had the same problem on the last Div3 round. lower_bound(set.begin(), set.end(), sus_element) works in O(n) for some reason set.lower_bound(sus_element) works in O(log n)
•  » » » » » 2 months ago, # ^ |   0 From what I could tell the reason that lower_bound(set.begin(), set.end(), sus_element) works in O(n) is because std::lower_bound uses iterators to find each pivot. Added up, it takes O(n/2 + n/4 + n/8 + ...) = O(n) time. I think they explain it better
•  » » » » » 2 months ago, # ^ |   0 Oh it's very important I will remember it. Now it got AC with it.
•  » » » » » 2 months ago, # ^ |   0 Hello, thank you for the explaination. However, I did a similar idea and used set.lower_bound() and not std::lower_bound, but I TLE on subtask 2. May I know what is wrong with my code(https://codeforces.com/contest/1697/submission/160362579) ? Thank you.
•  » » » 2 months ago, # ^ | ← Rev. 4 →   0 can you explain more ....I solved it and got AC but my sol is not simple in implementation ....  Complexity: O(NlogN) my solution
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +1 Sure, the main idea is to consider operations as moving 'a' through 'b' to the right and moving 'c' through 'b' to the left.The logic of the first step is – we can't move 'a' through 'c' and vice versa. So we can initially check if the arrangement of a and c is correct.The second step – if there's a k-th occurrence of 'a' in first string that is righter than the k-th occurence of 'a' in the second string then we can't move that 'a' in the required position since we can't move 'a' to the left. Exactly same logic for 'c' and moving it to the right. If we see such occurrences then the answer is NO.If neither of 2 conditions above are true then answer is YES – it's because of the same logic from step 2 – we can move each 'a' and 'c' to the required position since we only need to move 'a' to the right and 'c' to the left and it's guaranteed from step 1 that 'a' and 'c' has the same arrangement as in the second string.
•  » » » » » 2 months ago, # ^ |   0 Very nice implementation idea altgifted I thought same but was not able to implement it correctly. Had to go through a tough implementation :)
 » 2 months ago, # |   +5 In normal Div.2 contests when I re-submit a problem that was previously accepted, I get penalty and the previous one gets skipped. But in this round it didn't happen when I re-submitted. Can someone tell me why?
•  » » 2 months ago, # ^ |   +18 Because it's ICPC mode
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +5 Does that mean the 2nd solution won't be considered? Sorry I'm not familiar with ICPC rules :(
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   +30 In ICPC mode contests all your accepted solutions will be judged, If for example you have submitted $k$ accepted submissions and the $i-th$ one gets accepted, you will get $(i - 1) × 10$ minutes penalties.
 » 2 months ago, # |   0 Is today's C related to : https://codeforces.com/contest/920/problem/C ? How to solve C? T_T
•  » » 2 months ago, # ^ |   +22 First, remove all occurrence of '$b$' and check if they are same. Second, find each occurrence of each non-'$b$' character in both $s$ and $t$. If it is a '$a$', it must appear in $s$ no later than in $t$. If it is a '$c$', it must appear in $s$ no earlier than in $t$.
•  » » » 2 months ago, # ^ |   0 What is the insight about deleting "b"'s?
•  » » » » 2 months ago, # ^ |   +5 because '$a$' and '$c$' can't swap, so deleting '$b$'s can check if their number and order match.
•  » » » » » 2 months ago, # ^ |   0 got this one, oh and b's could be simply removed from way either left or right, it's "proved by solution" I guess. Thank you!i_emerge16 Thanks!
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 It's more of a proof problem. I'm not sure tho. HintWhat do you notice with the number of $a$'s and $c$'s for each $s$ and $t$, while iterating from left to right?
•  » » » 2 months ago, # ^ |   0 can you pls explain your approach?
•  » » » » 2 months ago, # ^ |   0 S--->T Because a cannot be swapped for c, each char 'a' in s and t must have the same number of char 'c' on the left and right sides ( sequence wise for every a in s & t) Second, we can't change ba to ab, thus for each a in s and t, no of b in left of a in s <= no. of b in left of a in t (sequence wise for every a in s & t). Finally, because we can't exchange cb to bc, thus for each b in s and t , no of c in left of b in s <= no. of c in left of b in t (sequence wise for every b in s & t).
•  » » » » 2 months ago, # ^ | ← Rev. 4 →   0 It's essentially the same with Aging1986's solution. But, I didn't think of deleting the $b$'s. Observe that $a$'s can only move to the right, while $c$'s can only move to the left. This means that when iterating from left to right, the number of $a$'s in $s$ must always be greater than or equal to the number of $a$'s in $t$. Similarly, the number of $c$'s in $t$ must always be greater than or equal to the number of $c$'s in $s$. Then, also notice that $a$'s and $c$'s cannot swap. Meaning, in between $c$'s, if they exist, there will always be the same number of $a$'s. Similarly, in between $a$'s, if they exist, there will always be the same number of $c$'s. That is why Aging1986 "deleted the $b$'s". I had a different way of checking that. Every time both the numbers of $a$'s or $c$'s, in $s$ and $t$, increases, I must check if the previous numbers of $c$'s or the previous numbers of $a$'s, respectively, is the same.
•  » » 2 months ago, # ^ | ← Rev. 5 →   0 I did it with prefix sum of "a", "b" and "c", and with Upper bound. It works very well. 160360256 Just kinda sad I forgot if pos from (pos = upper_bound) is out of bounds, to print "NO\n" immediately, so I resubmited, and it got accepted 1 minute after the contest ended.. :( But I am glad anyway, because I learned something new. :D
 » 2 months ago, # |   +2 Can anyone help with C?
•  » » 2 months ago, # ^ |   +3 There seem to be more solutions to C. I'll explain mine.First, we need to make a few observations: both strings s and t should have equal amounts of 'a', 'b', and 'c' 'c' cannot be moved towards right in string s (So, each 'c' in s should be present towards the right of its counterpart in string t) 'a' cannot be moved towards left in string s (So, each 'a' in s should be present towards the left of its counterpart in string t) by doing the given operations. Let's start with the observation#2:To move a 'c' towards the left from index i to j(j < i), the range [j, i-1] should have all 'b's. Try moving each 'c' in s to its correct position in t. If we cannot move a 'c', we cannot convert s to t.Now, all 'c's should be in their correct positions(if possible)Similarly, with the observation#3:To move a 'a' towards the right from index j to i(j < i), the range [j+1, i] should have all 'c's. Try moving each 'a' in s to its correct position in t. If we cannot move a 'a', we cannot convert s to t.Now all 'a's should be in their correct positions(if possible)Since all 'a's and 'c's are in their correct positions, now we just need to check if all b's are there in their correct positions and determine the answer.Implementation:To check if a range contains all b's and make point updates while moving a character from one index i to j(the move is a direct swap of s[i] and s[j] and not actual swaps between adjacent characters to reach the destination), we can use Segment Tree with range query and point updates.
•  » » 2 months ago, # ^ |   +1 hope my implementation using stack give you some hint :-160349549
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Can you once check what's wrong with this implementation of mine: here It's failing on 2164th test case in pretest 2.
•  » » » » 2 months ago, # ^ |   0 before pushing (a,b)into stack we must check if any pair (b,a),(b,c),(c,b)is present on top then return no otherwise if top contains (a,b) then we can push(a,b). similarly for (b,c) to push(b,c)into the stack we must check (c,b),(a,b),(b,a)if any of these pair present then return no else if((b,c) is present on top then we can push (b,c) pair accepted code of yours:->160388847
•  » » » » » 2 months ago, # ^ |   0 yeah, got it! Thanks a lot :)
 » 2 months ago, # | ← Rev. 2 →   -48 Worst round since last Month.Upd. Change my mind:
 » 2 months ago, # |   +3 Please explain the solution to the problem D; Thanks :)
•  » » 2 months ago, # ^ |   +12 Double binary search. First binary search to find the point where a new alphabet first shows up in the string (counting from the left), and then, we iterate through the string from left to right. For each character of the string, we save the last occurrence of the letter, and to determine the unknown character, we do a binary search on the array of indexes of last occurrences to find the index at which the unknown character does not contribute to the number of distinct characters. This should yield a $O(26logn+nlog26)$
•  » » 2 months ago, # ^ | ← Rev. 3 →   +4 We are going to use binary search.Imagine you are trying to figure out index ith, and imagine you already know all characters from 0th to (i — 1)th.you can add all the right most index of each character that you have found in an index array, this index size is at most 26. You are going to binary search on this index.let say you are considering index jth before ith. if from j to i — 1, the index at i already appears, then you have the same count from j to i — 1, and j to i, bc ith doesnt add anything new. So you can binary search the right most position where this is true, then you can find an index j that is the same with i. so each binary search check, you can check the count from mid to i — 1 and mid to i, mid to i — 1 can be updated after every ith, so it's free. If you can't find this then you can use the first query.the total used is at max 6 * 10, you only use 5 times in the binary search, at only use the first type when there's a new character.
•  » » 2 months ago, # ^ |   +26 Shortly, you restore the characters of s from left to right. The first character is restored by query "? 1 1". For each of the next characters, let's ask if this character is new (by query "? 2 1 i"). If it's new, ask "? 1 i"; otherwise, find the previous occurrence of the i-th character with binary search.To run only 5 queries of type 2 in binary search, you can see that we are interested in segments of type $[last_c, i]$, where $last_c$ is the last occurrence of some character on the prefix we know.
•  » » 2 months ago, # ^ |   0 Keep track of known letters and their last positions. Build the string up from the front by querying the entire string up to that position to find out if its a new letter (if it is then use query type 1 to find out what it is) otherwise do a binary search with the array of last positions to work out which letter it is.
 » 2 months ago, # |   -6 D << C
•  » » 2 months ago, # ^ |   0 will you please tell me why this code fails? 160354394
•  » » » 2 months ago, # ^ |   0 your solution makes mpre than 6000 queries of the second type
 » 2 months ago, # |   +3 E was a nice question with 2 parts to it. How to solve F though?
•  » » 2 months ago, # ^ |   0 How to solve E?
•  » » » 2 months ago, # ^ |   +11 Connect a line between 2 points if you can possibly colour them as the same colour. Notice that this will result in a graph of disconnected cliques. The clique can either be colored with 1 colour or different colours for each point. Then, we can use DP to colour them.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Will the connected componnets be atmost of size 3? My code gives WA on tc 4 can you tell me why Code...
•  » » » » » 2 months ago, # ^ |   +8 Test 4 has a component of size 4 (a square which has its sides parallel to lines $y=x$ and $y=-x$).
•  » » » » » » 2 months ago, # ^ |   0 Ah alright thanks!
•  » » » » » 2 months ago, # ^ |   0 At least put your code in spoiler or something :|
•  » » » » 2 months ago, # ^ |   0 thx! I catched my error
•  » » 2 months ago, # ^ |   +21 F is two sat . You can make some variable : (a[i]<=x) is true or false , (a[i]>=x) is true or false.
•  » » » 2 months ago, # ^ |   0 Oh wow, I didn't think of it that way.
•  » » » 2 months ago, # ^ |   0 I get that you could use $a_i <= x - 1$ or $a_i >= x + 1$ to deal with the first operation, but how do you go about the second and third operation?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +18 $a_i+a_j \ge x$ iff $\forall y$, either $a_i \ge y+1$ or $a_j \ge x-y$ should hold.
•  » » » » » 2 months ago, # ^ |   0 Ahhhh, that makes sense. Thanks
 » 2 months ago, # |   0 How to solve F?
 » 2 months ago, # |   -90 Since D requires stupid observations and E,F are unsolveable, todays edu was like speedforces.Usual edu rounds where mostly implementation based problems, I liked that.
•  » » 2 months ago, # ^ |   0 What's the observation for D ?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +9 :v No observation at all! Find the all position such that $cnt(1, i - 1)$ < $cnt(1, i)$ and do query of type $1$ for that position $i$. After that, do a for loop from $1$ to $n$ and take all the last appearance of characters that occur before $i$ and binary search on it.
•  » » 2 months ago, # ^ |   0 A and B make this round somehow "speedforces". But D has a clean solution and I think it's a good problem. I have no idea whether C has a clean (and PROVED) solution because my solution for C was terrible.
 » 2 months ago, # | ← Rev. 2 →   0 How to solve D? was D binary search on last unique characters encountered so far?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 That is true, the total number of 2 Query will be less than log(26)*1000, Do you search the last 26 characters[a-z] instead of all the previous characters?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 For each character ch encountered, I stored its latest index, then binary searched on that vector indices by quering them. But I'm going wrong somewhere. the vector kind of vector> where v[i].second is unique. and v[i].first is latest index where v[i].second appears
•  » » » » 2 months ago, # ^ |   0 you can post your submission
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 No worries, I had done some implementation mistake.fixed it. Here is AC submission 160370256
 » 2 months ago, # |   +13 What is test case 10 of E?
 » 2 months ago, # | ← Rev. 2 →   -58 A and B are TOO EASY as Div.2 AB.But for Div.2 level contests you don't expect this kind of easy problems so you will spend some time on thinking again about A and B before submitting them, but this will cause your ranking become low and it is VERY disturbing.
•  » » 2 months ago, # ^ | ← Rev. 3 →   -36 Never downvote a post due to the reason "there are already many downvotes and I would like to add more". If you downvote a post you should really have a "good reason" otherwise it's only making this community crazy and unfriendly.
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 I think this is more about just a lack of self confidence in your skill or a lack of contest experience to notice the problem is actually easy or a trick question imo. EDIT: I removed the joke.
•  » » » » 2 months ago, # ^ |   0 I somehow agree with your serious point but your first two sentences are a little bit offensive in my opinion.
•  » » » » » 2 months ago, # ^ |   0 Hmm, it was supposed to be a joke and I didn't mean to encourage downvoting, but I suppose I could remove that bit if you find it offensive.
•  » » » » » » 2 months ago, # ^ |   +5 Thanks. Maybe I shouldn't care about downvotes at all.
 » 2 months ago, # |   0 What's wrong with my sol of problem D. It's showing WA on tc 9 160357208
•  » » 2 months ago, # ^ |   0 too many queries leads to wa
 » 2 months ago, # |   0 Is there a way to solve D without bsearching at every iteration? Feels like there should be an easier way to do it.
•  » » 2 months ago, # ^ |   +4 I guess no, as the query limit is an obvious indication to do a binary search.
•  » » » 2 months ago, # ^ |   +8 How do you deduce this from query limit that binary search is to be used?
•  » » » » 2 months ago, # ^ |   0 1000log(26) is roughly 5k
 » 2 months ago, # |   +5 Someone hack my C, https://codeforces.com/contest/1697/submission/160337496, I think it should give tle for large test case
 » 2 months ago, # | ← Rev. 2 →   0 This was a nice round, but what I don't understand completely is that my solution of Problem B passes in C++, but does not pass in Python (due to Time Limit). I think that in educational rounds it should not matter which language is used if the idea is correct. But, yes, probably, it is too difficult to check it for multiple languages.
•  » » 2 months ago, # ^ |   0 Probably due to slow I/O in python. It's better to load / write data at once.
•  » » » 2 months ago, # ^ |   0 Thank you! Looking at the solutions, I realised that my solution makes some unnecessary work, and that just by removing those things, it would have passed.
•  » » 2 months ago, # ^ |   0 My solution passed in Python but TLE'd in PyPy.
•  » » 2 months ago, # ^ |   0 same bro, even I submitted in Python and got TLE
 » 2 months ago, # |   0 What's the testcase 8 in problem D :(
•  » » 2 months ago, # ^ |   0 Try testing your code with abca, abcad, abcadd.
 » 2 months ago, # |   +11 Problem C & D, Easy to come up with the solution but frustrating to implement it !!!!!
 » 2 months ago, # | ← Rev. 3 →   0 solved
 » 2 months ago, # |   +1 is problem D inspired from this ?
 » 2 months ago, # |   0 When and where can I get the solutions?
•  » » 2 months ago, # ^ |   0 Just wait until the announcement post gets updated. It should have a hyperlink "Editorial" by then.
 » 2 months ago, # |   0 Is there an option to see rank among rated participants?
 » 2 months ago, # | ← Rev. 5 →   0 [deleted]
 » 2 months ago, # |   -54 I don't really see the benefit to require 6000 operations in D instead of 27000, from an algorithmic point of view it seems a bit weird to ask for a constant factor <10, as for the quality of the problem the answer is obviously binsearch, so it adds no more thinking but only risks of missing it, and potentially more time and WA spent for the same problem. That will either prevent you from ACing it or spending more time on more interesting problems.
•  » » 2 months ago, # ^ |   +47 With 27000, you don't need binary search at all.
•  » » » 2 months ago, # ^ |   -38 That's what I'm saying, moving the constraint to 6000 only "artificially" adds an obvious binsearch which is a bit annoying to code
•  » » » » 2 months ago, # ^ |   +46 This would make the problem too easy, perhaps easier than C, and the gap between D and E would be enormous.
•  » » » » » 2 months ago, # ^ |   -40 Well I think we should not balance problemsets by making implementation artificially harder but rather by finding problems that are harder to solve, but that's only my opinion. Plus I'm kinda bored with "obvious binsearch interactive problems" tbh
•  » » » » » » 2 months ago, # ^ |   +6 But if the interactive problem is not a typical binary search, I feel like it tends to be very adhoc/implementation heavy
•  » » 2 months ago, # ^ | ← Rev. 4 →   -19 (misunderstood the point, so deleted)
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +27 binary search is actually "THE algorithm" here
•  » » » 2 months ago, # ^ |   +26 How is binary search not an algorithm?
•  » » » » 2 months ago, # ^ |   -6 I never say "binary search is not an algorithm".
•  » » » » 2 months ago, # ^ |   -8 I assume the solution is binary search and I would like to see how to optimize a naive binary search to make it fit in 6000 (or at least pay attention to some implementation details to avoid exceeding 6000). My "naive" binary search didn't pass.
•  » » » » » 2 months ago, # ^ |   0 I thought the crux of this task seems to design a algorithm with query complexity $O(n \log |\Sigma|)$ instead of $O(n \log n)$, and the query limit makes great sense if so.
•  » » » » » 2 months ago, # ^ |   0 You only need to run your binary search among the values $last_c$ as $l$, where $last_c$ is the last occurrence of some character you already have met, so there are only $26$ values to choose from.
•  » » » » » » 2 months ago, # ^ |   0 That makes a lot of sense!
 » 2 months ago, # |   0 Can anyone explain for Problem B ( PROMO ) , what happens if x == y? I am confused as if x == y then we need to purchase x+1 items as one purchase will be done and rest items sum will be answer. Can anyone clarify it.
•  » » 2 months ago, # ^ |   0 Think of it this way: you pay for the x most expensive items first, and then because of the offer, the store refunds you for the first y cheapest items of your purchase. because x = y, so you don't need to spend a penny after the refund.
 » 2 months ago, # | ← Rev. 4 →   +6 Can C be solved by using this idea?First I check if all frequency of some letters are not the same, then it's impossible to form $t$Then, I try to move all c to the front. Assume that : In original string $s$, we have c at position $c_1 < c_2 < ... < c_k$ In final string $t$, we have c at position $c'_1 < c'_2, ... < c'_k$ My claim : It's optimal to move c so that $c_i$ moved to $c'_i$I just need to check that for each $i$ : value of $c_i > c'_i$ (because we can only move c to the left) there are no a between $c'_i$ to $c_i$ (since a cannot be swapped with c) Then I do the same for a, but I try to move a to the back. I got WA but not sure what case breaks itMy implementation : 160335858
•  » » 2 months ago, # ^ |   0 I have the same decision and it also failes, I do not Understand why. https://codeforces.com/contest/1697/my
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Kind of easier C implementation codeint cnt[3][2]{}; for (int i = 0; i < n; ++i) ++cnt[s[i] - 'a'][0]; for (int i = 0; i < n; ++i) ++cnt[t[i] - 'a'][1]; for (int i = 0; i < 3; ++i) if (cnt[i][0] != cnt[i][1]) return no(); fill_n(&cnt[0][0], 6, 0); for (int i = 0; i < n; ++i) { cnt[s[i] - 'a'][0] ++; cnt[t[i] - 'a'][1] ++; if (s[i] == 'c' and cnt[0][0] != cnt[0][1]) return no(); if (s[i] == 'a' and cnt[2][0] != cnt[2][1]) return no(); if (cnt[0][0] < cnt[0][1]) return no(); if (cnt[2][0] > cnt[2][1]) return no(); if (cnt[2][0] < cnt[2][1] and cnt[1][0] <= cnt[1][1]) return no(); } yes(); 
•  » » 2 months ago, # ^ |   +3 I did not read your code but did the same. When you move 'c' don't forget to do the swap. Example : 4 abbc bcab My code https://codeforces.com/contest/1697/submission/160335317
•  » » » 2 months ago, # ^ |   +1 Oh ya you're right. I forgot to swap it. Thsnks
•  » » 2 months ago, # ^ |   -18 same, make the round unrated
•  » » 2 months ago, # ^ | ← Rev. 2 →   +30 This is how interactive problems work — not only on CF, but in official ICPC contests as well. There is no separate verdict for exceeding the number of queries (what should it be? RE, TL, something new?), so the WA verdict is used for it almost everywhere.Note that the phrasing in the problem is "you MAY receive some other verdict", not "you WILL receive". This is due to the fact that, in interactive problems, two separate programs are used to judge your submission, and in some occasions, their verdicts can be different (for example, the interactor says that you should get WA for sending too many queries, but then your solution crashes or spends too much time, so it's eligible for WA/RE/TL). That's why you should terminate your program immediately after receiving the response "your query is incorrect", which you don't do.
•  » » » 2 months ago, # ^ |   -6 please quote fully it says "you may receive some other verdict INSTEAD of wrong answer". It may be possible that my English is just bad but to me this statement means that you can receive any verdict on exceeding queries but not a WA.
•  » » » » 2 months ago, # ^ |   +13 You can receive any verdict, period. You may receive something instead of WA, or you may receive WA.
•  » » » » » 2 months ago, # ^ |   0 The problem did not say "or you may receive wa" or meant so. If it did really mean so, why did statement include "instead of wa"? It was unnecessary.
•  » » » » 2 months ago, # ^ |   0 It says you MAY receive any verdict instead or wrong answer. As BledDest said, it does not guarantee that you will not receive WA
•  » » » » » 2 months ago, # ^ |   +3 It was so easy to be misunderstood. Your viewpoint is true, some people will understand the problem in the way you did, but many other won't.
•  » » » 2 months ago, # ^ |   0 Thanks for the informations. However, such things are beyond newbie's level for myself (and some other contestants too, I undertood it after reading your comment though). I mean yes those might be compulsive for highly-rated contestants. But contests are for everyone, I don't think every div2-D-solver should have already taken those into account, some of them might just take contests for fun and have a passion for problem-solving for instance. With all being said, I acknowledged that it was my fault for not checking the number of queries, and furtherly understood how computers work to a certain extent (I'm really thankful and appreciate those informations), but the contest organizer could have done better not to confuse a lot contestants, including myself (I had suffered a lot of emotional damage debuging my code for that problem ngl xD).That was just my opinion, also English is not my mother tongue langague so please excuse me for any grammar or spelling error.
•  » » » » 2 months ago, # ^ |   0 Usually it's best just to do what the problem statement says you should do. The problem says that you should terminate your program after getting a $0$ in response to the query, or otherwise some strange things may happen — so you wouldn't have experienced this issue if you handled this case in your solution.
•  » » » » » 2 months ago, # ^ |   0 The word "should" might be used for illustration of meaning "the program will be like this like that" or something similar (I have experienced that while doing some cf problems ngl). Also it didn't say those verdicts are "strange things". As I have already said, contests are for everyone, not only for the experienced. So why wouldn't they make everything clear so that everyone can understand? Mistakes are inevitable, but they should be acknowledged. I am just telling my opinion, no offence here.
•  » » » » » » 2 months ago, # ^ |   0 Sometimes it's impossible to make everything clear for everyone, unfortunately. I used this exact wording in one of my previous interactive problems, and there were no issues about that. Maybe I'll change the wording for future interactive problems, considering the feedback from this contest.
•  » » » » » » » 2 months ago, # ^ |   -16 I believe that many other contestants would have had the same problem so I'm glad that you will consider it, thanks a lot.
•  » » » » » 2 months ago, # ^ |   +9 By the way, just for clarification, immediately terminating after getting response '0' will also lead to WA verdict, won't it?
•  » » » » » » 2 months ago, # ^ |   +12 just do vector a;a[784]=784; after getting response '0' and you will get Runtime Error instead of WA )
•  » » » » » » » 2 months ago, # ^ |   +48 What a strange way to write assert(false)
•  » » » » » » » 2 months ago, # ^ |   0 Ok ig the final issue is wrong answer and too many queries are all merged in one verdict, so as long as there are no different responses, can't really differ between them!
•  » » 2 months ago, # ^ |   0 I didn't see you check 0 as return value, so the verdict will be WA.
•  » » » 2 months ago, # ^ |   0 I'm new to competitive progamming, so I haven't gotten what you mean yet. Please further explain it. Thanks a lot.
•  » » 2 months ago, # ^ |   0 yes exactly this statement is the reason why I spent ~1.5 hrs thinking that either my logic or my implementation was wrong. It literally says that you will get "Some other verdict instead of Wrong answer"
•  » » 2 months ago, # ^ | ← Rev. 4 →   0 I too was confused by the WA I got on submission just before contest ended. Now I realize my code just missed a single variable increment which I forgot to write(facepalm) making my program flooded with query 1 AC submission after contest.However, it is solely my stupidity and I greatly enjoyed the problem!
•  » » 2 months ago, # ^ |   0 I don't understand what you mean — this simply means that if your program is wrong you might get any verdict. You don't need to check 0 in case your program is correct
•  » » 2 months ago, # ^ |   0 Better count the queries in code, and put an assert statement in end to get RE instead of WA
 » 2 months ago, # |   0 interactives -_-
 » 2 months ago, # |   0 how to do c?
•  » » 2 months ago, # ^ |   0 S--->T Because a cannot be swapped for c, each char 'a' in s and t must have the same number of char 'c' on the left and right sides ( sequence wise for every a in s & t) Second, we can't change ba to ab, thus for each a in s and t, no of b in left of a in s <= no. of b in left of a in t (sequence wise for every a in s & t). Finally, because we can't exchange cb to bc, thus for each b in s and t , no of c in left of b in s <= no. of c in left of b in t (sequence wise for every b in s & t).
 » 2 months ago, # | ← Rev. 2 →   0 Can someone please explain me why my solution 160333877 gives TLE? From the code the complexity seems like nlogn. Thanks
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Strange, I have a similar implementation and it runs within 2s. https://codeforces.com/contest/1697/submission/160368077
•  » » 2 months ago, # ^ | ← Rev. 2 →   +8 I believe, it's because you're accessing st[3] which is out of bounds.
•  » » » 2 months ago, # ^ |   +5 Arghhhh! How did i miss this?! This contest was a nightmare for me. Thanks for taking the time to figure it out.
 » 2 months ago, # | ← Rev. 4 →   0 .
•  » » 2 months ago, # ^ |   0 Doesn't Java use dual pivot quick sort for primitive objects? It runs in $O(n^2)$ in worst case.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 .
•  » » » » 2 months ago, # ^ |   +8 I think your solution runs in $O(nqlogn)$ which is too much lol.
•  » » 2 months ago, # ^ |   0 Do not use system io for io-intensive problems. Search for fast io
•  » » » 2 months ago, # ^ | ← Rev. 2 →   -8 .
•  » » » » 2 months ago, # ^ |   0 For all queries.
 » 2 months ago, # |   +4 Wasted 30 mins on C because of a single "break". How careless I am! :(Anyway,the problems are fantastic!
 » 2 months ago, # | ← Rev. 2 →   +14 I got the solution idea for problem D from the constraints. First, we can use the first type of query at most 26 times. That indicates that we will use it to know the indices of the first appearance of each character. Second, we can use the second type of query at most 6000 times. After trying some calculations, I found that the nearest calculation to 6000 is 1000 * log_2(26) which is approximately equal to 5000 or smth like that. So, then I came up with solving it using binary search. Honestly, I think this problem is very interesting!
•  » » 2 months ago, # ^ |   +1 yes, I too came up with approach but unable to implement it.
 » 2 months ago, # | ← Rev. 2 →   +4 I kept getting WA 7 in problem D so I though that i am not exceeding the number of allowed queries. (because the statement mentioned that I should get some verdict other than WA in this case)so I was looking for a bug in my code instead of my idea I also added assert to the response to make sure ites not 0 as the question suggested which means not breaking the rolesand after the contest finished I found out that its wrong because it exceeded the allowed queries -_-
•  » » 2 months ago, # ^ |   0 Same, what a pity.
 » 2 months ago, # |   0 import java.util.*; public class PalinInd { public static void main(String args[]) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); long q=sc.nextInt(); long arr[]=new long[n+1]; arr[0]=Integer.MIN_VALUE; for(int i=1;i<=n;i++) arr[i]=sc.nextInt(); int arr1[]=new int[n+1]; arr1[0]=0; int p=1; long s=0; Arrays.sort(arr); for(int i=1;i<=n;i++) { // s=s+arr[i]; arr1[i]+=arr1[i-1]+arr[i]; //arr1[p++]=s; } for(int j=1;j<=q;j++) { int x=sc.nextInt(); int y=sc.nextInt(); int val=n-x; System.out.println((arr1[val+y])-(arr1[val])); } }} why my code give tle in 3rd test case in java??please answer
•  » » 2 months ago, # ^ |   0 Arrays.sort is quick sort that is O(n^2) in worse case Scanner is slow. I used: new BufferedReader(new InputStreamReader(System.in))
•  » » » 7 weeks ago, # ^ |   0 why it works in other questions??
 » 2 months ago, # |   0 NEED A counter TESTCASE:https://codeforces.com/contest/1697/submission/160352564
 » 2 months ago, # |   0 A to D are good. Problem E seems interesting, will give a try later.
 » 2 months ago, # | ← Rev. 2 →   0 It seems like the observation of E is easier than D，but I dont have enough time..
 » 2 months ago, # |   0 What's the different between F and k-sat?
 » 2 months ago, # | ← Rev. 3 →   0 my solution to b part ishttps://codeforces.com/submissions/dsanurag520 (it is in python)But my solution is jumbled. Does anyone know why this is happening?
 » 2 months ago, # |   +7 Spoilerinteractive = binary search
•  » » 2 months ago, # ^ | ← Rev. 2 →   +8 or something related to binary bits if constraints contains 32 as limit of queries
 » 2 months ago, # |   0 https://codeforces.com/contest/1697/submission/160338205 This is my submission for problem C. It fails on test case 407 of main test 2, which isn't visible (only the first 110 lines are visible on the page). Could anyone tell what test this solution fails on?
•  » » 2 months ago, # ^ |   0 14baabcbba
•  » » » 2 months ago, # ^ |   0 It give the answer as "NO" only.
•  » » » » 2 months ago, # ^ |   0 Gives YES in my ide
•  » » » » » 2 months ago, # ^ |   0 The number of 'a' and 'c' are different in the string 's' and 't', did you make a typo in the test case?
 » 2 months ago, # |   0 B task is almost similar to this one
 » 2 months ago, # |   +22 I love getting rank 3000+ because i solved D and i was unable to solve C, and i am getting passed by people who solved C with O(n^2), feels great and fair :)
•  » » 2 months ago, # ^ |   0 You can always hack those who passed with n^2
•  » » » 2 months ago, # ^ |   +7 I tried hacking one and it goes up to 1.9s but it doesn't pass 2sec (i don't think there can be a more optimal hack) C++ is way too fast and O(n^2) solutions pass the time limit. Honestly, i believe that the TL for this problem is just way too big since optimal solutions in C++ pass in about 15ms.
•  » » » » 2 months ago, # ^ |   0 My C just got hacked
•  » » » » 2 months ago, # ^ |   +6 Maybe limits for such problems should be reduced to 1.5s
•  » » » » 2 months ago, # ^ |   0 Your hacks were not good enough. You were attempting 10 tests of size N = 10^4. 1 test of size N = 10^5 would have crashed an N^2 solution. Not even C++ can handle ~ 10^10 operations in 2 seconds.
•  » » » » » 2 months ago, # ^ |   0 I tried 2 different hacks, the last one (the one you describe) was a curiosity hack because I wanted to see what time difference it would make if I dropped the operations down to 10^4 and increased the number of tests. On my first hacking attempt, I tried the hack you describe — 1 test of size N = 10^5, and yet this didn't crash an N^2 solution. The link to the submission I tried to hack is 160337496 and it is still not hacked.
•  » » » » » » 2 months ago, # ^ |   0 Apologies. I was only able to find the smaller attempted hacks. You're right though; somewhat incredibly it passes. I'm indignant on your behalf as it doesn't deserve to pass, and also kind of in awe at C++.
•  » » » » » » » 2 months ago, # ^ |   0 No worries, indeed it's insane how fast C++ is, in this submission in particular it loops around ~2.5*10^9 times, and finishes in under 2 seconds.
•  » » 2 months ago, # ^ |   0 Educational Rounds always weight each problem equally so solving F only and solving A only can have similar rankings. In a previous Education Round I solved A-D but then C got FST due to a stupid long long overflow and then I dropped to my lowest rating :).
 » 2 months ago, # |   0 Would like to see a great solution for C. My solution requires complicated proofs and cumbersome implementations. Not sure whether I was in a hard and stupid direction again.
•  » » 2 months ago, # ^ |   0 The simple solutions of C are based on two observations: the subseq of 'a's and 'c'c in both strings must be same. And the positions of the 'a's (and 'c's) must be so that they can be moved in the desired direction. That makes it possible to implement it with only simple loops.example 160322407
•  » » 2 months ago, # ^ |   0 Let's assume that two characters did not match when passing through C and T. We have two options when it can be fixed. 1. s[i] = 'a' and t[i] = 'b'. Then we need to find the next b and swap it with s[i]. This can be done only when between this symbol b and our s[i] all characters are a. 2. s[i] = 'b' and t[i] = 'c', etc., only instead of a, b — b, c. All this can be quickly implemented, for example, by creating a set of indexes for each letter and using upper_bound to recognize the next letter. If anything, English is not my native language, I write through Yandex translator. My code (on c++): https://codeforces.com/contest/1697/submission/160320598
 » 2 months ago, # |   0 Anyone please tell me what is wrong with in my submission for C. It is giving WA on test 2. I can't even see that case
 » 2 months ago, # |   +32 same question as of C in leetcode https://leetcode.com/problems/swap-adjacent-in-lr-string/
•  » » 2 months ago, # ^ |   +1 Lol. Roles got reversed.
•  » » 2 months ago, # ^ |   +5 Last Atcoder contest has the famous leetcode problem: construct binary tree from preorder and inorder traversal.
 » 2 months ago, # |   +7 the guy's solution is weird 160366565It seems to be written like this on purpose and then hacked by others.
•  » » 2 months ago, # ^ |   0 pure genius
 » 2 months ago, # |   0 For problem B, I used Arrays.sort() and got TLE but after only changing code to work with Collections.sort() it passed. Why is this?
•  » » 2 months ago, # ^ | ← Rev. 3 →   0
 » 2 months ago, # |   0 This implementation of mine is failing on 2164th case of test case 2. Can someone check what's wrong? Submission link
•  » » 2 months ago, # ^ |   0 hi brother...mine is failing on 1180th case...close enough!
 » 2 months ago, # | ← Rev. 4 →   0 good contest
 » 2 months ago, # |   0 I suspect a problem with problem B. Promo I made a very fast O(NlogN) solution using Java, and I got "TLE on test case 3". Since I knew for a fact it was fast enough, I wrote the exact same code logic using C++. It passed. I think the problem should have a second or 2 more, for non C++ users. Did anyone else encounter this problem?
•  » » 2 months ago, # ^ |   0 I have used very fast algorithms in B, merge sort and then individual operations, but it was showing runtime error!
•  » » 2 months ago, # ^ |   0 Same here. After contest I tried with Arraylist and used Collections.sort method which eventually passed.
•  » » 2 months ago, # ^ |   0 Arrays.sort in Java uses quick-sort for primitives (with worst case O(n*n)) And merge-sort for wrapper objects. Instead of int[], if Integer[]` is used, it passes.Check this blog to understand more.
•  » » » 2 months ago, # ^ |   0 wow, this is extremely helpful, tysm! I never knew this — somehow I have solved many NlogN problems where N>=100k without knowing this haha.
 » 2 months ago, # | ← Rev. 2 →   0 Could anyone please check where my code fails? 160297431 Its really annoying to get weak pretests. Coz of this my initial rank was 2k and now it is 8k. Had solved C in 14 mins :facepalm: :lolisad:
•  » » 2 months ago, # ^ |   0 Your complexity seems to be $O(n^2)$, so it is hacked because of TLE.
 » 2 months ago, # |   0 Completely bricked C. Bye-bye rating :(
 » 2 months ago, # |   0 Hello, I found in the hacks that it appears as though a solution without prefix sums had passed the pretests on problem B (and then painfully got hacked). Is this intended, or did noone expect this passing the pretests? The submission of interest is as follows: 160341801
•  » » 2 months ago, # ^ |   0 difference between x and y could be 2*(10^5), and number of operations could be 2*(10^5). So, yeah prefix sum is expected solution.
•  » » » 2 months ago, # ^ |   0 Got TLE even with prefix sum Painaverage python user
 » 2 months ago, # |   0 Could someone say me where my 160349731 failed for problem C. I collected all those places where there is a mistake in string. They should be even in number because there if a letter could be corrected by swapping, then the other letter in pair of it should also be in wrong position. Now going from smallest index to largest index (in the collected indexes). Suppose if 2nd index letter is 'b' and 1st is 'a' without any c between them (I calculated it by prefix sum difference between these 2 positions is 0) then I'll swap them and remove those two indexes from my que. Similarly for c and b pair. Note: if 2nd element in que is 'a' then you can't swap element in 1st position to correct place.
 » 2 months ago, # |   +6 Often struggle with constructive algorithm problems in div2 C. Any suggestion for improving in this category will be appreciated.
 » 2 months ago, # | ← Rev. 2 →   +3 I have somewhat different idea for C, Some observations we can make:1)In string s, if we have a 'c' at some position,then characters to left of it always remain left and characters to right of it always remain right.Similarly in string t, if we have 'a' at some position.2)From 1 we can immediately say that if there is index i such that s[i]='c' & t[i]='a' ,then answer never exists.3)strings should be anagram of each otherNow suppose that i is first index where a 'c'occurs in string s and j is first index where 'a' occurs in second string,and since i!=j(2nd condition) ,wlog suppose i>j ,then we can use first i-1 characters of s to match first j characters of t,this can easily checked if count a,b,c in s till i-1 is greater or equal to count of a,b,c in t till j,now we reduce frequency count of a,b,c in string s. This works because till i-1 we have only 'a' and 'b' in s and since they can cross each other i would be able to achieve any configuration of 'a'and 'b' to match first j characters of t.Now we move to next 'a' in t(because i>j) and disregard first j characters of both strings For example:bcaabababc cbbababaacwe start from left i=2 and j=4 count of a,b,c in s=0,1,1 till i and count of a,b,c in t=0,2,1 till j-1 and count in t is greater or equal we move to next 'c'(because i
 » 2 months ago, # |   +19 When will the rating change?
•  » » 2 months ago, # ^ |   -6 How to check whether System testing is done or not?
•  » » » 2 months ago, # ^ |   +12 Just open your in-contest submission and see 'Sent' and 'Judged' time If they are 12-15 hrs apart then system testing is done else they are not.
•  » » 2 months ago, # ^ |   0 Edu round take 24 hours after contest.
•  » » » 2 months ago, # ^ |   0 Thank you very much! ❤️
 » 2 months ago, # |   0 When will Editorial out?
 » 2 months ago, # |   0 In problem D , (Guess the string) , while applying binary search how are you deciding that you have to go to left or right. Let's say: distinct characters(mid...i) == distinct characters(mid...i-1). Then we are sure that Str[i] = Str[mid]; Otherwise , you have to go left. (How can you say that you have to go left? ) Can anyone please explain it?
•  » » 2 months ago, # ^ |   +3 You have to create a new temporary array where you store the index of last occurrence of all characters that you have encountered so far and then binary search on that array. if distinct characters(tempArr[mid],i)==(tempArr.size()-mid+1) then move left else you have find a potential character save it into variable (say fans) and move right in tempArray. Finally do ans+=fans;LINK->160405246
•  » » » 2 months ago, # ^ |   0 Thanks for helping. I got it now.
 » 2 months ago, # |   +13 waiting for editorial.....
 » 2 months ago, # |   0 The judging for B seems to be inconsistent for python. I have gotten TLE while similar solutions have gotten AC :(
•  » » 2 months ago, # ^ |   0 I totally agree! My python solution was initially accepted, and then ended up being successfully hacked, due to TLE. And I am guessing that the only part of my code that was producing the TLE result — which I think is probably similar to what happened on your end, from looking at your code — is using python's built-in sort function. It seems very inappropriate that their judge function produces that result on this problem.
 » 2 months ago, # |   0 https://codeforces.com/contest/1697/submission/160311033 why is it wrong?
 » 2 months ago, # |   -19 Very slow system testing because most of people didn't use fast input. Please use it next time :)
•  » » 2 months ago, # ^ |   0 Why is there so many downvotes? I don't get it xd
•  » » 2 months ago, # ^ |   0 fast input can increase speed ~10x for problem B for example. Why is it so bad comment?
•  » » 2 months ago, # ^ |   0 the long systests were not because of people not using fast IO, instead it was due to the very few people expanding the systests to a whopping 60+ testcases on problem B only, and still more on other problems
 » 2 months ago, # |   +4 O(n^2) solution passing for C. Seriously guys, is this what this has come to?
 » 2 months ago, # |   0 Could someone please explain why the same code gives AC for C when compiled with GNU C++17 (64) but it gives Runtime error when compiled with GNU C++17 ??Incorrect soln: https://codeforces.com/contest/1697/submission/160432316
•  » » 2 months ago, # ^ |   0 Lines 94 / 109 you dereference an erased iterator which is undefined behavior.
•  » » » 2 months ago, # ^ |   0 I see thanks!
 » 2 months ago, # |   0 where can we find the tutorial?
 » 2 months ago, # |   0 Why does my rank keep on increasing by a bit in the hacking phase?
•  » » 2 months ago, # ^ |   0 because people participate virtualy
 » 2 months ago, # |   0 Problem C was a nightmare. Tried so many things with "a" and "c" like counting inversions and removing "b" s and they did not work, ate so many penalties and finally went with valid parenthesis approach and still made more penalties because of forgetting edge casesmanaged to solve it but ate 7 wrong answers. who else ?
•  » » 2 months ago, # ^ |   0 i just simulated process of moving first b after a in S if S[i] = 'a' and T[i] = 'b'and same for moving first c after b and used two pointers for that. Also checked edge cases when we can't move right character to that place because characters before it are the same for S and T. (in 10 minutes)
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 ...
•  » » 2 months ago, # ^ |   +1 We have 2 cases when we can change something.if s[i] == t[i] everything is good1: s[i] = 'a', t[i] = 'b' we need to find closest b and swap it with s[i] and also there can't be any 'c' in path -> aaaab... 2: s[i] = 'b', t[i] = 'c' same with above, find closest c, and check if there is no 'a' on pathotherwise we can't get s equal to tbest to use set for O(nlogn) time complexity https://codeforces.com/contest/1697/submission/160327520
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 best way is to solve with 2 pointers for O(n) time complexity
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 ...
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 your solution is not using 2 pointers method.you could just store variable l and go forward until letter changes and if you again need to put letter you can just continue from where you finished last time and set l to i if i > l
•  » » » » » 2 months ago, # ^ | ← Rev. 3 →   0 ...
•  » » » » » » 2 months ago, # ^ | ← Rev. 3 →   0 no, l will go no more that n so it's O(n)if you're interested what two pointers method is check this link https://usaco.guide/silver/two-pointers?lang=cpp
•  » » » » » » 2 months ago, # ^ |   0 There's no need to swap them at all
•  » » 2 months ago, # ^ |   0 Solved during the contest but got hacked :)...hence was unsolved during contest:( Finally solved after 3-4 WA's.