Привет! В Mar/02/2023 17:35 (Moscow time) начнётся Codeforces Round 855 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, myav, Aris, Gornak40, senjougaharin и Vladosiya.
Также большое спасибо: tolbi, lunchbox, Son, sary, Wibo, yorky, nigus, tute7627, 74TrAkToR, bigfoot19982, oversolver, Be_dos, CARBINE, molney, KoT_OsKaR, Nickir, cute_hater, Crutch, vrintle, Rubikun, akulenok, medk, Jostic11, Ghassane за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.
Всем удачи!
UPD: Разбор
I became expert for the first time around an year ago. But never got a chance to participate in an unrated div 3 contest. So this is my first unrated div 3.
I hope this div.3 will help people increase their rating . Good Luck to all!
positive points to all!
THE Worst Contest I Have Ever Seen!..
I was solving some NP problems and I saw this contest. I thought it could have some nice problems and it will be worth the time that I spent. But I am regretful of entering this contest. My time has gone in a useless way.
ok
I became expert an day ago. unrated div 3 make me feel a little sad.
i took part in only three rated rounds. Unrated div 3 make me feel a little sad.
hh,div3 will be unrated >1600,upperclassmate had missed extension meeting(
how long it took to you to become expert?
Around 10 months
but you can register new id to get happy rating.
I believe in no alt supremacy.
This div3 round will be the 1800th contest of Codeforces. Congratulations!
Congratulations!
Wow! congratulations <3
....
atb!
"do not have a point of 1600 or higher in the rating"?
Whis the last two problems of the contest will be interesting.
looking forward to be pupil finallyy pls
didn't participate ig
Hope so I reach pupil this time. :-)
maybe you can
My birthday contest! I hope I can become expert. Edit: lol I'm dropping a lot
you can now! atb
I hope being specialist after this round
вот блин,почему раунды див3 рейт только для людей с рейтингом меньше 1600(
Apparently I probably get negative delta in the last div 2 round which will put me back to specialist.
If my rating isn't update soon will this round be unrated for me ?
Div.3 is perfect for my first rated contest.
Looking forward to a good rating.
Expect +200 easyy
First time to test a codeforces round, The problems are nice, I recommend everyone to participate, have fun and prepare your cats!
What does
prepare your cats
mean (?)muchas gracias aficiónados esto para vosotros SIUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
Круто! Всем удачи на предстоящем 3-ем Диве. Теперь ждём Див. 4)))
This will be my first div 3 contest I'm so excited
waku waku
As a tester, Worst Contest I Have Ever Seen!..
Just a joke of course the best <3!
Worst Contest I Will Ever See!..
:)
Let's see!
hope a big postive delta I want to rank up to be Specialist:)
this time div3 contest will not be rated for me. Mixed feelings
I hope every participant to get + points and do well today <3.
I have to say it... drumroll..
stringforces
lets become pupil
congo
StringForces
I think first prob should be like: "the string can only contain the letters 'm', 'y', 'a' and 'v' ..."
never thought a day will come that I'll hate strings and string algos.
it's sad that I wasted too much time on D due to a small mistake again :(
I can't reach expert now.
the worst round of my life...
Great Contest!
Enjoyed solving a bunch of problems, Finally back to specialist again :D !
Nope . Not Today sadly.
Didn't age well xD
A great Div 3 as always. My best ever contest performance.
A: Pretty trivial, just remove duplicates
B: Process all the good pairs, then for letters with >= 2 occurrences use a k to make them good.
C: Standard priority queue, I took a risk and didn't prove it however. (also got a penalty because I forgot to use long long >.<)
D: Another solution I didn't prove, but I used memoization and checking for !memo[i][s[i]+2] to increment answer
E: I did casework for the easy version, then generalized it for the hard version.
D has a rather simple solution by checking characters at index $$$i$$$ and $$$i + 2$$$ and if they are equal they give the same string.
How do you prove it tho?
not a mathematical proof, but here I go- let's suppose 2 char are equal and they are 'X' in "abcXdX". If we remove (Xd), string is abcX, and if we remove (dX), string is abcX, which is the same. . For: XdX, if we remove Xd, (X) remains, and removing dX, (X) remains. I hope this helps
C is similar to IZhO 2023 Day 2 Problem 1, where you have to match bonus cards to the right (another type of) cards as well
Ignore this, since the earlier message can't be deleted
Wow, I didn't know something like a priority queue existed. For the easy version, I just retrieved the maximum element of the previous elements before the hero card, but that gave me a TLE for the hard version as expected. I was searching for something similar to a priority queue, but I wasn't knowledgeable enough to create something like it from scratch. I am sure it will come in handy in the future.
Multi-set works too
How to solve F?
I'm getting WA3, but I still hope the direction is right, correct me if it's wrong;
I came to using https://www.geeksforgeeks.org/count-pairs-given-xor/ so 25 unique characters, for each word, we go from a character 'a' to 'z' and set 1 if the number of occurrences of a character in the word is odd, and set 0 otherwise.
then we try to exclude every character from 'a' to 'z' and consider all other 25 characters, we said that each character should occur an odd number of times, in binary it's all 1s, so we count the number of pairs with xor equal to all 1's
but getting wa3
Been trying the same. Seems like there was a case of overcounting. Also, in the problem, $$$i = j$$$ can never contribute to the answer.
When the character is not present then it's also 0 becuase it occur even number of times. How are you checking if there are exactly 25 characters? are you checking this case too?
You can Use bit manipulation with DP.
See you have N strings. For each string count the number of all characters present them if all the characters from 'a' to 'z' is present in the string than this string is of no use for us.
So we consider all the strings where unique characters are less than 26. For each string we will create a val initially with 0. If some character x comes odd times than we will add (1<<(x-'a')) to val. Now we can use a DP of say type like this
vector<unordered_map<int, int>> dp(128). For each character ch not present in the current string we will increase the value of dp[ch][val] by 1.
As the number of strings are 2*10^5 the number of values are also can be at max 2*10^5. Now similarly for each string again we will check for all the characters that are not present in the string we will consider them not present in the second string as well and for remaining characters if some character is present odd number of times in current string than it should be present even number of time in other string and vice versa.
This way we get a value same way we calculated while creating the DP. For that value and absent character we will add that value to our answer.
At the end for each string we had added each value twice. So print ans/2.
Nice Div. 4 Contest
Is it possible to calculate the hash when swapping one character with another? I used the polynomial rolling hash algorithm, but my code fails on Test #5 in Problem D, not sure what exactly that I did was wrong. Can someone give me a clue why my intuition was wrong?
Submission
I guess it's because of the anti-hash testcases, made to elevate the probability of collisions. And I couldn't find a way to use two different hashes for the computation.
Gave this question a 15 min thought and realized it's just observation and 3-5 lines of code.
How to solve D?
D can be solved by checking characters at index $$$i$$$ and $$$i+2$$$ and if they are equal they give the same string.
Wasted 30 minutes in D because I thought hashing would work..
I did hash ... xD
lol, my solve function has 11 lines
Could you please elaborate on what do you mean by hashing. I have somewhat basic knowledge of what hashing means, just curious what was your approach.
lets say a string is: $$$abcde$$$.
At first the hash value is like this:
$$$a*X^0 + b*X^1 + c*X^2 + d*X^3 + e*X^4$$$
if you remove $$$bc$$$ from the string then it becomes:
$$$a*X^0 + (d*X^3 + e*X^4) / X^2 = a*X^0 + d*X^1 + e*X^2$$$
let this value be $$$y$$$. so we just have to count the number of distinct $$$y$$$ for all adjacent pair of characters.
Aaah, got it! Thank you very much!
Same, even I wasted 20-30 mins thinking of prefix-suffix hashing...
Double hashing worked for me (although it was a pain doing it lol)
Yeah it was a pain. Could you maybe take a look at my submission?
195675499
Sorry for the late reply! But I regret to tell you that you were correct for most of the parts, and there was just a tiny little flaw! The problem with your code is that using 2 maps would cause issues, for example
string1 = (3, 5) string2 = (3, 6)
This case m1[3] and m2[5] is true after registering string1. When your code comes across with string2, it will not try to record it, since m1[3] is already true!
Therefore, a correct implementation is to merge hash1 and hash2 into 1 single number. (i.e. hash = hash1*(1e9)+hash2) Then, simply use 1 map is sufficient. Here is the amended code of yours (Submission ID : 195846862)
.
stringforces
i think it was nice for speedrunners
In problem $$$E2$$$ why $$$k$$$ may be larger than $$$n$$$ !?
I wasted 15 minutes because of that (I assumed that $$$k≤n$$$), and I'm sure many people failed because of that case.
If you read statement carefully they mentioned there is no boundation on the value of k. Also there was no relation mentioned in the statement as well between n and k.
Nice problems like always. orz ITMO University team
I've already hacked it.
same for me. luckily found the case just before the contest ended.
Nice round with a variety of themes!
how can i optimized this solution for problem E1 https://mirror.codeforces.com/contest/1800/submission/195690945 I have used brute force approach to check
There are two types of letter positions:
unreachable by any swap (eg. third in 5-letter word)
possible to do a swap with some other letter
So for the first category they have to be the same, position-by-position (as they cannot be swapped). For the second category only total number of each letter must match — because they can be permuted in every possible way (I didn't prove it formally, but just assumed and it worked). There was no need of finding the chain of swaps leading to correct one
here answer me how WE COULD SOLVE THE PROBLEM C WITH NOT KNOWING THE QUEUE
using multiset
or write treap (Декартово дерево координат)
Can Someone Please Point Out Why My Code Fails For F?
195704952
My casework solution for E1 lol, it actually helped me realize the general solution for E2 and only needed a few tweaks.
Not only yours, I did the same for E1 and it really helped in E2 https://mirror.codeforces.com/contest/1800/submission/195683040
Wow, our ideas were really similar!
well, I have a completely different approach as yours. Mine uses dfs, because it seems more intuitive for me. Just couldn't thought of other solutions other than graph in comp. :)
Can you tell why for n>=6, it is always "YES".
was it your observation or is there a logical reason behind it ?
If n >= 6, you can swap 1 4, 1 5, 2 5, 2 6, 3 6. So this implies you can swap any two characters.
Did some minor optimizations and did the E2 also.
As a tester, I was late xD
A: Implementaion.
B: For each pair of lowercase and uppercase we count their occurence, let they be cnt1 and cnt2, then it contribute min(cnt1, cnt2) to the answer we can get initially, and abs(cnt1-cnt2)/2 to the answer we can get by operation, so the answer is sum(min(cnt1, cnt2)) + min(k, sum(abs(cnt1-cnt2)/2)).
C: We can maintain a priority queue. We scan the array from left to right, when s[i]>0 we push it into the priority queue, and pop an element and add it to the answer when some s[i]=0.
D: Let f(i) be the string after removing s[i] and s[i+1], then f(i)==f(j) (i<j) is equivalent to s[t]==s[t+2] for all t in range [i, j-1]. Therefore, let the initial answer be n-1, and each t that s[t]==s[t+2] will contribute -1 to the answer.
E: First check the trivial case when s and t are different after sorted. For a pair of (s[i], s[i+1]), if i>=k, we can swap them by:
(s[0], ..., s[i-k], ..., s[i], s[i+1], ..., s[n-1]) --> swap (i-k, i) -->
(s[0], ..., s[i], ..., s[i-k], s[i+1], ..., s[n-1]) --> swap(i-k, i+1) -->
(s[0], ..., s[i+1], ..., s[i-k], s[i], ..., s[n-1]) --> swap(i-k, i) -->
(s[0], ..., s[i-k], ..., s[i+1], s[i], ..., s[n-1])
Similar for i+1+k<n. So if every pair of chars can be swaped like this, which means n>=2*k+1, we can re-arrange the string arbitrarily. If n=2*k, we can swap (s[k-1], s[k]) like this:
(s[0], ..., s[k-1], s[k], ..., s[2*k-1]) --> swap(0, k) -->
(s[k], ..., s[k-1], s[0], ..., s[2*k-1]) --> swap(0, k-1) (we can re-arrange [0, k-1] arbitrarily since we can swap every pair in this range) -->
(s[k-1], ..., s[k], s[0], ..., s[2*k-1]) --> swap(0, k) -->
(s[0], ..., s[k], s[k-1], ..., s[2*k-1])
Finally, if n<2*k, there are some chars in the middle can't be moved, but we can re-arrange every movable chars like steps above. So we need to check every unmovable positions of s and t.
F: Bitmask. Let mask1(s)= the letters occurs odd times in s, mask2(s)= the letters occurs any times in s. Then (s, t) is a good pair is equvalent to popcount(mask)==25 && mask&mask2(s)==mask2(s) && mask&mask2(t)==mask2(t), where mask=mask1(s)^mask1(t). Therefore we can calculate the contribution of every mask[i]=(1<<26)-1-(1<<i) for i in range [0, 25] using a map.
G: Tree hashing. If the root has even number of childs, the hashcode of subtrees of these child must appear in pairs, and if the root has odd number of childs, there must exist a child with symmetric subtree, and the hashcode of other subtrees appear in pairs.
Tree hashing is very like string hashing, which means we use a integer to discribe a class of isomorphic trees. There are many different ways to implement it. For example:
We choose an arbitrary large number as seed (prime numbers are prefered).
For a tree with a single node, let its hashcode be 1.
For a tree with childs, we sort its childs' hashcode in non-decreasing order, and let hash[i]=size[i]+sum(hash[child[j]]*pow(seed, j)), where size[i] is the size of the subtree rooted at i.
By this calculation, for each i and j with isomorphic subtrees, hash[i]==hash[j] must hold, and if they're not isomorphic, hash[i]!=hash[j] holds by very high probability. To avoid hacks we can solve the same problem for several times with different random seeds (we could misjudge some testcases with answer "NO" to "YES", but all testcases with answer "YES" will be determined correctly).
Could you explain how to find the tree hashcode?
There's these two blogs on it. [Tutorial] Tree Isomorphism CSES and Hashing and Probability of Collision.
Particularly like the second one. Nice buildup and proof for bound on collisions.
Any good materials for tree hashing? I figured out hashing should solve this task but I had a hard time finding materials for it.
I did implement tree-hashing for the first time in my life by using some StackOverflow answer https://stackoverflow.com/a/58502389/6946362. But I had no confidence if it won't fail due to some hash conflicts.
thanks for this <3
in problem D why are you checking only two strings only lets say string is abcde possible strings are cde ade abe abc you are only comparing string 1 ,string 2 & string 2 , string 3 & string 3 ,string 4 why are you not comparing string 1 with string 4,why only adjacent strings only?
Because in string abcd, if ab==cd (f(2)==f(0)), then ab==ad==cd (f(2)==f(1)==f(0)) must hold, so we only need to check adjacent pairs: (f(i), f(i+1)).
Could you please elaborate on your F solution? How do you calculate this Therefore we can calculate the contribution of every mask[i]=(1<<26)-1-(1<<i) for i in range [0, 25] using a map. in O(n) complexity?
Let's fix mask and ignore all s[i] with mask2(s[i])&mask != mask2(s[i]). Let i<j, then mask1(s[i])^mask1(s[j])=mask is equivalent to mask1(s[i])=mask1(s[j])^mask, then #{i<j: (i, j) is a good pair} = #{i<j: mask1(s[i])=mask1(s[j])^mask) = occurence of mask1(s[j])^mask in range [0, j-1]. So we can use a map to store occurences of each mask1.
Thanks. I followed your description of F and upsolved it.
I implemented G according to your solution but it's getting WA on test 3. Could you or anyone else help me find the bug please?
UPD: I ACed using the seed that you were trying and optimizing the hash function.
First time to solve all the problems in Div.3 ^_^
(But without coding)
Talk is cheap.jpg
Finally solve till E2 :) .... Dream comes true lmao
same here !!
Too satisfying, aint it :)
Yeah, it is.
I think this round's problems where a little too easy for div 3 lol, but I love it. I think I'm hitting Specialist for the first time after this round too, so that's great
Bro can you plz explain briefly the idea behind your graph implementation for E1?
I think it's straightforward. Since you can swap any two characters as long as their indices have a difference of k or k+1, that means that a character can make its way to any spot that's "connected" to its current spot via the k and k+1 index difference. So you can create an adjacency list for every index (which contains at most 4 other indices by the way, meaning that you can even get rid of the adjacency list if you feel like it's unnecessary) and use it to find all the "connected components" where a character can possibly go with depth-first search (dfs). Then all you have to do is iterate over each character of the target string and check if there's at least one available character in the first string which can reach this specific spot via a connected component. Also I know this solution is a little overkill for this problem, but it's the first thing I thought of and I didn't want to waste too much time thinking about another one during the contest. I hope I explained it well
Thanks for strong E2 pretests! WA on test 20 was really helpful
D is very cute!
G: About rooted tree hashing
You don't need hashing, there is deterministic and simplier solution: for each vertex let's calculate the number, which represents equivalence class by isomorphic relation. To do so, we calculate these numbers for all childs, put them into a vector, sort it, then using smth like
std::map<vector, int>
we can determine the equivalency class for current vertex.But how to ensure right time complexity? We need to compare the whole vector and the worst time complexity for this kind of map is $$$O(n\log n)$$$.
Oh I understand. The sum of time spent on map is $$$O(\sum_v \deg(v)\log n)=O(n\log n)$$$ so the amortized time complexity is still $$$O(\log n)$$$. Nice solution!
This contest was easy.
Solution to E without any implementations
[solution]
I solved C1 with DP and I couldn't convince myself how PQ works on this problem. Take the case:
5
5 4 2 0 0
I see why it works now because we only have to return count but technically what happens if you simulated is that the first hero picks card 0 and the last two cards are discarded. I think if you had to return the cards that each hero picked in the answer, PQ wouldn't work right?
Yes, that was my concern too. But since we don't have to return the order of the picks, then we just need to prove that some optimal picking order exists such that you can use all of the max values before the 0s. I didn't prove it, but I didn't see why some optimal picking order shouldn't exist which implies the priority queue sum is optimal.
I think we could store pairs <value, card order no> in priority queue. PQ solution will then tell us which cards should be used. After that filtering, our task becomes trivial as we know exactly which cards will be used. We can recreate each hero pick on the second run with selecting only those filtered bonus cards (by using stack)
It is what I came up with, it might be possible of doing it in a single run through cards
E can also be solved with DSU. It can be done by merging all positions with distances k and k + 1 between them and checking for each connectivity component if set of letters on corresponding positions in s and t are the same: 195646722
I also thought it seemed similar to the classic number of swaps to sort problem. I wasn't completely sure so I wrote a casework solution instead but cool to see it works!
it's just 2 lines of code.. just need to check if each index maps to a valid index incase it's not similar to the character at the same location in the other string. you check my submission here -https://mirror.codeforces.com/contest/1800/submission/195634085
I hope you will upload some solution video.
already done. last time some youtuber and his subs started downvoting my comment so didn't feel like commenting here. but since you asked,
Problem A, B,C1,C2,D — https://youtu.be/cAtcgtNc6_U
Problem E1,E2,F- https://youtu.be/giVfpH16v-w
I don't know why but the recording is of a pretty bad quality today, I would definitely rectify the issue.
Good contest! A-F were smooth :)
Although I was able to solve A-F however I'm still trying to wrap around the fact that why would initialising the unordered_map elements make a difference.
This works -https://mirror.codeforces.com/contest/1800/submission/195719096
This fails — https://mirror.codeforces.com/contest/1800/submission/195719053
The only difference b/w the 2 being that in the working code I have initialised all characters to 0. Aren't unordered_map elements given a default value 0 when not present? I also tried explicitly checking for the members but no luck!
I would be grateful and really appreciate if someone could help me with this.
Thanks in advance :)
You are iterating through the frequency map with a for auto loop. When you check for a key that doesn't exist, it is created with a default value of 0. But creating a key while iterating through the map with a for loop is undefined behavior.
oh I didn't know this. thanks a lot. could you provide some reference material for this ?
This will be helpful.
https://stackoverflow.com/questions/10124679/what-happens-if-i-read-a-maps-value-where-the-key-does-not-exist
https://usaco.guide/bronze/intro-sets?lang=cpp
don't know how should i react knowing that I'm not alone :/ this thing cost me the entire round, I wasn't able to figure out how this could be wrong. I thought to move to other problems but B got my mind and i got stuck at it for long time. I tried many times changing the code lil bit but it didn't help and made me write a whole different code after wasting a amount of time in which i should've solved all the other problems i solved in the round. After the contest, I again came back to this, added few lines and got AC just to find out that it was all due to the uninitialized map............. Lesson learnt -> always initialize maps :)
Or rather just use vectors when working with finite set of integers/chars
What's the proof of C?
Can anyone explain why this approach works for D? I did testing on random strings in compare with brute force solution and could not find test that would break the solution.
1592B - Хемосе в магазинах Similar to E1 and E2 But I did not solve them, although I solved this problem more than a year ago
Isn't G a little bit easy for its position?
Depends on the person I would say. Idea definitely wasn't hard to find but implementation and execution might be hard if you're new to the concept. In my case I found the idea when there were 20 minutes left but had no idea how to correctly implement it.
1592B - Hemose Shopping
Similar to E1 and E2 But I did not solve them, although I solved this problem more than a year ago
Don't care about how many problems you solved bro. Keep your focus on learning and pushing your limits forward.
Personally, I learnt from E even though I solved it (virtually), I learnt from other solutions which used DSU. Some people also solved D using hashing.
I also found problem G interesting and I'm going to learn tree hashing.
What a great round!
God willing, the next one will be better
Thanks a lot for sharing the old question, had good practice solving multiple questions of the same type.
Pardon me!
Antihash tests? My solutions with unordered_map/cc_hash_table passed (task G), but gp_hash_table got TL on testcase3. And after making my own hash all is OK. UPD after systests. cc_hash_table gave TL. But unordered_map is fine
SO HAPPY !! Got a sub 1k rank for the first time ! Loved the questions
flunked very hard on E1 and E2, stuck for over 1.5 hours and could not solve them..
In my opinion, if a problem refers to many operations, sometimes it would be beneficial to consider the group/semigroup/set generated by these operations. May consider the properties of these operations, e.g., Do they commute? Are they invertible? Are they periodic (i.e., there exists an positive integer $$$n$$$ such that $$$a^n=1$$$)? Are they associative?
Sometimes drawing a graph helps.
thank you, i will keep this in mind and try to solve this problem again when i have time
Maybe try some small cases first.
Forgot to use
long long
for answer in C1 and C2, and I kept thinking I was using the wrong approach, so I couldn't solve either of them. Gonna fall to newbie now :(Regarding problem F, the time constraint for this problem is pretty tight,and the judge's behaviour is hence arbitrary. Check these submissions,195747465 and 195747315. I have submitted the exact same code twice, getting accepted verdict in one submission. Could someone suggest a faster algo, and hack this solution if this is'nt the intended one.
UPD: made it faster using hashing, fits well into the time limit now.
So interesting the problems are in this contest,I love this contest!but I think pretest in A maybe weak.
why my solution for problem A got hacked? qwq
Because it is wrong:)
For F task I got AC in java but getting wrong answer when i convert in to C++. Please help, i am new to C++
AC 195755004
WA 195754099
In your C++ solution, you forgot to check if
map[i] == 0
before incrementing values forvec[i]
. I believe you want to put values for the 0 bits inodd_freq
.Thanks a lot ankushkhanna, indeed I made a silly mistake and tried to debug for 1 hr.
I got AC, 195767362
in problem A , bad tests -_-
or bad code
painful reality
Has the system test finished? When will the rating update?
Why was that div3 round unrated for me? I'm under 1600...
just wait
hope this will make me expert
When will the editorial be out?
out
size up picture
late editorial :sadge:
How to prove the greedy solution of problem C?
Let's start with simplifying the problem. For each hero card we want to pick one booster card that appears before it. We may not use the same card twice. Heroes are interchangable because in the end it doesn't really matter which one gets which card. So, we traverse through the deck from top to bottom. Everytime we find a booster card we put it in a priority queue which shows the current best booster we can give to a hero. When we encounter a hero, we give them the top booster from the priority queue. We can do that because, at the end, we will have used a booster card at most H times where H is the amount of the heroes in the deck. Each of the cards is used in a legal manner (as when we consider a hero our priority queue only contains the cards that appeared prior to it). That means that if we choose the take operation for each of the cards we used in our final solution and the discard operation for everything else, we don't have to worry about the fact that you put the cards on top of the bonus deck beacuse we will have at most H cards and each hero will get one of them (Basically, we don't get any "garbage cards" that we don't want to use in the bonus deck. That means that the order in the bonus deck doesn't matter as we don't really care which hero gets which card as long as it's legal)
Thanks,bro
no problem :)
Why has this contest been removed from rating upgrades?