UPD: Special thanks to Mikhail awoo Piklyaev for help with translation and problems discussing, Maksim Neon Mescheryakov for problems discussing, Artem Rox Plotkin, Daria nooinenoojno Stepanova and Tommy STommydx Li for testing the round!
UPD2: Editorial is published!
<almost-copy-pasted-part>
Hello! Codeforces Round 590 (Div. 3) will start at Oct/01/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.
The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.
You will be given 6 or 7 (or 8) problems and 2 hours to solve them.
Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:
- take part in at least two rated rounds (and solve at least one problem in each of them),
- do not have a point of 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.
Good luck!
I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.
</almost-copy-pasted-part>
I can’t register for the contest unofficially. Is something wrong? Edit: Can now.
maybe delete this contest? if you agree upvote me
rtd?
what factor decides the number of problems ? Planetory motion?
We increase the number of problems by adding some new problems or subtasks of existing problems to smooth some gaps in difficulty.
Don't give up, Learn from your mistake
I've made some mistake on vovuh's previous contest Educational Codeforces Round 73 (Rated for Div. 2) and Codeforces Round 587 (Div. 3), It's my high time to apply what's I learn from that mistake.
Thanks vovuh for giving us another chance to improve our skills (and rating ;-) )
Lolololollolollllll, who asked you to divulge the story of your life??
Never give up. One day we 'll change our colour.
This contets is 1234 contest in codeforces Good luck to everyone.
Codeforces Round 590 (Div. 3)
https://mirror.codeforces.com/contests/1234
Thanks for the billion dollar information. You saved the world.
Will vovuh surpass awoo
I don't think it becomes true someday :(
Div.3 are much less useful for most participants so I gain less contribution than this tiny anime girl.
Yes and Educational rounds are also as frequent as div3 rounds. But you are only 2 points behind him. Maybe it will happen some day.
I think they're more useful. Div. 3 taught me a lot of standard tricks and quicker implementation back when I was a beginner. Educational rounds serve a similar purpose, but require a contestant to have a fair amount of familiarity with the aforementioned standard tricks. Since there are many more beginners in competitive programming, Div. 3 contests are far more valuable to introduce people to problem-solving.
Keep up the good work, man!
TRUE NOW!
Congrats vovuh
And now I can finally say thank you and deliver a message to awoo:
Now awoo's contribution is higher than vovuh again :XD.
I really like your contests, hope it doesn't get like Codeforces Round 579 (Div. 3) that the judge was so slow. good luck in the future contests vovuh :)
Well guess div3 always gets a judging queue that ruins the contest.
I_love_vovuh
I will AK this contest !!! And I will AK IOI2020 in just 3min with Denverjin !!!
Yes, I will.
As you see, I have AKed the contest. It means that I will AK IOI soon.
HYHAKIOI!
I know that it is out of topic, but will the Technocup Elimination Round 1 be rated?!
Well, I guess that Technocup Elimination Round 1 announcement would be a better place for such question.
Yes,It is ! :)
Hope to become blue after this round.
you downvoted me.... but I still will show my strength in the contest!!! (angery smiley)
Think you'll become blue)
Can anyone please tell me which problem has two subtasks? @vovuh
problem A
Hopefully problems won't be bad like last contest!
QueueForces?
exactly!
What is the reason behind giving ~50 test flies for problem D?
Why always this problem -> Queue
More than 5 minutes testing queue :(
this queue affected me really more than 15 minutes !
Look at rank 17 (Alex_____Wei) and rank 18 (AIex_Wei). Are they the same person?
NO , I'm just another account of Alex_Wei
And AIex_Wei is a FAKE one , he is chenxiaoyan
So, in total how many accounts you have? 1 or 2?
6,Alex_Wei,Alex__Wei,YDontYouWriteBruteForce,My_Rating_Is_1064,Alex_____Wei,Solar_Pea
Why you do this?
In order to compete in Div.3
You can always do that unofficially like lot of reds and oranges. Wouldn't new accounts affect ratings of normal div 3 people. Not sure how cf treats new user.
Is F a well-known problem?
How to solve F? I tried solving it using trie greedily but later figured out that greedy won't work.
Yeah an application of SOS(sum over subsets) dp. Link to the blog is :
Link
:(
Drake
no
: ScreenshotDrake
yes
: Photo of screenthis legit happened to me today
nice :)))))))))
I tried to solve D using fenwick tree but I failed coding it terribly anyone can tell what's wrong in my solution
link
there are 26 lowercase characters I used bitwise OR segment tree then count the number of bits for the L,R range
I know but it can be done with fenwick tree also but I did something wrong
Your
n
is not initialized anywhere in the code.in update I made the limit to 100001 and forgot to make it in delet but that's not the problem
One more bug
What's that semicolon doing at the end of for loop
Also you need to re-initialize
x
again, you are depleting it fora
itselfFix all these and try
thx bro got accepted
You can solve it easer. Just take a 26 sets of $$$i$$$th character positions ($$$i$$$th set contains positions of $$$i$$$th alphabet char in string). So, when you've got a update query, just delete $$$pos$$$ from $$$lastc$$$th set, and add $$$pos$$$ to $$$c$$$th set. When you've got a count request, for each of 26 charactes find any index in set, where $$$i\geq l$$$ and $$$i\leq r$$$, if it exists, just add one to answer.
Here is the code for the above approach : https://mirror.codeforces.com/contest/1234/submission/61643240
Hey can you explain your approach a bit so that i can understand your code easily?
Same as explained by MrLolthe1st. 26 sets that maintain the indices of the 26 alphabets.
The problem became so easy with your solution. Thank you dude
That's easier damn but I still want to know wth is happening in my code it didnt make any sense to me all values are 0 even though im updating
You also missed to update
s
But I guess there is still more bug
that's not necessary what matters is BIT array and all of it is zero and I can't figure out why
really? Wouldn't you delet some other character if same xx comes later on?
yeaaah yeah that's right but as you said there's another bug
me in this round
Drake
no
: Debugging own codeDrake
yes
: Create meme on selfI tried to solved D by simply map and string. I thought it will got TLE but I got AC. Here is my code. Can anyone suggest what is complexity for my code?
Its $$$O(Q*N)$$$
So How do I got AC instead of TLE?
Some optimizations in C++ language itself.
From docs:
The unspecified part is interesting, will need to check the source of C++ to know more.
Same for
find
.Pretest is a little bit weak. Some submissions in $$$ O(QN) $$$ can pass the pretest.
Sorry, but don't know the purpose of problem D unless there exist a solution without log(n) factor. C was far better than D. How to solve E?
How to solve C?
There is one way from $$$(1,1)$$$ to $$$(2,n)$$$ in any dataset, for which answer is "YES", only .
I have used the simulation strategy to solve this problem:
start from column 1 and row 1 :
if(pipe of type 1 or 2): you have to just move to next column with the same row else if(pipe of type 3,4,5 or 6): ... check the other row with the same column should have pipes(3,4,5 or 6), if(check = true): just change the value of row i.e from row=1 to row 2 or from row=2 to row 1 else if(check = false): you should print no as final answer
at last if row == 1: you should print 'NO' else The final result remains as it is what you get from the previous steps
You can understand better with my code: q=int(input())
for _ in range(q):
I used the same logic but there was a small mistake which I could fix only now :((
What is the mistake?
I solved C using recursion, but was able to submit after 20 min of contest(my bad was not able to figure out one error)
Usually during contest, i coded with comments so i don't get lost for what i need to do.You can check my submission here: https://mirror.codeforces.com/contest/1234/submission/61665005
Can anybody tell me test case 4th in problem E?
EDIT Forgot to take long long :(
Why unordered_map fails for Problem B2? I got TLE using unordered_map, but I got AC using map.
lol same wasted 2 hours over this. All solution on B2 should be rejudged everyone knows unordered_map is faster than map . It costed me almost 1000 rank due to this shitty issue.
SAME HERE BROTHER
Well ordered_map is always LogN Unordered_map isn't always O(1). It's usually O(k) where k is the size of buckets. Since in many cases k is small we take it as O(1). However when there is alot of collisions then it is O(n)
me too.o(╥﹏╥)o .So I didn't solve B2 in the contest .And I want to know why the unordered_map is less efficient than map this time.
unordered_map has a biiiig constant. sometimes, it doesn't works better, than map. And use there deque, not maps.
I used map (to save # of displaying ids) AND deque (to save displaying ids and their order). Can we use deque instead of map?
Even I wasted almost 30 min on this to recall that the worst case complexity of unordered map or hashmap is O(n) i.e. linear time...
Kudos to B2 problem to refresh my basics. But unfortunately I'll be afraid of using it in future
Can you tell me why unordered_map was going to the complexity of O(n) ? In a past contest I was getting TlE because I used map and got AC after changing it to unordered_map . Now I am just confused what to use because of this .
It's linear because of collision. I suggest you to read about hashing and collision.
And when you got AC earlier with unordered_map, it must be because the test cases were such that the collision was minimum
I have no idea how you managed to get TLE just because of the unordered_set. For me it is faster than the set on the given test data...
unordered_set:61684841
set:61666722
Hi all I tried to solve problem D using segment tree , but gets TLE at test 4. What's wrong with my submission ?
Do not solve D with segment tree.
I solved D using segment tree. https://mirror.codeforces.com/contest/1234/submission/61635269
I also can solve a * b problem with segment tree, and what ?
What? You can easily implement segtree and get AC, why not?
Can you explain you solution please ?
Build a OR segtree and print popcount(number of 1s in the result)
You can understand this easier by reading my code.
what's the alternative approach??
$$$O(Q\times\log{n})$$$
26 binary searches for one query
I solved D using binary search based on data structure set. So, the complexity is $$$O(q*log(n))$$$. Firstly, I stored all positions of character c ('a' <= c <= 'z') which occurs in s in
set<int> list[c]
. After that, each query, if type 1 I erasepos
inlist[s[pos]]
and insertpos
inlist[c]
. If type 2, I check all characters (maximum 26 characters) if range[l:r]
covers atleast 1 charater c (using binary search in set), i increase answer.My solution
your query function works with O(26*log(26)*log(N)*Q) it is about 10^9 operations
You merge 2 sets in each node of your tree. It's something like O(q * n * log(N) * log(N))
Can anyone please tell me the difference between these 2 codes for problem B2 — https://mirror.codeforces.com/contest/1234/submission/61663199 (AC code)
https://mirror.codeforces.com/contest/1234/submission/61657941 (TLE code)
dont use unordered map without custom hash or else you'll get tle.
Yes my mistake I should have read about custom hash earlier didn't know unordered_map could got to O(n^2).
something wrong with the problem tags
Also, lot of problems are tagged something but there is no reference solution (in tutorial) which uses that tag. So, the tag is more or less useless.
its becuas dp is double important :)))
and also bitmask
fixed & thx
I registered but didn't manage to enter the contest in time. Is my rating going to get affected ?
Your rating won't change unless you submit any solutions.
In Problem A, those who used ceil() function directly in cout, got WA.. Could you please explain why??
ceil returns a double/float. you can make that:
https://en.wikipedia.org/wiki/IEEE_754
U can use a well known trick to divide n by k rounding up. This value is a (n + k — 1) / k.
Very Interesting..
Note though that this only works well if $$$n$$$ and $$$k$$$ are both non-negative.
Can Anyone tell me what's wrong with my code for D. I'm getting TLE for this Sol link — https://mirror.codeforces.com/contest/1234/submission/61662523
haha, this div3 was more educational for me than all educational rounds.
Admin please rejudge the solutions of problem B2 for those who get TLE for using unordered_map and got AC by changing it to map . It wasted valuable time trying to figuring this out and I thought it was problem with my logic.
This is why unordered_map may exceed the time limit in some cases.
Wish I had seen this post earlier.
is there any way we can use binary search on TreeSet In Java. In problem D was adding all the indexes of every character in TreeSet but don't know how to use binary search on TreeSet.
Few useful functions of TreeSet that resembles binary search: tree.floor(int), tree.ceil(int), tree.higher(int), tree.lower(int)
How to solve F??
Why do I get TLE here? It is simple segment tree working in q * 26 * LOGN https://mirror.codeforces.com/contest/1234/submission/61659331
My solution with IT: https://mirror.codeforces.com/contest/1234/submission/61659385 350ms
What is IT? indexed tree?
Interval Tree
I came up with the ideal of problem C early but I can't implement it quickly. It took me more than 1 hour to implement C. So, I have about 30 min left for problem D, I also came up with the solution but I can't debug on time. Now I solved D, very funny experiment =)))
I used segment tree, stored set in each node, i think the complexity should be O(q*log(n)*27). And i got TLE, Any idea why?
CODE: https://ideone.com/D2AmFn
My solution with IT: https://mirror.codeforces.com/contest/1234/submission/61659385 350ms
Your solution works O(26*log(26)*log(N)*Q) it is about 10^9 operations
https://mirror.codeforces.com/contest/1234/submission/61659331 This is q * 26 * logN....but still TLE ...any idea what's wrong?
I don't prefer your realization of segment tree, but does you sure that here
all ok?
We only need to update nodes for which l lies in range [st to en] ....so i don't think that should be a problem
Log(26) because of the insert in the set, that's right?
yes
your solution working in O(q*logn*n*log27), may be that so, because each of node you merged 2 two set. sorry my bad english
In "O(q*logn*n*log27)", Why there is 'n'? I think it should be "27" instead of n, Because the size of the set will not exceed "27".
And even if it's "27", it is about 10^9 operations.
I'm Sorry. Your solution working in exactly O(qlogn*27*log27) time. sr
Pathetic Contest
the best hacker link
He very humorous =))
Can anyone explain why unordered_map solution is getting TLE and map solution is getting accepted for problem B2. Is there any specific case where unordered_map is slower than map.
dependent on data type, umap is faster than map when you can sort large arr
Yeah when there is alot of collisons then unordered_map isn't O(1). However ordered_map is always o(1)
I think ordered map is O(logn) in general case... Also I think there is a very similar and famous problem like problem B2 presented today where unordered map can give TLE, it's on codeforces only, — Molly's Chemicals, if anyone want to try it out...
how to solve C??
First you can start with the idea that there is only a single path that can allow flow of water from (1,1) to (2,n+1),because if you receive water from one side of pipe, another end can only face a fixed direction if you are getting water from fixed and unique direction (except for the case when you have tilted pipe and receive water from left side to that pipe, so it could continue flow in up or down direction ). So simulate that flow till either an out of bounds occur, otherwise if you reach (2,n+1) before, your answer is "YES", otherwise "NO". Hope it helps
I see people complaining that unordered_map gets TLE, then why didn't I get TLE during contest, even I didn't get it after the contest. (Just submitted 2 min ago)
It's because you are erasing the elements. AC with erase: https://mirror.codeforces.com/contest/1234/submission/61669672 TLE without erase: https://mirror.codeforces.com/contest/1234/submission/61648570
But still if someone set k = n and throws distinct numbers , wouldn't the first and second be same ? , what makes unordered_map TLE ? (More elements or same elements frequently ? )
what makes it go O(n) is that the numbers entered get hashed to the same hash value, i.e. if internally a poor hash function is being implemented;Generally it has no effect but here I think the test cases were such that unordered_map could not hold good.
Not quite "same hash value" (though that is a factor when dealing with things like strings); the more pertinent issue is bucket collisions. For example, even if there are $$$2^{32}$$$ possible hashes, the actual number of buckets in the map is often much less (stepping up as more values get added based on something called the "load factor"), so if the hash modulo bucket-size is equal you'd get a bucket collision. In such cases C++
unordered_map
s would store a linked list in each bucket, making access potentially $$$O(n)$$$ time for adversarial cases.Java's
HashMap
s handles this problem better since Java 8, as if too many items are put into the same bucket, the internal linked list gets converted into a tree, thus worst case access is $$$O(\log n)$$$ time.Hacks are not added yet..
My question might be stupid but I gotta ask. What's the point of having a hacking phase in Div3 and Edu rounds if hacks aren't counted in the score?
The point is to let others find the error of your program, improves yourself on a certain level, to reduce unnecessary errors.
(Or it's just for fun?)
I tried to solve D using sqrt decomposition but didn't manage to implement it right, can someone spot the error in my code?
Link
There is also the issue of time limit, it runs in $$$O(Q* nlog(n))$$$ due to sorting all the time. So, sqrt decomposition did not help much.
After quiting codeforce contest for about 3 years, I participated in 590 and 589.
It seems the problems have become harder than that of 3 years ago, problem E and F of 590 div3 has similar difficulty of typical div2 E 3 years ago.
I thought I had been more skilled, but the problems have been harder...
The future is now old man.jpg
For Problem F ; You can use SOS DP. Question Statement changed : We need to find out 2 substrings such that they contain different letters and are non overlapping.
If we were to consider the strings as integers, where each character represents a bit ( where in set bit means that, the character is present ). For eg : binary for ac would be 101. Now you need to form all such numbers(strings which cannot have length more than 20, as then it would for sure contain a repeat).So insert all the strings starting at one position without having any repeated character. And then you need to check for each number whether it has a subset of its complement. We will consider the subset having the maximum number of set bits, which can be found out by simple SOS DP. Link to the solution : Using long long int (not required) : it may give tle as this solution : https://mirror.codeforces.com/contest/1234/submission/61652445 Using int : https://mirror.codeforces.com/contest/1234/submission/61743609
Can anyone please tell me what's wrong with my code for B2? 61673618
I believe this part
is wrong, what you want to do is freq[brr[st]]=0 because you need to remove the start of brr not the start of arr.
Thank you so much. I made a very silly mistake.
WTF!!!!
How the Editorial published before end of the hacked phase?!!
The long queue really spoiled the contest to be honest With B2 not working for unordered_map i had to make three wrong submission(equivalent to 45 min long queue wait) to finally realize the error. :\ Could have solved c and d had the queue not been so long :(
Changed my dp cause the contest has really spoiled my rating
how to solve C problem?I have no idea.
My code for B2 got hacked (time limit exceeded) and i really can't understand why. I made a simple solution with a set and a deque. I have seen this kind of solution at everybody and they still got accepted. 61660949. What can be the problem?
A moment of silence for my fallen brothers and sisters who got TLEd/hacked in B2 because they were innocent enough to trust the default hash in
unordered_map
andunordered_set
instead of using a custom hash. You were too pure for this cruel world filled with hackers.You shall be honoured, your sacrifice shall not be in vain. Fear not, you shall rise stronger than ever, and ascend to your rightful place in this world !
I'm one of those brothers. But i still can't fully understand what is the problem with unordered set/map in this problem.
Worst case complexity for default hash is $$$O(n)$$$. So in everyday cases using it might be okay, but if an adversary knows your hashing scheme they might design a hack that will take linear time, causing hack/TLE. Either use
set
or use a custom, randomized hash.Check out this post.
Oh, this is really, really painful :))))). Thank you a lot. From now on, i will be really skeptical when using unordered sets/maps. :)))
No problems, I too got hacked by the same guy, in fact.
You can check out this entry. You can always use unordered_set or unordered_map but with a custom hash function. Read the article, and you will understand.
Is it fair that a single person hacks 50 B2 questions with the same test case? The lack of test cases and the long queues made the contest worse!
wrong submissions will anyway fail system tests.... even if he sits silent and doesn't hack anyonee....the final result will be same
These were Accepted submissions.
no they just passed pretests that doesn't mean they are right hacking is done before system test so if a solution is hacked...it would have failed system tests as well
if we write a correct solution then nobody can touch it .... if we write a wrong solution nobody can save us
well, that logic certainly doesn't work for non-deterministic solutions (hashes for instance).
yes (:
Getting aged by waiting for system testing.
Will there be an extra system testing? It says the results are final, hacking phase complete.
There will be a final system testing.
When will the ratings be updated for this contest ?
waiting for it too.
After the system testing.
System testing is taking more time than the actual contest.
System testing is run on mobile phone instead of servers
Round was cool, especially problem D and E. Hope in future will be rounds like this!
Thanks for vovuh for the nice div3 round.
Hello all! How can I find my position after a contest? (if I haven't a history)
Yeah, its weird that one has to keep scrolling the standings. One way I use, go to your
user page
, click oncontests
and at the top you will see it https://mirror.codeforces.com/contests/with/__Andrewy__My Solution to Problem D was skipped . According to the rules , there is no problem to use third party code if it was published before the contest. The problem is a reduced version of the problem DISTNUM . So , i used this as template and changed accordingly , This is my solution . I guess this solution also did something like that . It is a coincidence that both used the same source . So , can you please put me back to the contest ? MikeMirzayanov
I used segment trees for problem D. Each node of the tree was an unordered map of type < long long int, bool >. I am not able to understand how it is showing TLE for test 4. Any help would be highly appreciated. Down below is my code
epic contest for epic programmers i congratulate you!1
WHY did you add anti-unordered set tests in B2? I could've become expert in this round https://mirror.codeforces.com/contest/1234/standings/participant/28564088# unordered set https://mirror.codeforces.com/contest/1234/submission/61718932 usual set
Well, educational rounds are educational in this painful way too.
Yep. Lesson learned :-)
J Q K A