Привет, Codeforces!
Благодаря поддержке Neapolis University Pafos, продолжается серия образовательных раундов. Университет предлагает получение степени бакалавра в области компьютерных наук и искусственного интеллекта со стипендиями JetBrains. Получите передовые навыки в области искусственного интеллекта и машинного обучения, которые подготовят вас к востребованным техническим карьерам. Любопытно? Ознакомьтесь с учебной программой прямо сейчас. Доступно ограниченное количество стипендий. Не упустите свой шанс учиться в Европе бесплатно!
Ищете способ улучшить свои навыки и увеличить шансы на получение стипендии? Присоединяйтесь к бесплатным клубам для старшеклассников от JetBrains:
В 14.10.2024 17:35 (Московское время) состоится Educational Codeforces Round 170 (Rated for Div. 2).
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов, Александр fcspartakm Фролов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Данный раунд частично пересекается по задачам с квалификационным этапом Чемпионата Юга и Поволжья России. Если вы участвовали в этом соревновании, то воздержитесь от участия в раунде.
Удачи в раунде! Успешных решений!
UPD: Разбор опубликован
It feels really good to be the first comment
it feels better to be the first reply of the first comment
funny how almost similar comments but the better color dude has much higher upvotes
or maybe "first" comments are stupid, so people upvote comments making fun of "first" comments
I think so.
Hope the contest will be fun and educative :)
Score distribution ??
there is no score distribution in educational rounds round will be held on ICPC rules
ok.. Thank You:}
How much +(Plus) will I get if I solve 3 problem in 1H...
How much +(Plus) will I get if I solve A-B-C within 1H??
It depends on many things like other peoples performance, your accuracy etc. So hard to tell.
Why are people giving downvotes to programmer5777
pta nhi bhai
Two contest on same day for me.
Two contest on same day for me.
Why the recent Educational Rounds were removed from Harbourspace?
I thought that there had been a logo on the top-left of the page.
Two contests on my birthday! Cool!
Happy birthday!
Thank you!
Happy birthday!!!
Thank you!
happy birthday
Thank you!
Happy Birthday!
Thank you!
Happy Birthday
Thank you!
wow special
As a participant.....
As a problem writer, I feel it is important for me to mention that problem D is going to be an interactive binary search tree problem.
Well what's the score distribution? Can you please update the post and add score distribution?
as a writer, its 69 — 69 — 69 — 69 — 69 — 69
its standard icpc, there is no score. Every problem is worth 1 point and tie breakers are resolved by looking at penalty time
Ohh, Thanks
Hope to become pupil after this round :p
As a joker, I'll get lower rating!!!
Hope you all have LOWER ratings after participating this round!!!
nooooooooooo！！
LOL! The profile dp and the votes on the comments
Last night/Early Morning contest Messed up my sleeping pattern. I desperately want to participate, but at the same time my mind is sleep deprived.
pupil in this round In shaa Allah!
yesss
I solved D but not able to solve B and I end up with 7k rank.
I won, but at what cost?
How did you do D?
Lets do DP. Let N be the number of 0's.
Define dp[i][j] as: we are at the ith 0, and we already have j intelligence points.
Now the current point can be an intelligence point or a strength point.
If we take intelligence point, we will have (j + 1) intelligence points and i — 1 — j strength points. Now find how many rounds you can win (you can do this by storing the positive and negative numbers from current 0 to next 0 and upper_bound over it).
So the transition becomes dp[i][j + 1] = max(dp[i][j + 1], dp[i — 1][j] + wins)
Or if I take the current 0 as a strength point, we will have j intelligence points and i — j strength points. Again find how many rounds you can win (same way as before).
Again, transition is dp[i][j] = max(dp[i][j], dp[i — 1][j] + wins)
Finally, ans = max(dp[last_0][intelligence_achieved])
can you explain how you calculated wins in more detail please?
First, for every
ith0, store all the positive and negative numbers fromith0 to the next 0 in a list. Call itcnt[i][0]for positive numbers andcnt[i][1]for negative numbers (take absolute value of the negative numbers and store)Later, when you do DP, at
ith0, if you havexintelligence points andystrength points, you can upper_bound overcnt[i][0]forxand see how many rounds you can win. Same fory, upper_bound overcnt[i][1].what if we can also win some more rounds after the i+1th 0?
We don't know what point we will take at the i+1th 0, when we get there, based on our calculated DP states we will decide what to do.
This is exactly same of what I thought, but the implementation was a bit difficult for me. Bad luck!
Found it nvm
its a very trick observation don't worry
you needed to observe the pattern, took 30 mins away from my clock :(
what is the soln for D ? i tried DP but TLE'd 285921797
DP optimized with binary search 285875242
UPD: If you TLE'd, you probably didn't split the Attribute Checks into sections. If you split, you get worst case of $$$\displaystyle \mathcal{O}\left(M^2 \cdot \log_2\left(\frac{N}{M}\right)\right)$$$ instead of $$$\mathcal{O}(M^2\log_2N) $$$
i did this and TLEd. unlucky ig
same i also dp + BS but tle how can we further optimize??
Don't really need binary search, can just go over all positions, update dp only at zeroes and keep count of each check level to the right from the current position 285916481 so it's O(n + m^2) total.
any idea why is this getting TLEd
i think the overall complexity should be (m^2 + n)
https://codeforces.net/contest/2025/submission/285979006
nvm i found my mistake ... its actually m^2*n
Did you write recursive DP?
My code with same approach using recursive DP (285888018) TLEd, but with iterative DP (285891738) got Accepted!
i wrote iterative dp :(
My iterative dp + binary search failed while iterative dp + prefix sums passed :(
U might need to solve it again
my recursive dp got accepted but may be chance of hacked 285918445 2.3s
Nice one. I did exactly the same but failed to implement :(
wow thats fascinating
How did you calculate time complexity? I think my solution is same with yours, they have close time, but I can't find what time copmlexity of my solution is. 285897223
It's the same complexity $$$\mathcal{O}\left(M^2\log_2\left(\frac{N}{M}\right)\right)$$$. In the worst case, all $$$N$$$ checks are split evenly among the $$$M$$$ sections.
Then, isn't the time complexity $$$O(NlogN + M^2log(\frac{N}{M}))$$$? And it's ~$$$2.6 × 10^8$$$(TLE?), but I don't now if we have to include $$$NlogN$$$, if don't it won't be TLE. Or is it $$$O(Nlog(\frac{N}{M}) + M^2log(\frac{N}{M}))$$$, if so it won't be TLE(?).
You're actually not sorting the entire $$$N$$$ checks in a go, but instead section by section too. Without this consideration, it seems like your complexity right, but consider this: If the first part is $$$\mathcal{O}(NlogN)$$$ (ie all checks are in the same section), then the second part is actually going to be $$$\mathcal{O} (M^2+MlogN)$$$ which is quite fast. But if all checks are spread evenly, you get this (slower) complexity instead: $$$\mathcal{O}\left(N\log_2\left(\frac{N}{M}\right) + M^2\log_2\left(\frac{N}{M}\right)\right) \sim 2.3 × 10^8$$$ operations.
Constant factor is important too. TL is also 2.5 secs, so it won't TLE.
I did with Fenwick tree, a dp would need to loop $$$m \times n$$$, which shouldn't be fast enough.
It is DP only.
For each Incrementing Point ( where a[i] = 0 ) , check what gives you most benefit ? Whether to take this as strength increment or intelligence increment.
i mean i did that , but my complexity is mxn which is horrible
My Solution is m^2logm but still tled
Link: https://codeforces.net/contest/2025/submission/285908603
How to further optimize it??
I used linesweep for O(m^2 + n) and barely managed to scrape through.
Solved that with an approach with the same complexity and got TLE at Test Case 5, probably because of Python.
You can store the indices of values in lists (like $$$list[arr_value] = indices$$$) and use a pointer to keep track of how many have passed since the pointer will always be increasing.
you can use difference arrays to optimize dp
can you explain more please ?
you can compress data and use simple prefix sums for calculation.
UPD: nevermind, it's about C.
I did just two suffix count arrays of sizes m+1. Then i do dp on each zero and if I take +str count number of elements with new str on suffix and calculate new values for suffix.
You can store the positive and negative numbers from every 0 till the next 0 in a list, and for a fixed no of intelligence and strength points, you can upper_bound on the list to find how many rounds you will win.
yah i see, thats smart unlike me
Just keep a suffix sum of the number of times a check with value x occurs after the ith point you get. Total time complexity is O(m^2 + n) 285984080
F is the same as https://codeforces.net/problemset/problem/405/E .
Also the same as https://codeforces.net/contest/860/problem/D
I was thinking about this problem when solving F, but F has multiedges Even Outdegree Edges
Upd: easy to adapt and worked for this F too, almost the same code I made for the above problem, just try to define the direction greedily in DFSTree, if outdg is 1 for the current node, change edge to its parent and update the outdg of parent node. if orientation is 0, then choose xi, else, choose yi. 285931982
2nd question sequence
Can someone pls help me understand why my code for (C) gave WA on test 2? Not able to figure it out. Thanks!!
285922242
my m^2logn dp TLEd in D. bruh moment
O(n^2) can't pass Problem D easily and need exhausting optimization. Time limitation tooooo strict.
You need to write O(n log m + m^2) for D instead of O(n^2)
O(n^2) can't pass 2*10^6 for sure.
Sorry i mean O(m^2)..
Fine..For python, create new counter(defaultdict) after updating dp array will give TLE. Use .clear() instead.
If $$$O(m^2 * log(n))$$$ can pass how does $$$O(m^2)$$$ not?
Don't know..Maybe create new variables for 5000 times is too slow for this.
[https://oeis.org/search?q=1+2+1+2+4+1+2+4+8+1+2+4+8+16+1+2+4&language=english&go=Search]
What's the intended time complexity for D? My O(m^2logn) passes.
mine doesnt lmao.
$$$O(m^2 log n)$$$ seems like a lot.
I think
O(M^2+N)https://codeforces.net/contest/2025/submission/285927740 anyone knows why this TLEs? i saw some people doing the same thing :(
I tried to make an vector of vectors
srswhere all the continous segment are present and did the sliding window to check the max I can pick withkdistinct, can any one point out where Its failing. thankshttps://codeforces.net/contest/2025/submission/285927740 anyone knows why this TLEs?
mine is MLE :) https://codeforces.net/contest/2025/submission/285924484
wow, it got passed after I changed long long to int
I think submissions should be rejudged for D with less strict bounds if O(m^2logn) cannot pass... Even my O(m^2 + mlogn) code barely runs under the time constraint...
Was about to get excited until
Wrong answer on test 8on D, well fml then I guessSame here, please post test case if you find it
Please try this:
5 4 0 4 0 0 0AC, wasn't handling transitions propperly.
This is supposed to yield 0 right?
yes of course. I just hacked myself with this small case to pass test #8, but it seems that #8 is just generally stronger than the previous ones to detect various mistakes
In problem E, I wrote the solution such that:
I started on first suit and define if I take first j cards, so number of ways if C(m, j) * ways[m — j][(m — j) / 2] which ways[i][j] is number of ways to divide i element to 2 parts
When I took the transition of the dp, on next suit, if I had j cards from first suit, I can use x of them to beat any x cards so I have to mul C(m, x) * ways[m — x][(m — x) / 2]
So the transition of f[i][j] from i to i + 1 is: f[i + 1][j — x] += f[i][j] * C(m, x) * ways[m — x][(m — x) / 2]
Did I make a mistake ? I can't find
I guess C(m,j) is binomial coefficient. But some of those combinations are not valid. Actually, you want Catalan numbers or "number of valid parentheses expressions of size $$$m$$$".
question B is cancer. Just guessed 2 power k after 45 minutes.
question B is cancer, Took 45 minutes to just guess 2 power k.
Can you please explain the logic of this problem, I was struck the whole time :(
there is no logic. just do a brute force and guess the pattern
There is a logic. Let's imagine a grid NxN. According to the formula C[i][j] = C[i-1][j]+C[i-1][j-1] and C[i][0] = 1, C[i][j] is the number of ways to get from the cell (i,j) to any of cells (0,0), (1,0) ... (N,0) when only following steps are allowed 1) (y,x) -> (y-1,x-1) 2) (y,x) -> (y,x-1) Since each time x is decreased by 1, we move exactly j times. Since j < i, it is always possible to chose any of 2 steps. For (n , k) there will be k steps, and two variants for any step, which leads to the result 2^k.
sure ig. what i meant is, in this type of problem you shouldnt look for logic. guessing is the way to go
You can draw the grid on paper and see how it goes. As in how Pascal's triangle is calculated, same for this one.
in the wrong formula, C(n,k) = C(n,k-1) + C(n-1, k-1)
As is stated that n > k for all n,k , you can see that for every K, you will have 2 branches of K-1 until it gets to k = 0, which the result is 1. Which means, C(*,K) = C(*,K-1) + C(*,K-1) = C(*,K-2) + C(*,K-2) + C(*,K-2) + C(*,K-2), that is, 2^k (considering that when k = 0, it returns 1)
I knew it would be some kind of pattern otherwise it will be too hard for div2 B so i generated sequence using that wrong formula given and search the sequence on enclyopedia of interger sequence and got formula ,
Could have just manually solved for n = 1, 2, 3, 4, 5. It was easy to see the pattern after that.
explain E clearly please :(
explain E clearly please :(
How to solve E?
I think it is dynamic programming. dp(suit number, remaining cards of suit 1). then you just have to solve the one dimensional problem for a specific suit number. This is rough idea, still haven't solved it. This should solve it in O(N^2M) time complexity I believe.
I treated the one-dimensional case as a balanced bracket sequence (there can't be a prefix where player 2 has more cards), then the transitions are basically counting balanced bracket sequences with fixed prefixes which is a known problem
Maybe I need to explain why n = 3, m = 6 's result is 1690 :(
Consider one suit. Define $$$a_k$$$ is the number of valid ways such that the difference between the number of cards of two players is $$$k$$$. You can use either dp or combinatorics to solve this. Note that player 1 must have no less suit 1 cards and no more suit X cards than player 2, so we have $$$k_1=\sum_{i=2}^nk_i$$$. The number of ways for the other suits is a convolution of $$${a_k}$$$, and given $$$n,m\le500$$$ you can use either brute froce or NTT.
Detailed. Thx.
Okay finally I solved it.
You can see that if on the first time, you have x cards with suit 1, then when you go from suit i to suit i + 1, if you have to "pay" j cards suit 1 to beat j cards on suit i + 1, so the transition is f(i, x) ----> f(i + 1, x — j)
Let's define ways(i, j) is number of ways when you have i cards and after distributing, the number of cards in first set more than the number of cards in second set j ones. I define j is the different between number of cards in first set to number of cards in second set because j is "free", you can use j to beat another cards
The formula of ways(i, j):
ways(0, 0) = 1, ways(i + 1, j — 1) += ways(i, j), ways(i + 1, j + 1) += ways(i, j)
the formula of f(i, j)
f(1, j) = ways(m, j)
if we use x of j cards to beat x cards which suit i + 1: f(i + 1, j — x) += f(i, j) * ways(m, x)
Final result is f(n, 0)
In fact, $$$f(i, j)$$$ can be seen as $$$ways(i, j)$$$.
You can solve it bracket match. The first player's cards are
(s, the second player's cards are)s. For suit 1, each prefix must satisfy(s are no less than)s. Now $$$f(i, j)$$$ means that we concider first $$$i$$$ suit 1 cards and the first player has more $$$j$$$ cards than the second player. So the fisrt part is as you said.Let's see how it works on suit $$$2 \sim n$$$. We know that each suit satisfies the second player has each suit no less than the first player. If $$$f(i, j)$$$ means the first $$$i$$$ cards
(s match)s, and the second player has more $$$j$$$ cards than the first player. Note that if we replace the excess(s to)s, it's completely identical!So for suit $$$2 \sim n$$$ cards we can use convolution. Let $$$g(0, x) = f(m, x)$$$, calculate $$$g(i, k) = \sum_{x + y = k}g(i - 1, x) \times f(m, y)$$$. After $$$n - 1$$$ rounds, $$$ans = \sum_{i = 0}^{m} f(m, i) \times g(n - 1, i)$$$. Because the more $$$i$$$
)s should be matched by $$$i$$$(s.Here's my submission 285980588.
This is an interesting solution, can you tell me where to learn more about the concept you mentioned towards the end?
Oh, we refer to this form $$$h(k) = \sum_{k = x + y} f(x) * g(y)$$$(* can be any operator) as the convolution. It has the same form as normal convolution. Because it is $$$O(n^2)$$$, an algorithm can solve this form with $$$O(n\log{n})$$$, like NTT and FFT. Generally speaking, in this problem we don't need to use NTT or FFT, because $$$n \le 500$$$, $$$O(n^3)$$$ is enough.
As for what I mentioned at the end is to multiply many of the same things together. We consider $$$g(i, k)$$$ means that, for first $$$i$$$ suits the second player has more $$$k$$$ cards unmatched. $$$g(i, k) = \sum_{x + y = k}g(i - 1, x) \times f(m, y)$$$ means the $$$i - 1$$$ state how to recursive the next state. Because for first $$$i - 1$$$ suits the second player has more $$$x$$$ cards unmatched. For $$$i$$$ suit the second player has more $$$y$$$ cards unmatched. Then for first $$$i$$$ suits the second player has more $$$x + y$$$ cards unmatched. This is why it comes up.
Note that convolution is just a form of calculation.
Thankyou very much YipChip
Memoization gave TLE on D :(
converted into iterative soon after contest got over :(
I don't even get that D is a dp problem lmao, 1hr on the problem and I don't have a single clue. I need to do more dp exercises
I think the submissions for Problem D should be rejudged... My O(m^2logn) solution did not pass, and even after rewriting to O(m^2+mlogn) it barely passes...
Do u think there is a specific reason for TLE when memoizing ?
the constraints are too strict. everything TLEs if not done carefully, not just memoization.
Unsure, but it is true that binary searching at each state is not the most optimal solution. I don't think it warrants a TLE in this situation, however, because some solutions like this passed (I'm not sure why mine is so slow actually).
I was able to pass by fixing iterating over sum and fixing i and j and updating the number of passed checks by iterating forwards and backwards, reducing the need to binary search at every state, and now I only do it at each index.
I fixed My Binary Search approach using prefix sums on frequency for each interval 1 min after the contest was over :(, sad to see some binary search solutions getting passed while mine failed :(
$$$\log_2(2\cdot10^6)\approx21$$$ so $$$m^2\log n$$$ exceed $$$5\cdot10^8$$$. It is very normal that $$$O(m^2\log n)$$$ doesn't pass.
While this is true, language/implementation differences allow some of such solutions to pass while others do not.
It's hard to believe that my $$$O(N + M^2)$$$ submission 285907904 was nearly TLE.
You are not using fast IO (ios::sync_with_stdio(0)). I'm pretty sure these problems are made considering the answer will have that line of code.
True. It runs in < 1s with this one line: 286094496
Right, I've found many people have this line in their code. Does it matter?
Well, as you can see from sarodesparsh's test, it kind of matters. It desynchronizes C's IO with C++'s IO (aka using cin/cout mixed with printf/scanf may have unexpected behaviour). That synchronization had a cost, and when you stop it, you gain a performance boost. By the way, since we are talking about IO, if you have to print a lot of lines, using '\n' instead of endl is also a good performance boost (because it flushes less often).
Thank you very much, I will try it next time.
You are welcome :)
You know what, it makes sense. Though some of them do pass due to small constant I suppose. For me, I genuinely had no further ideas beyond binary search and it seemed elegant enough (massive pitfall lol). Hopefully editorial explains prefix sum idea as well.
I don't think binary search should be used at all. I could get it working by simply using maps. Run time < 1s: 286091048
285925069
Why is this giving TLE? (C)
isnt it bc of the loop from 0->n mapp.find?
no
I didnt read your whole code, buy anyway, u solved it in O(n^2), you have to solve in O(nlogn)
i think this is O(nlogn) only, thats what im asking.
its not, for every start 0->n you create a new window from scratch, which makes it n^2
thats not how it works, lil bro
Try an input of all the same number such as
1 1 1 1 1 1. You can see that it is $$$O(N^2)$$$.It literally is, you can prove it with induction on paper. For that reason ur getting TLE
If you complaint about the tl in D being too strict, that probably because you lack proper optimization skill lol https://codeforces.net/contest/2025/submission/285928139:
1) The most efficient data structure to store data is the one that has all the memory as close as possible: an array/vector.
2) If you ever use a 2D vector to store the dp, you have to wonder if you can optimize it to 1D. This is a huge leap, not for the memory, but for one important thing: Cache.
You can see my submissions for thought process
based cache utilization enjoyer
The one contest I decide to skip has an easy problem A, sigh.
Great problem set!
For problem D
My first solution had used an ordered set for the splitting the indices into segments and storing in a sorted order which gave me a TLE. The TC for the solution should be O(m^2logn) as to my knowledge please correct me if I'm wrong. 285893834
I used the exact same logic but replaced the ordered set with a vector and sorted the vectors and used upperbound for my final submission which should be of the exact same time complexity and got AC. 285923230
Could anyone help me out in understanding why is it so that upper_bound solution works but set doesn't?
I tried to use the same logic with a regular set and had the same issue. Adding the else if(abs(x)>cnt) continue; line in the ordered set solution did not work which is the bit of logic changed in both the implementations.
my approach was similar with your vector approach... still I got a TLE :(
since u r using recursive approach too , I don't think it matters..
Yep, complexity is right, but constant seems quite higher, since you store pairs and ordered_sets are quite slower than a normal set/map/multiset. Notice you don't update (erase) the sets, so yo can use vectors and use binary search (upper_bound).
Makes sense, thanks. The constraints were too tight for any overhead.
In E, I just didn't realize that in a suit i(>1) 1st player can't take extra card when the current state of suit is already a tie (assuming we select the card from small to large in the suit). Since all previous card matched with a 2th player's card, if 1st take this card, it cannot beat any card (but you cannot let this happen, it will leads to the lose in global).
I'm really glad that ki<=ni in problem B Imagine it's not and that it would pass the system tests
G is cool
U are cool
How to solve G? I see, that the answer is $$$\sum{a_i} + \sum{\min{(a_i, b_i)}}$$$, where $$$a_i$$$ are heroes and $$$b_i$$$ are artifacts, and they are matched greatest-to-greatest. Is it some well-known problem?
I don't think it's a well known problem, this is the first time I encountered something like this. Took me a while to came up with the solution during the contest.
Square root decomposition.
Your observation about the answer is correct btw.
there seems to be some issue. On "Standings" page, even after un-selecting the "show unofficial" checkbox, contestants having rating greater than 2100 are included in the ranklist.
for Problem c , can anyone tell why this solution is giving wrong answer on test 4 (i used binarysearch to solve this): https://codeforces.net/contest/2025/submission/285946605 thanks in advance !!
how to hack for the first time my generator gives
Validator 'val.exe' returns exit code 3 [FAIL Expected integer, but "/**" found (stdin, line 1)] close .
how to hack in codeforces for the first time ? my generator gives
Validator 'val.exe' returns exit code 3 [FAIL Expected integer, but "/**" found (stdin, line 1)] close this error as invalid input
nvm
How do you know?
My post contest discussion stream
Hints blog
Anything wrong with this solution to E, or just python tax? Runs in about 10 seconds on my machine. 285917083
TC is super strict on D. I think it cost me to write my own bsearch and use extra variables within the dp function (recursive of course). I kept debugging thinking there's some way to optimize further, but I'm just dumb. My brain during the round:
https://www.youtube.com/watch?v=fTczCpIaLAU
Solution of D in O ( M * M ) using prefix sums !
285955590
Your solution is O(N + M*M)
It is impossible to be faster than O(N), you need at least that time just to read all inputs.
m = 5e5 , m^2 = 2.5e7 >= N = 2e6 so we can ignore that ( + N )
[email protected]
i have solved two problems and initial my rating was 460 but in this contest it is not showing any rating change, what could be the issue please help me !!
It will update in a while.After the contest ended, there was a hacking phase for 12 hours. Now it has also concluded. Ratings will be changed after system testing. Thanks :)
guys, why it isn't rated for me?
The rating hasn't been calculated yet. (Please forgive me for my poor English.)
Thank you so much
Hi I submitted a solution for C after contest had ended (during the open hacking phase probably).
And it showed TLE for 6th or some TC. But now in the final standings it shows -1 for C problem, but that was not submitted during contest time. So is this -1 normal ? or some error ? I am new to this platform.
@awoo @adedalic
I was randomly checking other people's submission and came across This Submission . This code fails for the following testcase:
Correct Output: 8
Actual Output: 0
Can someone explain why this code was Accepted?
UPD: The author of that code told me that, the continue statement used in his code caused it to fail in my given testcase.
Dp_forces
my code for B got hacked and the same code got Accepted after the system testing why is this?
hacked:https://codeforces.net/contest/2025/submission/285916972 Accpeted:https://codeforces.net/contest/2025/submission/285996748
MikeMirzayanov
Tabulation DP worked in D, recursive gave TLE, same logic in both.
Are there a system test soon?Or I'll get my rating later?
Can anyone tell me why "re on test8"
285930355
d[sum+a[j]+1]--
here sum+a[j]+1 could exceed the bound
you have put a semicolon(;) instead of comma(,)
thanks！！！
when will rating points be awarded?
I solved two questions in yesterdays contest , A and C
both of them showed as accepted during contest
but now its showing that only A has got accepted and submission of C is showing as "In Queue"
Can please anyone explain it?
The submission are being rejudged after open hacking phase against the test cases from hacks and system tests.
Ohh got it!
Thank you sir!!
After contest 12 hours of hacking phase takes place which is already done for this contest after that System testing takes place. which is going on rn. Your submitted goes thru more test cases during this phase. You can click on problem section you will see there written system testing x% done. during this phase your submitted code will be In Queue (that is being tested)
Ohh got it!
Thank you sir!!
I solved three questions in yesterday's contest: A, B, and C. If system testing is already done and my problem C fails, my result will be two questions solved, even though I had solved three before.
System testing now
Problem E1 and Problem E2: I saw the tutorial done using number of connected components. But does this handle the case of impossible?
Hi guys, I am a bit new in CF, please answer my few questions.
If I can solve some easy DP,greedy,Data Structure,Graph/Tree Problem,prefix sum... but can't solve for most hard algorithm (or just know it and can solve very simple problem about it), is div. 2 fit for me?
And how can we increase our rating fast? Is it really hard for me to get to Specialist by only two contest?
And when have the contest with different time? Randomly? or some special type of contest? (Usually the CF rounds are near my sleep time)
Thx for you guys' answer.
Problem D recursive dp submission 285916779 2499ms I submitted anathor solution with vector inplace of array dp
Problem C: Why did i get TLE test 10?
because
ouch... but thnx
When will rating get changed???
Already Changed I thought, at least mine.
Why I get 1900,but still have a blue title?
Maybe it didn't update immediately, like what happend before.
Published explanation to Problem E (which I haven't solved in time, but shortly after) https://codeforces.net/blog/entry/135152
I submitted solution 285915907 in a contest which shows accepted during the contest and now it is showing runtime error on test 8. When I resubmit the same solution it shows it as accepted.Can anybody please help me out
It seems to me, you search for lower bound in vs[-1], when indx = 0
Thanks, but don't how it got accepted
Well, it's undefined behaviour. Given that index = intel = str = 0, this two lines look like:
Compiler might optimize this code, checkin the conditions that arguments to the function are the same, and not perform lower_bound calculation and subtraction at all (less likely).
Or, more likely, lower_bound from a location in memory that is garbage pretending to be a vector, yields some result, which is garbage, but consistent for the same arguments of lower_bound. So you get your cti = garbage — garbage = 0
Until at some point, lower_bound(all(vs[-1])) fails because you try to attempt some restricted area of memory
That's really helpful
Can someone help me understand why this got hacked for TLE? 285966035
I'm assuming there's something python specific which I'm doing inefficiently, but I'm not sure what.
You should use pow(a, b, mod) instead of (a**b)%mod.
This explanation might be wrong, but my assumption would be that in (a**b)%mod, since a**b can get giant, it's slow to work with and leads to TLE on larger test cases. When using pow(a, b, mod), the number stored internally in the pow function never gets above the modulo value, so it isn't as slow to work with
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
why div 3 and div 4 contests are stop ?
Админы обращаюсь к вам, мне решение задачи В не засчитали, указав на списывание у другого участника(совпадение), хотя я этого не делал, более того, решение задачи по которой мне предъявили нарушение, содержит 5 строк кода, 3 из которых это ввод данных. Решение максимально тривиальное( 1 цикл и принт следующей строчкой), потому прошу убрать данное нарушение в силу того, что это не более чем совпадение, я участвовал в соревновании самостоятельно.
Oh no... Starting in midnight AGAIN (UTC+8) T^T
my solution 285887003 got blocked, i used this site for alg
https://stackoverflow.com/questions/67664402/python-speed-up-powbase-exp-mod-for-fixed-exp-and-mod-or-with-vectorization
Can anyone help me to find what's wrong with my D solution Solution.Failing on TestCase 19