Привет, Codeforces!
В May/23/2022 17:35 (Moscow time) состоится Educational Codeforces Round 129 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Раунд основан на Межвузовской олимпиаде г. Саратова, поэтому просим воздержаться от участия тех, кто уже знаком с задачами.
Удачи в раунде! Успешных решений!
UPD: Разбор опубликован
Educational Round are the best for me, good luck for all participant <)(>.
Goodluck all participants <3
hope I become a specialist today !!!! :)
Solve 3 problems in less than 30 minutes of time.
don't expose the secret technique of speed-solving experts :)
okay...XD
plz bro can guide us how to do speed solving
Practice . I speedforces upto to D. Guess what ?? i will become expert today. Haha
Soml xD
I sometimes speedforce upto D. but average I can only do until B or C
When i was newbie i was only able to solve A and sometimes B. You are already ahead of me mate. That's great
Can anyone guess what the rating range problem C would be??
1400-1600
I mean there has been Cs with 2000 rating like robot collision from Edu round 109, so trying to generalize ratings of problems could get you stuck trying to solve a problem that is way harder than what you think.
I think it's like around 1200. Question difficulties have increased significantly to account for rating inflation.
Hope problems are less Ad-hoc and more algorithmic this time :/
Always love educational round.
I can not thank you guys enough. Thankyou so much for your efforts.
Educational rounds seems brainstroming to me. Does this happens to others also? But, Happy to attend these contest thinking one day these hard problems would be easy for me. Best of luck guyzz.
"Useful, even well-known ideas can be reused in order to introduce them to a wide range of participants;"
Source: https://codeforces.me/blog/entry/51208
For the love of back to back rounds. <3
Hope that I will not mess everything up again.
Hope you to become master and I can get specialist this round :>
Thanks!
Considering your rating history, I don't understory what you mean by "again"
Because of stupid mistakes like not opening correct array sizes or mistaking C for D,I lost 150+ points.
I might have got top 100 if I didn't.
TAT
Your messing up is equivalent of my best performance
I just lost my color.
HackingForces
...
Thank you for the contest
If the score is more than 2100, why do people with a score of more than 2100 participate in the ranking
Probably one of the best question sets I've seen this entire year!! However, I made one typo in question C which costed me 20 more minutes and 4 penalty attempts :(
Probably one of the best question sets this year!! However, I made a typo on question C which costed 20 minutes and 4 penalty attempts :(
Only solved A-C again :(
Maybe I should have a rest……
Relatable :(
D is just such a frustrating problem I hate it so much. Eventhough I solved it took me an entire hour to realize it is just a stupid bruteforce. it was not fun at all. so it's not your fault
How do you prove bfs will not time out though?
I did a bfs, but only took the 10000 highest numbers after each step. Have no proof that this yields always the correct answer (although I have a strong feeling that it does), but for sure this won't time out. (And just now I noticed, that I forgot to erase duplicate numbers. Uh-Oh...) 158202121
It even works if we take just the top 5 numbers after each step. I am a little surprised.
Maybe you will be more surprised tmrw morning..
'
That was my problem the entire time! but after proofing by AC I think you can prove it this way: so because multiplication is commutative (i.e. 5*3 =3*5) then the order of the digits you use doesn't matter. How many numbers you can multiply by so that the result doesn't exceed 10^n? not that many as you are only using digits between 0 and 9
Numbers which will increase x are from 2 to 9 in which prime numbers are 2,3,5,7.
So x will eventually turn into x*( 2^a * 3^b * 5^c * 7^d ) after some number of operations.
As we all know 2^63, 3^39, 5^27, 7^22 are all close to 10^19.
So 64 * 40 * 28 * 23 = 1648640 are the number of different numbers that can be made.
In this I have considered all the numbers which can be made using these combinations of prime to the power of some number. Which will not be the case in the real brute force implementation. It will close out at about 1e5 or so.
There's your proof.
Great! I think there is a tighter upper bound.
If we simply see that
(a + b + c + d) <= 64(considering a = 64, b=c=d=0). So, the numbers possible is found from this formula —(N+R-1)C(R-1)i.e(64 + 4 - 1)C(4-1)which approximates to47905.I think it's just the fact that it's Educational round. You can see my contest history, and literally from each educational round I consistently have negative delta. And they also have an "individual" feature of FSTing and a lot of hacks each time.
Educational speedingforces
Dude, really 6500+ people solved C?
Yeah, coz n^2 is also allowed
I fiddled like half an hour on a nice solution before realizing that stupid bubble sort also works.
lmao just realized this. I wrote a solution that uses a n queries at most. It was not much write though
actual selection sort.
Speedforces
What was the approach for D? Weren't we supposed to multiply the number by its biggest digit each time or I am wrong?
I solved it using maps and DP, not sure if there is a greedy solution for it
Proof that this wont give TLE?
Well, this will require a lot of thinking and tracing, and honestly, I'm not very convinced but I would say that since I'm starting with one number for example 123 and I want to try to multiply it by 2 or 3, no matter what is the result they will all be divisible by 123 so the chance of duplicates is very high.
no how does this matter? You can have so many numbers that are divisibl by 123 up to 10^19. it's
\floor{10^19}/123>= 1e^16. I think it has to do with the fact that you only use digits and that you multiplication is commuitative1. __This comment is nice. https://codeforces.me/blog/entry/103099?#comment-915079
I thought about DP, but wrote greedy which works in $$$O(2^n)$$$. (On every step choose from 2 different maximum digits). Surprisingly it got AC.
EDIT: Hacked :D
why the limit of 1000 ?
Just a number which is bigger than possible maximum answer (if we take 2 on every step, there will be maximum $$$log_{2}(x)$$$ steps.
lul.. that's why you should never reveal anything "surprising" about your approach while the hacking round is still going on.
No. My main mistake was to think about E/F tasks instead of resolving D in proper way, while I had a feeling my intuitive solution is wrong. Someone proved this, and it's good, I don't really care about color.
If you always multiply by the biggest number then you might exceed n
No this will never happen as each time you can at most increase the size by one. The problem with the greedy approach is that it might lead you to a number that has digits of low values, so it is the same problem with "good localy, bad globaly"
Thanks for the explanation
you can't even pass given testcase by that greedy approach..
No bro, the counter example is given in sample.
Yeah thats what I am saying. However Im asking about the logic overall.
In my head we get the best result while multiplying number by its biggest digit. Isnt it correct?
test case : 13 42
6 -> 7 is better than 9 -> 3 so you might multiply by a lower number at first in order to gain better number in the future
158229061 what should I add here?
123456789x9=1111111101 and you're stuck :D
What's the proof for C???
it's a swap so between any two indices so it won't take more than n steps. (unless I get hacked)
first forget about the values, after some swaps you'll attain a permutation of the indices so any permutation that works for both a and b is good, let us sort a first and then check if we can sort b without ruining the first sort(only moving elements with the same value), this process produces a new permutation and what's left is to check it
Thank you :)
I think today's contest was easy as compared to normal Div2 rounds
I spent 30 minutes thinking that C could be solved greedily, then I said let me just try to perform the K swaps no matter what, and it passed LOL
What was the idea behind E and F?
I used binary lifting in E. We just maintain the dp array of $$$jmp_{i,j,k,l}$$$ which represents the minimum distance moving $$$2 ^ j$$$ from the ith section first using the kth door of the ith section and ending up at the lth door of the $$$i + 2 ^ j$$$ section
EDIT: Sorry for being ambiguous in the original response
Binary lifting what, and in which problem?
You can use binary lifting for E, it's similar to the idea for BOI 2017 Toll.
Can you elaborate how do you count the binary lifting array?
I did it like how u would do initialize a sparse table
In E binary-lifting or $$$SQRT$$$-decomposition can be used. I tried the second but failed to make it accurate and correct (as usual).
God damn it! So everyone knew how to solve F except me. I lost my chance to became Master.I'm so sad now....................
similar nickname，same hacked on Problem D :(
Can anyone hack me? Unordered map Your text to link here...
How to solve F?
You can consider each $$$x$$$ separately. You can compress nodes connected by non-$$$x$$$ edges to get a new tree for each $$$x$$$. A pair of nodes $$$u, v$$$ has $$$x$$$ as a unique occurrence only if $$$u$$$ and $$$v$$$ belong to adjacent nodes of the new tree of $$$x$$$.
To build the tree efficiently, iterate through all original tree nodes in decreasing order of depth and simultaneously build all the new trees. When you encounter a node $$$u$$$ for which the edge connecting it and its parent has value $$$x$$$, search for all components of $$$x$$$ already existing within the subtree of $$$u$$$, and join them to get a new component of $$$x$$$.
What's the intuition behind D??
Use Breadth-first, a multiply x with every digit and take care of duplicates and also manage edge cases like if x=1 and n>1, ans=-1
length(x) can't be > n because x < 10^(n — 1)
Thanks , edited
I used dp, where dp[i][j][k] = max number after i steps lastly multiplied by j and has k as digit
Number of steps can't be more than 30, checked it with greedy
I used memoized search: https://codeforces.me/contest/1681/submission/158228515
In task D, How to know that memorization in a map will not exceed time limit?
I also used the map, but it passed the pretest. I hope it will also pass the system test
Even if you multiply by 2 everytime you will reach n digits extremely fast. This along with the fact that you can multiply by only 8 distinct number assures that the number of
statestransitions are actually quite small.no it does not. If you can multiply 8 distinct digits to get 8 distinct products, that has a very high upper bound. The map solutions have passed as the number of "distinct" numbers encountered, the "X"s are limited. That is different from what you meant to say.
Edit: Explanation below makes more sense.
You're right. I believe the 8 numbers fact is more prominent in a way that it limits the number of transitions from one state greatly.
Just notice that any value $$$y$$$ that will be reached can be represented as $$$y = 2^{\alpha}3^{\beta}5^{\gamma}7^{\delta}x$$$ and realize that the total possible combination of the quadruple $$$(\alpha, \beta, \gamma, \delta)$$$ is loosely upperbounded to $$$log_{2}z * log_{3}z * log_{5}z * log_{7}z = 60 * 40 * 26 * 21 \approx 1.5 \times 10 ^ 6, z = 10 ^ {n - 1}$$$, but obviously didn't prove during contest
EDIT: Made the explanation a bit clearer.
Trash E.
It only takes me 5 minutes to manage out a way to solve it using something like Matrix multiplication and Segment Tree or binary lifting.
But there are TOO MANY GOD DAMN DETAILS that I failed to accept it before the contest ends.
I hope there will be more brain-consuming problems (maybe greedy or constructive ? ) instead of such complex and meaningless ones.
+1, the detail are nightmare to follow, I kept getting WA on test 5 :(, but since it's and edu round it completely deserves to be their.
I use DFS to solve problem-D, but get TLE. :D
158223688
You need to use memoization to avoid visiting the same values multiple times (which can happen).
yes, it should use memoization, so BFS + memoization, not DFS + memoization.
I used DFS + memoization. Worked ok. I guess you could try to hack me :)
oh! I get AC with DFS + memoization 158229644, but I think BFS is more better, because if DFS always meets bad answer firstly, then memoization does't work.
Well, as I say, I used memoizaton and haven't been hacked yet. Why do you think it doesn't work?
I simply called a 'bad' answer very big (1e9) and then said if my final answer was >= 1e9, then output -1.
Hi @jimm89. I tried DFS too. Got TLE. Used memoization and it worked. Its kinda weird that you need memoization for this. I initially thought the probability that you will encounter a value you encountered before is so low. I thought the overhead for using a map would harm more than it will help but it is the other way around :-) I was just curious if I will need memoization for BFS as well.
I expect you would not need memoization for BFS.
I saw that tourist submitted a DFS solution with no memoization, but with sufficient pruning so as not to TLE. I suspect he knew it would not TLE, but did also wonder whether that was due to instinct from vast experience or whether there was some underlying (very fast) deeper thought process. Effectively the solution tries 'higher digit' paths first and then also eliminates any path which could be longer than the current best answer.
For that reason, I am confident that BFS is fine without memoization, since you will only visit paths shorter than or equal to the best answer.
Can someone share the approach for problem F ,how to solve it using disjoint sets
you may google "dynamic connectivity problem (offline)"
Why are there orange people in the official standing?
Can we solve F using smaller to larger technique ?
Yup https://codeforces.me/contest/1681/submission/158217933
Can you explain exactly what are doing in your code ? and what will be the time complexity ?
what is smaller to larger technique? can you refer any blog?
tanjim54
https://codeforces.me/blog/entry/67696
What a bullshit D.
If I solved that shit, I would achieve performance of IM because I solved ABCF before. But now I even lost my rating.
First time solved 4 problems in div 2
What the meaning of D? I can't imagine the reason to put a rubbish standard dfs in the place of D.
Is it so hard for you to simply delete this problem? I can come up with hundreds of problems like this.
And for the difficulty, many people can't solve it just because they aren't dare to use such a stupid method in fourth problem. Why not put it in the place of A?
that's sums up my feelings. If this was C, people would have done it faster and lots more people would have solved this.
The point of D is to be a problem on implicit BFS/DFS/dynamic programming where it's not so obvious (but easy to prove) that the solution is fast enough. I don't think that your claim "they don't dare to use such a stupid method" is correct; proving that it works is not difficult.
I would guess that most the people who solved it didn't actually prove that the number of states is small enough.
It is true that the dfs solution can be proved to be fast enough. However, this is a programming contest, not a math contest. Most people who passed this problem during contest didn't think about what the complexity will be, they just tried dfs and it worked. The aim of the problem is to separate people who can come with a method and who can't, not "Here is an easy way to solve the problem. Can you prove it?" This way it will be more like a math problem. The proving part is important but that's not something that should be asked in contest.
You say "Here is an easy way to solve the problem" as if it's written in the problem statement that you should use DFS/BFS/something other there. I agree that this problem is on the easy side for ER D, but I don't think it's C level.
I don't see anything wrong with some participants guessing that the method works without any actual proof. This is fairly common even on high-level contests. As long as the proof doesn't take five full pages of formulas (I mean, it's definitely possible to come up with the proof in a short period of time), it should be fine, in my opinion.
I am not familiar with what the difficulty of ER D should be, maybe some of my opinions are biased. I am just expressing my confused feeling after solving this problem.
Actually, I would really appreciate if the problem is changed to "Count how many different numbers $$$\le N$$$ could be reached by using this function."
By the way, I do think that the problem statement directly points to the dfs solution because that's just something everyone will come up with after seeing the problem.
Judging by the results of our local competition where I used this problem yesterday, it's not the case. Some of our students definitely recognized a graph problem fairly quickly, but not all of them, even those who are kinda familiar with DFS/BFS.
In fact I used pruning instead of memoization. 158184259
This shows another problem: you can get accepted using whatever approach you want as long as you dare try the easiest dfs.
So, I think his claim "they don't dare to use such a stupid method" is totally correct since I don't think a lot of people actually proved it. The people who solved it are probably just like "okay, let's try dfs. Test 19 42 and the answer came out immediately so submit!"
This way of thinking is definitely not good for ER D.
Kind of sad that $$$O(N (\log{N})^2)$$$ approaches passed in F.
I initially had an interesting $$$O(N^2 \log{N})$$$ solution where I run a re-rooting DP on each edge weight separately, to calculate contributions of that edge weight (a range sum data structure was used for this, thus the log factor). I sped this to $$$O(N \log{N})$$$ by using the DFS times for each node and simulating the DFSs for each edge weight by just looping along occurrences of each edge weight in the DFS order, using only $$$O(\text{occ}(x) \log{N})$$$ for each weight $$$x$$$, where $$$\text{occ}(x)$$$ is the number of occurrences of $$$x$$$.
Edit to add:
Since people seem confused, I will explain my solution in some more detail. Firstly the $$$O(N^2 \log{N})$$$ idea. First root the tree arbitrarily. Now, we find the contribution for each edge weight separately. I will describe how to calculate the contribution of edge with weight $$$x$$$.
Notation:
$$$\text{comp}(u, x)$$$ is the size of connected component of if only edges with weight not equal to $$$x$$$ are considered, $$$\text{sz}(u)$$$ is the size of subtree of $$$u$$$, $$$\text{par}(u)$$$ is the parent of node $$$u$$$, $$$\text{anc}(u)$$$ is the set of proper ancestors of $$$u$$$, $$$\text{sub}(u)$$$ is the set of nodes in subtree of $$$u$$$.
Define $$$\text{dp1}[u] = \text{comp}(u, x)$$$ if the parent edge of $$$u$$$ has weight $$$x$$$ and $$$0$$$ otherwise. Similarly, define $$$\text{dp2}[u] = \text{comp}(\text{par}(u), x)$$$ if the parent edge of $$$u$$$ has weight $$$x$$$ and $$$0$$$ otherwise.
How to compute $$$\text{dp1}[u]$$$? Some careful thought yields:
and
With these expressions, $$$\text{dp1}[u]$$$ can simply be computed with DFS and a range sum data structure (on the Euler tour of the tree). After computing all values of $$$\text{dp1}$$$, the $$$\text{dp2}$$$ values can be computed with DFS and a range sum data structure, noting that $$$dp2$$$ value of a node $$$u$$$ will be used when $$$u$$$ is an ancestor and $$$dp1$$$ otherwise. So, these values can be switched in the range sum data structure during DFS.
Contribution of weight $$$x$$$ is simply $$$\sum \text{dp1}[u] \cdot \text{dp2}[u]$$$.
How to make this $$$O(N \log{N})$$$? Well, since only particular $$$dp$$$ values are ever non-zero for a weight $$$x$$$, we can simulate the entire process by just looping over the positions of these nodes in the DFS order.
Code: 158206764
samjh nhi aaya pr sunke aacha laga
I initially had an interesting $$$O(N^2 logN)$$$ solution where I run a re-rooting DP on each edge weight separately, to calculate contributions of that edge weight (a range sum data structure was used for this, thus the log factor).
You can improve this solution to $$$O(N)$$$.
Oh yes, somewhat painful, but can be done.
I am trying to Solve Problem F using centroid Decomposition.
Timecomplexity should be : $$$O(N(\log(N)^2)$$$,But I am getting TLE on TestCase 45.
MySolution:158262510.
I have $$$O(n)$$$ solution of F
For each value of $$$w$$$ from 1 to $$$n$$$, break all edges which have weight $$$w$$$. The tree will break into connected components. Now for each pair of "adjacent" connected components(i.e. components which were connected by the broken edge) you need the number of paths starting from one component and going to other. If we store everything in dfs order, then this can be accomplished in $$$O(n)$$$. It is not that painful but my implementation is a bit messy.
https://codeforces.me/contest/1681/submission/158273456
Problem D was so frustrating. Still can't figure out why DFS would work?
Also, can anyone point out what is the issue with the idea of always multiplying with the largest digit in X? This should give the largest possible number in some number of moves, right?
I initially applied DFS but it was giving WA on test 3. Tried BFS and it worked
But why did it work? From what I can think of, we have 10 different possible states to go from each number. Talking in terms of Tree DS, we have a rooted tree of depth ~20 and each node has 10 children. This leaves us with around 10^20 leaf nodes.
Is that even possible to solve?
Is there any special structure to the problem which is not considered in my analysis?
I donot know how to prove it but it got ac. I think some values will repeat in sequence so you do not need to process them, and hence the solution will pass in time. I tried to test it, at max only "4833" values were inside my queue when it reached level 19.
158229061 what should I add for this D problem submission so it will work? Or at least give TLE..
Note that it is not always optimal to multiply by the largest digit every time.
See this comment (and maybe work it out on paper too).
But that’s basically what dupl vector and for loop is for. Am I wrong?
Yes -- it looks like you are keeping track of what digits appear in a single current number and then picking a digit to multiply by based on what maximizes the next number.
What I am saying is that this decision of taking the largest of the results is not globally optimal.
The contest is nice but there are plz skip them ... bcz problems A B and C are in Youtube !
wdym problem are on youtube?
Yes ! U can find them easily
Link?
https://www.youtube.com/watch?v=hTl-ALbHdog https://www.youtube.com/shorts/MqYzcHaGekw
I think I solved E during contest but was lazy to implement (though might TLE in theory). Tell me what you think.
I looked at the doors as a layered graph. Each layer has 2 nodes (doors), and there are only edges between nodes of adjacent layers (the distance in the matrix between the doors of consecutive layers). So in total there are 4 edges between 2 layers.
Now for the preprocessing, I want to calculate the distance between the doors of special layers (0 with 300, 300 with 600, 600 with 900). I'm using 300 but actually I would take sqrt(10**5).
This is a simple DP such that in the end each node in each layer has a pair (d1,d2), where d1 is the distance from the first node (corresponding to top door) in the previous special layer, and d2 is the distance from the second node (corr. to right door) in the previous special layer.
Observe there is never any need to travel back and forth between layers. Only one direction.
So now, assume I get a query (x1,y1), (x2,y2). Suppose the first is in layer i, and the second in layer j. All I need is to calculate the distance from x1,y1 to both doors in layer i, then. Then use my preprocessing to calculate the distance from doors of layer i to both doors of layer j (4 distances), and then calculate the distance from both doors of layer j to (x2,y2).
This could take up to 900 operations per query (300 for layer i to special naively, 300 for special to special using preprocessing, and 300 for special to j naively). But notice that if you do the preprocessing in both directions, this can be done in 302 operations per query (the distance to the next/previous special layer can be done in one operation).
Of course this isn't really 302, but more like 302 * 4? (because every calculation I consider 2-4 different options?). So it might be TLE, but it might just work. I'll probably try to implement later and see ^_^
Yes, it is called SQRT-decomposition and should work with $$$10^5$$$, but as you noticed, it depends on realization.
It's better to make some const $$$X = 300$$$ and use this value for pre-calculating, calculating an answer. Then you will be able to play with this number to get the best result (usually it's less than $$$\sqrt{N}$$$, about 250).
P.S. I think $$$6s$$$ time limit was done specially to pass such solutions.
Oh didn't notice the 6 seconds! Thanks for advice :)
Is it possible to solve $$$F$$$ using centroid decomposition? I tried to write it, but couldn't do it in time and don't know, will it work.
Also, has anyone noticed, that during contest "cses.fi" went down? I only loaded my submission there for a centroid decomposition problem, and after several minutes the site stopped working.
Yes. But not a good implementation though.
https://codeforces.me/contest/1681/submission/158227788
I can't control myself to complain the weak pretests of problem D. A way to express this feeling is to hack myself :(
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.
If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
Could you please a provide a failing test case for 158212087. It got hacked.
please try to hack this one , my solution is already hacked , i just want to confirm whether my new solution is correct or not. link-158229941 thanks in advance.
Hacked with Ticket 7282
For D why a DFS with memoization works? From any starting number x you just multiply it with {2, ..., 9}, and there are only 4 prime numbers in that set: 2, 3, 5, 7.
That means you actually just multiply x with those four prime numbers and in the worst case you start from 1 and use 64 multiplications with 2. But some of those 64 multiplications can be 3, 5, 7 as well. So that is really at most 64^4 (imagine you divide 64 positions into four segments for 2, 3, 5, 7). The real number will be much smaller because for 3, 5, 7 you probably don't need 64 multiplications.
SpeedForces, in two consecutive days QAQ SPEED IS NOT MY FORTE It's shocking that a D problem can be solve by brute force?? I'm trying to do recursion or dp, without even thinking that this problem can be sooooo easy! and I am sad that I mistake $$$bj$$$ to $$$bj_{th}$$$ in problem B.
and I am sad that because my func for sort() returns false when two elements are equal, I received 3 Runtime Error..
You're not alone being sad. lol
My only bug on E was forgetting to initialized my binary lifting array with INF...easily the stupidest bug I've made out of not solving one of the hardest problems in a contest
I also find it kind of funny that samples didn't even catch this bug
I solved problem D using recursion + memoization. only prime numbers which will be multiplied by x are only 2,3,5 and 7 and each prime number occurrence will not be more than 60,40,24,28 respectively. so we can memoize the count of each prime number.
awoo my 1st submission on D is wrong on sample test case 2, then why I am getting a penalty when my solution is wrong on the sample case? Isn't sample test cases free of penalties?
Only the first sample is free of penalties.
nice pfp
Can solve F more directly using a dynamic tree supporting subtree aggregates, such as this. Just cut/compute/link the edges for each color.
I solved problem D with a dp approach. https://codeforces.me/contest/1681/submission/158204160 dp[size of number][mask][distance from the original X] = max number with this mask.
I have a mask of all of the digits that are present in the number.
So if I have a number 1434, digits 1 3 4 are present and current mask is equal to 2^1 + 2^4 + 2^3 = 26
I used an assumption that if we consider all of the numbers with the same size and mask, we should always pick the biggest one. I am not sure about this assumption, I was not able to prove that is really always profitable to always pick the biggest number.
My approach was similar to you; however, I didn't used mask but one of the digits existed in that number. "Wrong Answer on test 13 T_T"
why this recursive solution to problem D doesnt work? link
from a rank of 2000. to a rank of nearly 6500. after a solution get hacked is worst feeling ever for a coder. why don't they make proper pretest
hacking is a part of educational round.
used 3 hours to solve F with smaller to larger technique and get passed 2 hours after the contest. Made so many mistakes to count the number and contribution. Anyway, next time I might be better. How will you rate E and F?
try hacking this 158235750
Me: struggle with all my might in yesterday's round #793, solving one task for the entire contest, -131 rating
Also me: solve ABCD in the first 26 minutes today and run away to work because I didn't have time for this shit from the very beginning. Predicted rating +203
I'm stable like a stablecoin
Interesting. Perhaps you should always do contests before your work, so you can push yourself to solve problems very fast and then you can run away to work :)
(of course, just kidding)
Question D, if you use dfs to solve this problem, pay attention to this, if the front is 2 and the back is 4, the number of steps *2*2 will be more, but *4 cannot enter because it has already accessed this number
WHat?
Nice tests on E without
intoverflow, did some hacks with it.Can somebody please explain C ?? also, i wasn't able to solve 'column swapping' in Round #794 (div1 + div2) , these are similar, right?? i think just saving the swapped elements in arr / vector was the difference.
And they say time travel is impossible
I really amazed about problem D! how a single bfs with visit array make this code accepted without TLE, what is the time complexity of the previous code? or there is a failing test case which make it TLE?
deleted
I think D problem in this round is most hacked problem I have ever seen till now. It has changed so many rankings up and down. As I have also hacked 7 submission of D problem.
whats the testcase? my d also got hacked. https://codeforces.me/contest/1681/submission/158189337
you can see testcase on which your solution was hacked under show judge protocol option.
but where to find that option
You have to go to your submission by clicking on # button.
It is 12 10000000000
whats the hacking testcase for D? https://codeforces.me/contest/1681/submission/158189337
System test has already passed ?
I am wonderning too ??
same question
I'm not sure if my assumption is correct, but if the new test cases will be added to the original ones then the answer is no because problem D is still showing 66 test cases, which is the number of the original test cases.
why you think new test cases won't included and no re-run the system test again.
What I meant is that if the new test cases will be added to the original ones this means that we will have a number > 66 test cases for problem D and I can still see that problem D has 66 test cases, and if I'm not mistaken then they didn't run the system test yet.
Gotcha, thanks
Is rating calculation still going on or it has been decided to become unrated even for Div. 2?
After participating in almost 5 educational rounds you haven't realized that this series of contests rating always come late??!
Yeah it was late on previous contest but I didn't check the graph on those contest.
Since it displayed as "unrated" on my graph so I was wondering if some new announcement was made.
When will the tutorial open? The hacking phase is over ig
same question
System testing is in progress now, it should take a while.
Why so many downvotes?
I think it's because peoples are waiting tutorial/uprate too much
Even my grandma runs faster then the rating update system. Lol XD
desperately waiting for the rating update
When you wait for the rating change:
Me who is going to become expert right now. Having a lot of adrenaline rush. Can't wait anymore now .
Me too.
Bro Your graph and solve count is so inspiring . You must be my friend . I have made you my friend . :_:
Thanks! I made you my friend too.
I think your graph is so inspiring, too.
If someone is going to be an expert, it must be you. XD
I didn't like my graph at all because I got stuck in gray and green for long period. But seeing you guys saying that my graph is inspiring really made my day! Thanks!
Me as well. :)
yeah, holy crap. Lots of effort, you definitely deserve expert!
Thanks!
Bro prioritize upgrading the grand warden.
Yeah this was my first thought too ...
it's an outdated pic, hes like level 11 or smth now
My dad has returned with the milk already.
so drink that and have asleep
I Think your don't get the Joke. Is's the classic british Dad joke.. Google it :_:
Yeah, I got that.
The blog now has -1 votes , 5m earlier it had 1 upvote.
-1 votes right now, and it keeps decreasing.
MikeMirzayanov awoo submission 158171922 and submission 158186561 are nearly same and its a pure co-incidence neither i know the person nor i used any online IDE and question was pretty brute force so its obvious to have same kind of solution and further more I have no history of such offence and i personally hate cheaters . This kind of things demotivates a lot please look into the matter.
Idk why ppl are downvoting this contest . I find Task great . Just because of fst ??
#define fst plsI got my ans similar of C to somewhat 100 people; tell me it isn't possible that too many people do the question with the same approach? IDK why my answers are being skipped. I did not use an online IDE or something that would leak my code. It's too bad; after 2 hrs of brainstorming, you just skipped my question, with no-fault. It is a correct ans, and that's why so many people have the same approach. awoo MikeMirzayanov adedalic BledDest
Exactly its a simple solution and many people can have it
Codeforces is considering me responsible for the mistake that I have never made.Actually I was sitting in a public library while competing in this round.I guess someone has copied my solutions by continously peeping into my laptop without informing me. I have not indulged myself in any such activities and I always beleive in right conduct.For reference you can check my submission timings and code. I beleive codeforces won't do injustice to me.
aren't you responsible for keeping your code safe?
I finally become expert after 1 year . Cheers
congratulations
Thanks Bro . You too for becoming cm!!
me too.. after 5 months
Congratulations!
Thank you Brother !!
Congratulations, well deserved. :)
How on Earth did I pass pretest with accidentally typing "int" in memoization for D task?
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Can anyone tell why I haven't received the ratings for this contest yet... I am in div 2 (920 ratings)
Your Last rating change was +13, after this round. So, you're
Well, finally i got my color back. Now i need to get back my rating! xD
awoo MikeMirzayanov Yestarday, I recieved a letter from Codeforces System in which it was written that my solutuion 158183564 is similar to Boboge's solution 158175797. We weren't communicating with each other. It's just an coincidence. Both of us used simple implementation of classic bubble sort and well-known C++ STL functions. Please, review your verdict P.S. I didn't use any online IDE, just CLion.