Hello Codeforces!
On Jun/12/2022 17:35 (Moscow time) Educational Codeforces Round 130 (Rated for Div. 2) will start.
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
- CV or LinkedIn Profile (your Codeforces rank has to be added to your CV)
- 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
Good luck on your round, and see you next time!
Harbour.Space University
UPD: Editorial is out
Good luck for Everyone
Yet another meme.... :/
Finally a Div2 Edu Round :)
Sometimes the Codeforces community is crazy. Why is this normal comment being downvoted so many times? Can we stop this kind of "insane downvoting"?
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 :)
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.
Maybe I am gonna be a pupil this time! Hope a nice problems.
NO way . Only solving 1 / 2 question can't make you green
Same for you ;]
It can, if you solve them fast
but eating some sus mushrooms can,
I don't know why I like educational rounds so much.
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.
hope for a good contest, not speedforces .
Good luck everyone! Удачи всем! Hemmäňize üstünlik!
All the best Everyone!
Good luck for Everyone
Geez, they don`t expect much out of the candidates, do they?
Hope to become BLUE at least today.
+1
Good Luck !!!
Do we get solutions of these questions after contest is over anywhere??
Yeah! ...Editorial will be released after the end of contest where you can find the solutions to all the problems!
It's annoying when you passed the given test and it fails on some other test case which you can't even see!!!
Is this a joke or what
problem A is very easy but B I can't solve it XD!
Thats intended :)
I'll die doing C
C was annoying
but D was very great and nice
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?
first you have to know the number of different letters in every prefix there are at most 26 different response you will get
I've already calculated this during the contest, what is the next step?
Wouldn't this exceed the limit of questions if the string is like this?
abcd...xyzabc...xyzabc....xyzabc...xyz..... and so on
The 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?
interactive = binary search
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 submission
Thank you
I think he meant to binary search the 26 steps not the whole string
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.
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
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.
I did exactly the same.
My solution for C has O(Nlog(N)) complexity and it gives tle but some O(N^2) are also passing.
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)
From what I could tell the reason that
lower_bound(set.begin(), set.end(), sus_element)
works in O(n) is becausestd::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
Oh it's very important I will remember it. Now it got AC with it.
my solution
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.
Very nice implementation idea altgifted I thought same but was not able to implement it correctly. Had to go through a tough implementation :)
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?
Because it's ICPC mode
Does that mean the 2nd solution won't be considered? Sorry I'm not familiar with ICPC rules :(
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.
Is today's C related to : https://mirror.codeforces.com/contest/920/problem/C ? How to solve C? T_T
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$$$.
What is the insight about deleting "b"'s?
because '$$$a$$$' and '$$$c$$$' can't swap, so deleting '$$$b$$$'s can check if their number and order match.
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!
jnidv Thanks!
It's more of a proof problem. I'm not sure tho.
What do you notice with the number of $$$a$$$'s and $$$c$$$'s for each $$$s$$$ and $$$t$$$, while iterating from left to right?
can you pls explain your approach?
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).
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.
Can anyone help with C?
There seem to be more solutions to C. I'll explain mine.
First, we need to make a few observations:
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.
hope my implementation using stack give you some hint :-160349549
Worst round since last Month.
Upd. Change my mind:
Please explain the solution to the problem D; Thanks :)
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)$$$
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.
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.
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.
D << C
will you please tell me why this code fails? 160354394
your solution makes mpre than 6000 queries of the second type
E was a nice question with 2 parts to it. How to solve F though?
How to solve E?
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.
Will the connected componnets be atmost of size 3? My code gives WA on tc 4 can you tell me why
...
Test 4 has a component of size 4 (a square which has its sides parallel to lines $$$y=x$$$ and $$$y=-x$$$).
Ah alright thanks!
thx! I catched my error
F is two sat . You can make some variable : (a[i]<=x) is true or false , (a[i]>=x) is true or false.
Oh wow, I didn't think of it that way.
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?
$$$a_i+a_j \ge x$$$ iff $$$\forall y$$$, either $$$a_i \ge y+1$$$ or $$$a_j \ge x-y$$$ should hold.
Ahhhh, that makes sense. Thanks
How to solve F?
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.
What's the observation for D ?
: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.
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.
How to solve D? was D binary search on last unique characters encountered so far?
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?
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<pair<int, char>> where v[i].second is unique. and v[i].first is latest index where v[i].second appears
you can post your submission
No worries, I had done some implementation mistake.fixed it. Here is AC submission 160370256
What is test case 10 of E?
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.
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.
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.
I somehow agree with your serious point but your first two sentences are a little bit offensive in my opinion.
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.
Thanks. Maybe I shouldn't care about downvotes at all.
What's wrong with my sol of problem D. It's showing WA on tc 9 160357208
too many queries leads to wa
Is there a way to solve D without bsearching at every iteration? Feels like there should be an easier way to do it.
I guess no, as the query limit is an obvious indication to do a binary search.
How do you deduce this from query limit that binary search is to be used?
Someone hack my C, https://mirror.codeforces.com/contest/1697/submission/160337496, I think it should give tle for large test case
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.
Probably due to slow I/O in python. It's better to load / write data at once.
What's the testcase 8 in problem D :(
Problem C & D, Easy to come up with the solution but frustrating to implement it !!!!!
solved
is problem D inspired from this ?
When and where can I get the solutions?
Just wait until the announcement post gets updated. It should have a hyperlink "Editorial" by then.
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.
With 27000, you don't need binary search at all.
That's what I'm saying, moving the constraint to 6000 only "artificially" adds an obvious binsearch which is a bit annoying to code
This would make the problem too easy, perhaps easier than C, and the gap between D and E would be enormous.
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
But if the interactive problem is not a typical binary search, I feel like it tends to be very adhoc/implementation heavy
(misunderstood the point, so deleted)
binary search is actually "THE algorithm" here
How is binary search not an algorithm?
I never say "binary search is not an algorithm".
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.
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.
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.
That makes a lot of sense!
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.
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.
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 :c
at position $$$c_1 < c_2 < ... < c_k$$$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$$$ :
c
to the left)a
between $$$c'_i$$$ to $$$c_i$$$ (sincea
cannot be swapped withc
)Then I do the same for
a
, but I try to movea
to the back. I got WA but not sure what case breaks itMy implementation : 160335858
Kind of easier C implementation
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://mirror.codeforces.com/contest/1697/submission/160335317
Oh ya you're right. I forgot to swap it. Thsnks
Here is my submission for problem D https://mirror.codeforces.com/contest/1697/submission/160344339 . The problem states that: "In case you ask too many queries, or the jury program fails to recognize your query format, the answer to your query will be one integer 0. After receiving 0 as the answer, your program should terminate immediately — otherwise you may receive verdict "Runtime error", "Time limit exceeded" or some other verdict instead of "Wrong answer"." The jury program gave me verdict WA, but it also said (in the testcase 10) that i asked too many query type 2. This is unfair, I finished coding problem D when I still had more than an hour to debug.
Edit: actually less than an hour, my mistake xD
same, make the round unrated
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.
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.
You can receive any verdict, period. You may receive something instead of WA, or you may receive WA.
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.
It says you MAY receive any verdict instead or wrong answer. As BledDest said, it does not guarantee that you will not receive WA
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.
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.
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.
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.
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.
I believe that many other contestants would have had the same problem so I'm glad that you will consider it, thanks a lot.
By the way, just for clarification, immediately terminating after getting response '0' will also lead to WA verdict, won't it?
just do
vector<int> a;a[784]=784;
after getting response '0' and you will get Runtime Error instead of WA )What a strange way to write
assert(false)
I didn't see you check 0 as return value, so the verdict will be WA.
I'm new to competitive progamming, so I haven't gotten what you mean yet. Please further explain it. Thanks a lot.
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"
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
Better count the queries in code, and put an assert statement in end to get RE instead of WA
how to do c?
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).
Can someone please explain me why my solution 160333877 gives TLE? From the code the complexity seems like nlogn. Thanks
I believe, it's because you're accessing
st[3]
which is out of bounds.Arghhhh! How did i miss this?! This contest was a nightmare for me. Thanks for taking the time to figure it out.
.
Doesn't Java use dual pivot quick sort for primitive objects? It runs in $$$O(n^2)$$$ in worst case.
.
I think your solution runs in $$$O(nqlogn)$$$ which is too much lol.
Do not use system io for io-intensive problems. Search for fast io
.
For all queries.
Wasted 30 mins on C because of a single "break". How careless I am! :(
Anyway,the problems are fantastic!
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!
yes, I too came up with approach but unable to implement it.
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 roles
and after the contest finished I found out that its wrong because it exceeded the allowed queries -_-
Same, what a pity.
import java.util.*; public class PalinInd { public static void main(String args[]) { Scanner sc=new Scanner(System.in);
} why my code give tle in 3rd test case in java??please answer
A to D are good. Problem E seems interesting, will give a try later.
It seems like the observation of E is easier than D,but I dont have enough time..
What's the different between F and k-sat?
interactive = binary search
or something related to binary bits if constraints contains 32 as limit of queries
https://mirror.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?
1
4
baab
cbba
It give the answer as "NO" only.
Gives YES in my ide
B task is almost similar to this one
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 :)
You can always hack those who passed with n^2
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.
My C just got hacked
Maybe limits for such problems should be reduced to 1.5s
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.
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.
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++.
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.
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 :).
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.
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
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://mirror.codeforces.com/contest/1697/submission/160320598
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
same question as of C in leetcode https://leetcode.com/problems/swap-adjacent-in-lr-string/
Lol. Roles got reversed.
Last Atcoder contest has the famous leetcode problem: construct binary tree from preorder and inorder traversal.
the guy's solution is weird 160366565
It seems to be written like this on purpose and then hacked by others.
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?
Because Arrays.sort() is actually O(n^2)
good contest
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?
Arrays.sort
in Java usesO(n*n)
)Instead of
int[]
, ifInteger[]
is used, it passes.Check this blog to understand more.
wow, this is extremely helpful, tysm! I never knew this — somehow I have solved many NlogN problems where N>=100k without knowing this haha.
Completely bricked C. Bye-bye rating :(
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
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.
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.
Often struggle with constructive algorithm problems in div2 C. Any suggestion for improving in this category will be appreciated.
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 other
Now 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
cbbababaac
we 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<j) and disregard first 2 characters now i=10 and j=4, count a,b,c in s=4,3,0 till i-1 and count of a,b,c in t=1,1,0 .Again condition is true,we move to next 'a' in t. i=10,j=6 count of a,b,c in s=3,2,0 till i-1 and count of a,b,c in t till j is 1,1,0.Again condition comes to be true. move to next 'a' in t. i=10 j=8 (a,b,c) in s is(2,1,0) and in t is(1,1,0). Again true. move to next 'a' in t .in s (1,0,0) and in t (1,0,0) .Again true and we dont have any more 'a' to move for . and hence we terminate and we can say it is possible to interconvert s and t
When will the rating change?
How to check whether System testing is done or not?
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.
When will Editorial out?
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?
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
Thanks for helping. I got it now.
waiting for editorial.....
Very slow system testing because most of people didn't use fast input. Please use it next time :)
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
O(n^2) solution passing for C. Seriously guys, is this what this has come to?
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 ??
Correct soln: https://mirror.codeforces.com/contest/1697/submission/160348230
Incorrect soln: https://mirror.codeforces.com/contest/1697/submission/160432316
Lines 94 / 109 you dereference an erased iterator which is undefined behavior.
Why does my rank keep on increasing by a bit in the hacking phase?
because people participate virtualy
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 cases
managed to solve it but ate 7 wrong answers. who else ?
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)
...
We have 2 cases when we can change something.
if s[i] == t[i] everything is good
1: 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 path
otherwise we can't get s equal to t
best to use set for O(nlogn) time complexity https://mirror.codeforces.com/contest/1697/submission/160327520
best way is to solve with 2 pointers for O(n) time complexity
...
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
...
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
There's no need to swap them at all
Solved during the contest but got hacked :)...hence was unsolved during contest:( Finally solved after 3-4 WA's.
I think my solution for problem C was cool. I turned s into a list of tuples by counting same characters in a row, i.e. aaabbaccb would turn into [('a',3),('b',2),('a',1),('c',2),('b',1)].
if there is a match I decrease 1 from current char, otherwise if there is mismatch and possible to fix, I would decrease 1 from the following tuple. i.e., if s=aaabb and t=babaa, Then [('a',3),('b',2)] would turn into [('a',3),('b',1)], then [('a',2),('b',1)], then [('a',2),('b',0)] (when zero I delete it) then [('a',1)], then [('a',0)] and done.
To check that a mismatch is possible to fix is easy. If the mismatch is a!=b, then I just check if the next tuple contains 'b'. Also, when I delete an element I merge two consecutive elements of same char. Also the listis actually reversed so I can pop() in O(1).
Why is it showing unrated for me?
You are not alone bro.. But its taking a way more time than expected:).
oohh okay brother
Is it only me or the ratings for this round hasn't been updated yet for everyone?
https://mirror.codeforces.com/blog/entry/103654
It just changed for me, and I think it changes for everyone at about the same time.
Waiting for the rating to change.
the same code "copy & paste" :
TLE : 160442368
ACC : 160372033
How does this code get Acc with O(N ^ 2) where N is up to 1e5?
I see a lot of O(N^2) with Acc not only this
This is a more formal explanation of a solution to problem D.
Denote a query of type 2 by $$$ d(l, r) $$$, i.e. the number of distinct letters among $$$ s_{l..r} $$$.
First, find the first occurrence of every letter in the alphabet. They appear at index $$$ 1 $$$ and all $$$ i $$$ where $$$ d(1, i - 1) < d(1, i) $$$. Use queries of type 1 to find out the letters at these indices. There are at most $$$ d(1, n) \le 26 $$$ such indices.
Then, consider all prefixes of the string $$$ s $$$ in ascending order of length. Denote some prefix by $$$ p $$$ and its length by $$$ m $$$. Assume we know every letter in $$$ p $$$ already, now we will determine the next letter $$$ s_{m + 1} $$$. If we already know $$$ s_{m + 1} $$$ from the first step (because it is the first occurrence of a letter), we can move on to the next prefix.
Maintain $$$ c = $$$ set of letters in $$$ p $$$, and $$$ L $$$ = map of each letter in $$$ c $$$ to the index of its last occurrence in $$$ p $$$. Since $$$ s_{m+1} $$$ is not the first occurrence of a letter, $$$ s_{m+1} \in c $$$. Sort $$$ c $$$ by the value of $$$ L[c_i] $$$ in ascending order. We are looking for the last letter $$$ k $$$ in $$$ c $$$ where $$$ d(L[k], m) = d(L[k], m + 1) $$$, because it implies $$$ d(L[k] + 1, m) < d(L[k] + 1, m + 1) $$$ $$$ \implies s_{m+1} \not\in s_{L[k]+1..m} $$$ $$$ \implies s_{m+1} = k $$$. Note that we can compute $$$ d(L[k], m) $$$ instead of making a query. We can binary search for the required $$$ k $$$ in $$$ c $$$. Continue by setting $$$ p + s_{m+1} $$$ as the next prefix.
$$$ O(n \log 26) $$$ queries of type 2 are used.
I upsolved D here: 160441046
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Problem D was so great !!! Thanks for this nice round :)
Just did problem E. Awesome problem!
First I noticed that the sizes of equal distance groups can only be 4 at most.
Then I noticed that you just need to keep a list of all points of minimum distance from you.
Then I noticed that the only way to color a few points the same color, is if they are all minimum distance from each other.
Then I noticed that a group (of min dist from each other) has to either be colored the same color, or all different, and this type of coloring is completely independent from the other choices for other groups.
From there it's straight forward, a dynamic programming depending on how many colors remain, and if you choose to color the group in the same color or all different colors (no other options). i.e. dp[number_of_group][colors_remaining][color_same_or_all_different].
Don't yet know its rating, but might be the highest rated problem I solved!
Finally specialist!!
At problem C. Can anyone explain why I got TLE in the first submission and the other one doesn't?
Link 1: TLE submission Link 2: AC submission