Привет, Codeforces!
Во 19.12.2023 17:35 (Московское время) состоится Codeforces Round 916 (Div. 3) — очередной раунд для третьего дивизиона. В этом раунде будет 6-8 задач, по сложности подходящих для участников с рейтингом до 1600 (во всяком случае, мы надеемся на это). Но, конечно же, участники с рейтингом 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
У вас будет 2 часа и 15 минут на то, чтобы решить 6-8 задач. Штраф за неверную посылку будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того, являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Раунд основан на задачах муниципального этапа Всероссийской олимпиады школьников в Саратове и Саратовской области 2023/2024, поэтому если вы участвовали в нем — пожалуйста, воздержитесь от официального участия в этом раунде.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов, Максим Neon Мещеряков, Роман Roms Глазов и Александр fcspartakm Фролов. Отдельное спасибо Владиславу Vladosiya Власову за отличную координацию.
Большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces, без которых этот раунд бы не состоялся!
Наконец, спасибо тестерам раунда FBI, Kalashnikov и SonOfHonor за ценные советы и предложения!
Удачи в раунде! Надеюсь, задачи, которые мы подготовили, вам понравятся.
UPD: Разбор опубликован
Yet another post contest discussion stream
yet another youtuber whose streams i like :D
Really Informative. Thanks. Keep these Discussions coming...
Improve your internet connection before doing live streams and change your microphone. how someone supposed to understand whatever you are explaining in the live stream :')
I presume you are offering to buy them?
Wow, a div 3 round with edu round setters. Excited to see how this goes
Hi guys, I'm sorry to bother, I'm kinda new in this website, I just voted downside by accident, so please remove it, also, how can I unregister from a contest? I'm really really sorry, but I registered before 1-2 days, and I just remembered that tomorrow I have school so I can't participate, please is it possible to remove my registration from the codeforces round 916 ? thank you very much, I'm just worried that my rating would decrease incase I don't attend
As far as I'm concerned, not making any submission during contest will make the contest not count for you. But you can unregister anyway: follow this link: https://codeforces.me/contestRegistrants/1914/friends/true and click the red X
Thank you very much
Sorry, downvoted by accident.
Have a nice day, friend.
Marinush
First unrated contest Hope to see some good problems. (POV: frequency of contest at CF in this month is amazing)
hope to get positive delta :)
back to back cf round , yayyyy
Excited for the contest. Hoping To Solve 4 problems fast in this round. got -ve delta in education round :( .. hoping to become expert this contest
hoping to become pupil :)
Удачи Всем!
Please have more div2s or I'll lose a lot of money to pk_27. (;_;)
Me every time I do a div 3 contest:
plsnomath
Lol it didn't happen this contest :D. Bricked E1 tho
In last div-3 I bricked in $$$C$$$ , hopefully today I will have my revenge
Yes div3, hurrah!
After solving A, B & C:
There is nothing we can do...
After solving A, B, C, D, E1 & E2:
There is nothing we can do...
thank you for new pain generator!))))
Hoping to fast solve first three!
When will the rating of yesterday's edu round be updated? I was hoping to become specialist in that and then give today's div3 as a rated round.
Due to some issues, it will be updated after this round.
So i will have to give div3 as unrated?
Yep
that sucks, thanks for replying though!
i will be demoted to less than 1600 after the rating drops for the last div 2 contest that was yesterday. currently i'm unrated for the div 3. if i participate now will i be considered rated or no ?
Unrated for you.
i hope i'll get expert
My advice as a last-minute tester, don`t forget reading and thinking about every problem for at least 5-10 minutes, because all of them are nice
ok then I clearly assume that I can solve A-D :)
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
awoo can you please give some update regarding the rating calculation?
Whether for people who would be upgraded to Expert, the round will be rated or not?
Still rated
Will bhediya sir is the solves 6 problems today?
Upvote: Yes
Downvote: Yes
Queueforces
please fix the queue
please fix the queue
Nice problemset. I wish the queue had been a little faster
i got tilted after round
E1 is a bluff. The exponential time brute force solution is more difficult than the greedy optimal solution I think.
What's the greedy optimal solution?
You sort by $$$(a_i + b_i)$$$ and choose alternatingly
The sequence of play is according to the decreasing order of a[i]+b[i] I think
bro can you explain your brute approach
I couldn't figure out greedy solution even thought I tried for so much time. Finally had to submit E1 with brute force solution
sort the array by sum of their i-th marble
every turn:
they will select the most sum
and the color they selected cant play anymore
yeah, makes sense. I don't know why during contest I tried sorting on basis of (a-b) and take from alternative ends. I thought alice would maximize (a-b) and bob would minimize (a-b), though it didn't work.
F was an interesting problem for me... still not sure how to approach it but came up with this proof-by-AC solution lol
can you explain it
I did a lot of drawings of the sample cases, and observed that a good strategy seemed to be greedily pairing the employees at deepest depth with the deepest available employee. So we go through the employees from deepest to highest, always pairing the employee with the deepest available employee. Two employees at the same depth are always compatible, and we know that an employee at a higher depth is compatible as long as there is more than 1 employee at that higher depth, so we keep track of all depths with more than 1 available employee.
Good approach, thanks for sharing
i thought of exact same logic ...but was unable to implement it.. can't we do with only storing employees at particular levels then pairing??
How would it work with tree like this?
I do not believe how badly I performed... any advice on improving at game problems? I swear they are my kryptonite.
I couldn't even get E2 but got F :(
Yeah I too was surprised to see your performance. (been following you for some time :))
E1, E2 < D for me as i couldn't think of the easier solution and overkilled D.
I think C>E1,E2>D, C take me a lot of time, while D is my first submission
Same ..E1,E2,D have more trick parts and easy coding parts than C . And this contest had submission issues too which affected the performance of many of us for sure..
make a 3x3 matrix of the activities with the most friends, and do recursion to find the optimal 3 days, sum of whose is our answer.
Code: 238064464
what's the idea of d?
i can do both E how easy and hard version matter?
Try all 3*3*3=27 combinations of the largest 3 values of a,b,c
It is right.But how stupid i am that i solved d a few minutes after the game.
You don't have to try 27 combinations even comparing 9 triplets works
Can you explain how it's working? I'm not still getting it properly.
You can sort all the 3 types of activities and preserve their indices. Something like $$$Element, Id[Element]$$$ for each of activity individually. Now you can sort all three activities. The ways you can form combinations are
$$$max(A)$$$, $$$max(B):(id[B] \neq id[A])$$$, $$$max(C): id[C] \neq id[A], id[C] \neq id[B]$$$ or $$$max(A)$$$, $$$max(C): id[C] \neq id[A]$$$, $$$max(B): id[B] \neq id[A], id[B] \neq id[C]$$$ then you can do this for each of the arrays individually giving a total of 9 combinations
I did it by trying all permutations the order of choosing, and when its ones turn to choose they just choose the biggest one where the day isn't chosen before, and just getting the max of all permutations.
you can solve using dp ur states will be dp[index][did u take ski][did u take movie][did u take game]
Legends use math and 27 combinations, Pro's use dp
haha not really it alot natural and easy to approach this kind of problems using dp just need to handle some anouying cases
even your name can illustrate how much you like dp :)
I also did it with dp. But now it seems I just overkilled it.
You can just use a mask to denote the choosen elements
if u mean to use a mask to represent did choose ski, did choose movie, did choose game instead of the other three dimensions you are correct
Why is my code giving TLE in problem D https://codeforces.me/contest/1914/submission/238102211
Hmmm not totally sure but I see u are filling the entire dp array every test case which maybe the issue
got it! This is the correct one. https://codeforces.me/contest/1914/submission/238107771
U can also replace the memset line in ur previous code with this
memset(dp, -1, n * size of(dp[0]) Which will only fill n blocks of the array every test case
It can be done using dp with bitmasking. Here's the code: https://codeforces.me/contest/1914/submission/237970710
RIP my rating
should have not participate this round
couldn't solve E on time
nice round, me first time done 3 proplem in 1 round XD
Did decent in this round but unfortunately is unofficial because the changes for last round isn't updated. Can't enjoy the free rating :( Does anyone know how pF works? I solved G1 and have ideas for G2 but I couldn't think of how to solve pF at all...
You can greedily try to to match for each vertex vertices only from different subtrees and then you are left with maximum 1 subtree with unmatched vertices where you can recurse.
EDIT:
238056332
BFS and pair teams height wise (bottom to top) I think. If there are any remaining players (which happens when they are along a path of the tree), pair them up with players at a higher level with highest priority.
I think C > D D was very simple , but what is the idea behind C
I got confused with D and not able to solve at all
Please explain ?
Only $$$9$$$ positions are useful. You just need to consider these positions and count the max answer.
oh i think of that during contest but i can't proof it. sad
For C My approach was to take all the elements of A first Then greedily start removing elements of A from last and filling the remaining with the maximum available elements of B we have, while doing this keep taking max of all
Yes, I too had the same thought.
Same Approach, though took some time to implement it
I don't think there was an "idea". Firstly it was clear that distinct problem solves would be a prefix. So just brute force on the prefix and for the rest of solves just take the maximum b[i] in the prefix. See, just brute force.
Greedy approach, "if I decided to stop increasing my level at level $$$i$$$, what is the maximum score I can get?" if you stop at level $$$i$$$, then your best choice is to use the remaining $$$(k - i)$$$ plays redoing the maximum $$$b_j$$$ such that $$$(1 \leq j \leq i)$$$ again and again. So the answer is this maximum value across all $$$i$$$, just keeping in mind that you can't go to level $$$i$$$ if $$$k > i$$$
Запутанное определение начальника в задаче F. Пол часа решал не ту задачу. Одно расстройство...
Сейм. Я вообще сначала написал топ сорт, а потом заметил это условие.
Топсорт дерева?)))
Ну да. Если бы начальник не считался родителем всех вершин, то можно было бы сначала сделать топсорт, удаляя одновременно по две вершины и получить бамбук с ним наверху. После этого просто посчитать, сколько максимально мы можем взять пар. Но, к сожалению, это оказалось неправильным решением.
Great round, thanks for clear and concise problems and strong test cases, helped to catch couple bugs. My personal best result so far
Can anyone one tell me how to approach and come up with the greedy solution sorting on a[i]+b[i] for problem E1 and E2?
i just think which marble each player will select
if A's turn A just pick what max(A get + B lose)
Alice wants to save her balls and get rid of Bob's, they both equally affect the score. And the vice versa for Bob.
If Alice picks ith-marble, score increases by a[i]-1 and if Bob picks ith-marble score decreases by b[i]-1. If Alice did not pick up the ith-marble in his turn, this means that his choice of say jth marble which increased his score by a[j]-1 is more significant than the impact of Bob decreasing the score by b[i]-1 in the following turn, compared to an increase of a[i]-1 and a decrease of b[j]-1. So you need to sort the array |a[i]-1|+|b[i]-1|, which is equivalent to sorting a[i]+b[i]
great explanation
Initially, both Alice and Bob got all the marbles. No matter who operates on color i, the difference between their marbles is fixed a[i]+b[i]-1, so do a[i]+b[i] Sorting, Alice greedily chooses the largest a[i], and Bob chooses the largest b[i].
Simple and concise, Thanks.
I think I can give a more clearly stated explanation to the solution discussed here.
Consider current score as S.
Now, think of two index i and j, where values in a and b are still > 0.
Let these two index be such that Alice takes one, and Bob takes the other.
Final effect on Score after the 2 moves:
Case1 (Alice takes ith, Bob takes jth marble) : S1 = S + (a[i]-1) — (b[j]-1)
Case2 (Alice takes jth, Bob takes ith marble) : S2 = S + (a[j]-1) — (b[i]-1)
If S1 > S2:
S + (a[i]-1) — (b[j]-1) > S + (a[j]-1) — (b[i]-1)
(a[i]-1) + (b[i]-1) > (a[j]-1) + b[j]-1)
(a[i] + b[i]) > (a[j] > b[j])
Therefore, if both players move optimally,
They take the marble from the index which has the largest sum, a[k] + b[k]
Hence, the approach:
Sort and construct the score based on (a[k] + b[k]) is a correct approach.
Will the rating change of this round take place after the previous educational round or on the current rating?
I think this div 3 round's ratings update will be applied first, then the previous edu round, according to the latest announcement.
I've noticed the condition about head being superior over everybody in F, just after writing the solution, lol.
Amazing contest I enjoyed this Div3 specially problem C it's idea is very amazing and interesting to implement
D is a lot easier than C, you just need to care about three maximum elements of each array
Nope, Please I got that
Nice solution.. didnt thought of this did with dp ^-^
Really cool implementation for d.
I got the logic during the contest. But started implementing without any plan. Ended up with a big messy code which I could only complete after the contest. Got AC anyway.
Problem D was like, I know I can solve it. But how to get away with 3 way comparisons in 3 dimensions.
same
lmfao accurate
bhai yeh koi hasne ki baat hai gand uchhal ke
Speedrun until I forgot to update a value in D and got WA on pre#2, and it took an hour for me to realize my mistake, otherwise could have finished writing F and G2 which I knew how to solve by the end of the contest... RIP rating.
btw good E ig, interesting greedy problem.
D was way easier than C.I solved D(if you know vector's pair part you can solve it easily). Can someone explain main idea behind C?
mine
keep update max(b)
constuct prefix of a
answer = max( (k-i-1)*max_b + prefix[i])
(k-i-1) is remaining of k after do ith quest
I understood thanks :)
Implementation forces
i am newbie here i have given the contest first time and this contest is showing unrated
I think it is Rated. Look at that. Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
its showing unrated how can i register a complaint for that please healp
Could someone explain the amazing solution 237977153 in G2 by jiangly? I don't understand the meaning of xor operation
I think
f[i]
represents the set of all colours that occur exactly once prior to index i. It uses hashing to fit in a single integer and the xor means that after the second occurrence of each colour, it is removed from the hash. Then if there are two distinct indices i, j such thatf[i] == f[j]
and they are nonzero, all colours that occur between i and j only occur between i and j, and there exists another colour that "surrounds" them. Hence turning on any light bulb among this set initially could not be part of a minimal solution, because you would have to turn on one that surrounds them anyway (and that could have been used to turn that initial one on). So you can skip to the last occurrence of eachf[i]
when counting the number of ways.The core idea revolves around determining the number of ways to activate bulbs in such a way that disjoint ranges are covered. The approach involves finding** sets of bulbs that, when activated, cover a specific disjoint range**.
This is achieved by eliminating unnecessary bulbs through the use of prefix hash values, allowing for speedy identification of redundant bulbs.
Let's denote the number of disjoint ranges as 'k.' For each range, we aim to identify the bulbs whose activation covers the entire range. Through some careful considerations, we conclude that we need to eliminate bulbs that do not contribute to extending the current segment. This elimination process is efficiently executed using prefix hash values and storing the last pointer for each unique prefix value.
To illustrate this concept, consider the arrangement of bulbs: 1 2 2 3 1 3. The number of disjoint ranges in this case is one. Building prefix hash values results in pre[0]=1, pre[1]=1^2, pre[2]=1, pre[3]=1^3, pre[4]=3, pre[5]=0. After activating the first bulb, we jump to the bulb at index 1 + (last[1]=2).
Notice that bulbs at index 1 and 2 are not useful as they lie completely within our segment, and they do not contribute to generating a new hashed value or extending the current range.
The hashing technique employed here, as introduced by jiangly, is a so cool and unique that when understood properly can be generalized to solve a variety of other problems involving segment merging or ranges.
I am new, could anyone explain what is open hack timing that is going on now?, it wll affect in rating ?
read this post https://codeforces.me/blog/entry/107753
What's the idea behind F? I observed that we can pair up nodes from the $$$root(1)'s$$$ children and thier respective $$$subtrees$$$ as long as we can, Then the left over nodes in each children's subtree can be paired $$$iff$$$ they are leaves? I don't know a fast way to do all this? What's the optimal / correct approach?
You should just take maximum of possible pairings, no matter if it's leaves or not (just make sure they are from different branches). I've got my brain melted after writing the append of results of child-dfs to current res (.0 = pairs, .1 = available people in subtree) (solution). Same thing but much simpler is in the jiangly's solution
Ahh I see thanks I shouldn't have messed around with leaves bruh, Thanks!
Problem C: You can do at most $$$min(n, k)$$$ quests. To get first $$$m$$$ quests completed, you need to complete each of $$$m$$$ quests for the first time, then you have $$$k-m$$$ quests remain, of course you want to choose which quest brings the maximum profit, in this case, it is $$$max_{i=1}^{m} b_i$$$.
Solved 4 for the first time, had also solved 5th on paper but made an error addition for test case 4 to eventually discard my solution, had i not made the mistake i would have got the 6th question too. Should i call this a successful round for myself or try solving grade 1 mathematics to improve my addition and subtraction..
you can find it in chapter of bit manipulation (dp with bitmasking)
no, if you can provide a source where similar code was already written before the contest it's not considered as cheating.
link to the book
bit manipulation >>dynamic programming page 112
I wonder how many proved E
If you have proved it,can you pls provide a proof of it?
I imagined that both alice and bob actually have 2 arrays: 1 is empty and the other one is from the statement. So by 1 operation alice or bob delete a[i] / b[i] from the statement array of an opponent and then add b[i] — 1 / a[i] — 1 to the empty array. Then I determined the final score as diff between sum of elements of both alice arrays and sum of both of bob arrays. It's easy to see that with these 'new' rules the max final score will be determined by the same sequence of turns as with the 'original' rules. Then we can notice that if it's Alice's turn, the final score will increase by a[i] + b[i] — 1 and if it's Bob's turn the final score will decrease by a[i] + b[i] — 1.
Let's assume that Alice picked the pair $$$(x, y)$$$, then she will gain $$$(x - 1)$$$ pts. And moreover, she will also make Bob lose $$$y$$$ pts. Hence, the relative gain she made by picking the pair $$$(x, y)$$$ is $$$(x + y - 1)$$$, which is also proportional to $$$(x + y)$$$. Thus, she will greedily pick the pair with the largest sum. Bob will also follow the same approach to play optimally.
Now, we can just sort the
vector<pair<int, int>>
in decreasing order of the sum of both elements of the pair and assign them alternately to each player.proof was my way to solution. i couldn't guess.
Sorry, but I don't believe you
k
The explanation of issue A is very, very bad
someone explain how to solve E to me?
Try merging the total amount Alice and Bob have and choosing the optimal values greedily from the sorted merged set of values.
see this guy's solution: https://leetcode.com/problems/stone-game-vi/solutions/969817/strategy-proof/
only difference between the leetcode problem and E2 is that in E2 you subtract n % 2 from the answer.
Basically after each move each player in profit of a[i]+b[i]-1 coin if he choose ith index so make a set of pair and insert a[i]+b[i] in set with its index.(only if a[i]>0 & b[i]>0) and in each move pop greater sum index and do operation according to player while set is not empty.238003308
look from the perspective of alice & try to make score of alice as much as possible.
Now lets consider two elements a = [x1, x2] & b = [y1, y2] then in this case in which case alice will win
say alice first selects y1 to remove from b then score will be (x1-1 — y2 -1) because then bob will only left with x2 to remove
similarly if alice remove y2 first then score will be (x2-1 — y1-1)
now see in both the cases which is giving higher score simply sort the index with value x1 as first for alice and then alternately removed one by one because we have sort it such that it'll give maximum score to alice on its turn bob will try to remove the next maximum possible to minimize the score.
Check solution here : https://codeforces.me/contest/1914/submission/238051187
Thanks I will check out more on this problem. I have seen too many different ideas and gotten even more confused.
a few minutes late on G1. feels bad
D >>> E
I've never done problems with easy and hard difficulty before ; was I supposed to send my answer in both difficulties ? Or just sending it on hard gives you all the points?
You have to send it in both problems in order to get points.
Wrong, both problems are graded independently.
Can anyone provide any counter test for F https://codeforces.me/contest/1914/submission/238060620
In this contest time, I am not able to entering in the contest arena about one hours. In this one hour I am just seeing security checking. This problem also happens in the previous div3 contest. Why????
In this contest time, I am not able to entering in the contest arena about one hours. In this one hour I am just seeing security checking. This problem also happens in the previous div3 contest. Why????
Did anyone tried solving D using heap? pop largest 3 a,b,c such that they dont have same date.However i think here we miss many test cases
dude D is very easy just brute over the top 3 on each group and check if there is different date since we are sure we will find a combination for such conditions
yup
did you solve it
yeah solved using heap
jo maine comment kiya h usse kya alag kiya? i don't know Cpp, can't understnd your submission.yha bta de plz
I have tried this approach by storing sorted elements in a stack and popping if they belonged either to the same index or the same kind of event. This approach however does not work because it means that you will always choose the highest popularity on the first pick. Lets say u had 99 and 95 in A and 98 and 1 in B assume any value for C. If you choose 99 in A which will be on top of the heap you will fail to choose 98 for B which happened on the same day. 95+98>99+1. Here heap approach fails and you will have to compare the highest 3 to get answer.
can anyone explain the intuition behind greedy optimal solution for E2, like using a set which stores (ai+bi) and then iteratively taking the max value, what was the logic behind it, also is there any solution to E2 which passes and is not greedy?
If you play as Alice and take i on some move, you earn a[i] — 1 because Bob can't decrease this number after your move (-1 because you decrease your number by 1), and you earn b[i] because Bob loses b[i] marbles. And now you play as Bob and take j on some move, you earn b[j] — 1 because Alice can't decrease this number after your move and you earn a[j] because Alice loses a[j] marbles. So you need to maximize the same thing (a[i] + b[i] — 1) for both Alice and Bob on every move.
in each step you try increase yours score and decrease opponent score as much as possible so A[i] + B[i] its just how much you can get if u pick i-th element, increase for A[i] and descrease for B[i] (and opposite for bob)
i registered for the contest earlier but have joined some seconds late , is this the reason this contest became unrated for me, i am a newbie and this is first contest i have given
No. After hacking phase ratings will be updated.
How to brute-force E?
for E1: just use the mini max algorithm: check my submission
i did dp for d 238005542
i did dp for d 238005542
Me After reading problem statement of A :
Hey Codeforces community,
Today, I came across YouTube videos featuring solutions to problems from an ongoing Codeforces contest. It's crucial for us to uphold the principles of fair play and maintain the integrity of our contests.
Sharing or seeking solutions during an active contest undermines the spirit of healthy competition and the learning experience for everyone involved. Let's all be mindful of the Codeforces guidelines and promote ethical practices.
C : https://youtu.be/HX7hfWtbu34?feature=shared D : https://youtu.be/nRizpg7ohUM?feature=shared E1 and E2 : https://youtu.be/5-QQxSMgVEA?feature=shared
Hope this time i get green
it means that node x is a superior of node y if node y is in node x's subtree
Count pairs $$$(u, v)$$$ where $$$LCA(u,v) \notin \{u,v\} $$$
Bro, I managed to solve G1 after the contest and was glad that I could change it a bit for G2, but when I saw others' solutions for G2, I was completely baffled! Could someone please explain the solution for G2?
In problem statement it's highlighted in bold: exactly two light bulbs for each color. Tbh, I didn't notice it during the round. So when we have a group of bulbs with 2 of each, we have SCC and can turn it on with just 1 switch in |group| — |sub sccs| ways. 2 of each color => xor == 0.
Is there no streaming of this contest?
Could anyone please explain how C is solved with a greedy approach?
Suppose you pick all the quests until the index $$$i$$$ just once ($$$i$$$ must be less than or equal to $$$k$$$). You still have $$$(k - i)$$$ moves remaining, and you can only choose the quest with an index less than or equal to $$$i$$$. We will greedily choose the quest with the largest value of $$$b$$$.
Can any setter/ tester provide 3944th case in the 2nd test case of problem F?
Thanks in advance!
I fixed some of your logic, hope it helps
238110031
btw, the 3944th case seems to be
The answer is
3
but your solution says2
.The three pairs could be
(2, 6)
,(3, 7)
,(4, 5)
. Other combinations are possible.Right, I get the flaw in my logic, thanks for the reply and the fix!
So why it's unrated for me?Or it's unrated for everybody? What's the reason?
Long long integer timeout for question C.
CF predictor is trash now. Showed +100 in educational round. Just gained 47. Thankfully became Pupil. Also it was showing +125 for this contest but i am certain there will be almost no change in rating. Anyone can share their experience with carrot predictor?
carrot is good. It is always close to the real delta.
I replaced it with carrot. The experience was rather eye opening XD
Can someone explain F to me?
Start pairing members from deepest leaves until you reach the root
How do you pairing between leaves of different branches?
For example like this: fp = pair free people, and sp = split already paired people if it can lead to more pairs.
int dp[100003][2][2][2]; int f(int i,int x,int y,int z,vector &a,vector &b,vector &c){
}
int32_t main(){ int ; cin>>; while(_--){
}
Why does this code give me TLE? By changing the dp array to the dp vector, the solution has passed.But with dp array, it's giving me TLE,Can someone explain what is the reason?
maybe because of memset.... its kind of 1e5 times for every test case t and limits of t is 1e4
Can anybody explain the problem statement of F to me? Why is 3,4 the only team in the first test case? 1's superior is 1, 2's superior is 2, and 3's superior is 1. So, 2,3,4 are superior to nobody. But then why is 3,4 the only valid team?
Nope, question says The second line contains "n−1 integers p2,p3,…,pn(1≤pi≤n), where pi is the index of the direct superior of the i-th employee." So, in 1 2 1; first number is direct superior of p2 => p1 is direct superior of p2 ; second number is direct superior of p3 => p2 is direct superior of p3 ; third number is direct superior of p4 => p1 is direct superior of p4 ; So, only (3,4) is valid team.
Ohhhhhhhh, now I get it, thanks
этот раунд будет рейтинговым для тех, кто по итогам education div.2 стал синим, но на момент написания div.3 еще не был им?
Help needed with E2
This is giving runtime error on test 9, if I use multiset but it works with priority queue or sorting the sum, but why does it give rte if I use multiset ?
https://codeforces.me/contest/1914/submission/238110925
int main() { init_code();
int T; cin >> T;
while (T --){ int N; cin >> N; vector a(N), b(N); for (int i = 0; i < N; ++ i) cin >> a[i]; for (int i = 0; i < N; ++ i) cin >> b[i];
} }
shouldn't you erase it after updating res ?
Thank you very much now it works. I thought that it wouldn't matter.
Waiting for system tests finish?
yes when will ratings update?
I don't know for sure, but I think that in about an hour.
its taking too long nowadays
TOOOOOOOOOOOOOOOOO LOOOOOOONG
is this rated
yes
为什么无法提交呢
sorry , it is a coincidence , i am a fresh man in the codeforces , I don't know why this happened,I promise this is just a coincidence.I'm making a little progress.I released my code in ideone.com.Someone else must have done it.I hope you can return my rating
What's going on?
The DP implementation for D can be found here. https://cses.fi/book/book.pdf Page 112
ahahahah nice, I killed it in my code xDDD
238021917 Why is this giving runtime error in test 24?
in comparator when equal return false, just change >= to >
blog
Can you explain what goes wrong if we swap when they are equal?
check this: https://usaco.guide/silver/sorting-custom?lang=cpp
Thanks
Is system testing done?
yes
i am still unable to make submission
When will the ratings come...
I am writing in context to the email i received stating similarities between my code and other peoples code for problem 1914C. I have not used any unfair means but had just copy pasted the snippet from a famous github repository(I hope thats fine!). I request you to please keep me involved in the contest rating(Although i will be getting a negative delta).
same with me too..
I request you to look into this. I They literally did not consider any of my submissions just because they coincidently found a similar code to mine for 1 question. If I would have to cheat ,why would I not cheat in the other 2 questions I solved? I request you to either please unrate me for this contest or give me my true rating.
It is in context to Codeforces Round 916 (Div. 3). MikeMirzayanov
When will results be out
I received an email regarding similarities between my code for problem 1913B and that of other participants. I would like to emphasize that I did not intentionally copy any code and, to the best of my knowledge, I independently developed my solution. While I understand the need for fairness in the competition, I want to highlight that any resemblances might be coincidental. Despite the potential negative delta in my rating, I request your understanding and consideration to allow me to remain engaged in the contest rating
i didnt receive any email but my ratings have been r3dacted for the last 3 rounds. why did this happen?
I am a newbie here and my rating is currently 0, i solved problem A and C but my ratings isn't updated yet what rating should i expect??
depends more on your ranking and i am kind of surprised that you solved C instead of B i mean B was much easier than C B<D<C this is what i think
Hi, I was given a violation for sharing code with someone else. I accept that It was my fault to share the code, but I did not know that he would use that code for submission. I knew that if someone submit the same code as me, it would get caught in the system. I am very sorry for what I did.
But I am the legit writer of that code. I submitted way before him, I can only say that to prove that I was the legit writer of that code. Can you please remove the violation and give my scores back. If not, can you please at least tell me if this violation be any problem in future for me? Should I be worried? I promise not to share my code with anyone during contest in future. My submission number mdraihanhossen/237973286 and the person whom I had given the code, his submission number is mahin_sarker/238024074.
I have received an email and a notification from a system regarding my solution to Problem C colliding with some other users. I had done my code independently without any help from anyone. I don't know how my code is similar to others. Please return my rating. Or ensure me that this is not giving me problems afterwards.
When can i get my rating as a newbie……
hello, i have recieved a message from 'system' about solution to a problem being similar to another user called 'imspooky532'. I want to clarify that the other account is owned by me and i had no idea that it is a violation to contest guidelines. I would not enter the contests with my other account now and i apologize for all the trouble. if it's possible to remove the 'skipped' verdict then please do so, if not then i understand
as i have commented earlier with my account siddharthraj532, this account will no longer be used in contests from my side as it violates the guidelines. i once again apologize for the troubles. My verdicts for yesterday's contests are 'skipped' (the answers were correct), if there is a possibilty to fix this then i'd be grateful, if not then i understand.
my attempts to submit the C problem were ignored, but to be honest, I didn't understand why, my solution was written there like someone else's, but it's so sad that I solved the contest almost the whole round, and using the theme of my previous solution from the site on similar topics informatics(it's site) (many have there there is the same solution) I got a disapproving result on a task similar to the one I solved in the courses I attended (in my city, and the people on the list, as I understood, live far from me), the task was on the topic of simple counting, where I considered all possible cases according to the formula that I came up with on the go and used (to count the number of elements) to multiply by the value(write something how I can correct or apologize, I have been going to my rating for so long, solving the 2nd division, even though I was not so good at it) I am open to any form of verification to clarify this situation. Thank you for your understanding and attention to this issue. I am looking forward to solving this problem.
Your solution 237967879 for the problem 1914B significantly coincides with solutions peasantbird/237967879, srivathsava_337/237999030, Rohith_Sai_143/238001247, hitheshsiripireddy/238006274. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
Hi! I am hoping to prove that I wrote my solution independently and did not share it with anyone, and I hope that you would be able to help me reinstate my participation in this contest. I wrote the solution 237967879 on IntelliJ independently. My submission was prior to the 3 other submissions, and I had to come up with this solution on my own. I do not know who these people are, nor did I share my answer with anyone as I immediately just went on to do 1914C next. As such, I am not sure how these people may have copied my answer, or perhaps our solutions just coincided because of the limited number of ways to solve this problem.
I hope you or Mike could take some time to help me look through this! If there is anything else I need to show to prove that I wrote this answer on my own and did not let anyone else copy, please let me know!
labuda
Attention!
Your solution 237968347 for the problem 1914C significantly coincides with solutions lankapothusivakoti/237961744, NarzullayevMe/237968347. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
MikeMirzayanov — I'm not a cheater for this contest ! Similar codes may be coincidental.
WOW !! You submitted the same code, changing the variable name mb to ar .. And is it a coincidence ??
Your submission: 237968347 t = int(input()) for _ in range(t): n, k = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split()))
Your friend(/co-cheater)'s submission 237961744 t = int(input())
for _ in range(t): n, k = map(int, input().split())
I am writing in response to the email I received regarding the similarity of my code with others in the recent contest.
I would like to firmly assert that at no point did I engage in any form of dishonesty or cheating during the competition. The code I submitted was entirely the product of my own thought process and effort. I had diligently worked on the problems and developed the solutions independently, without any external assistance or copying from any source.
I was not aware of the similarity of my code with that of other participants until I received your email. This coincidence is as surprising to me . I understand the importance of integrity in programming contests and always strive to uphold these values.
I am open to any form of investigation or scrutiny you deem necessary to clarify this situation.
Thank you for your understanding and attention to this matter. I look forward to resolving this issue.
If you look at E1 and E2, I was not able to think of the greedy criteria of a[i] + b[i] at first so i had brute forced it for E1. I coded this up in the last 5 minutes when the solution came up to me. Idk what else i can do to justify my innocence :/
Comment the message you received from the system here if you are innocent ..
System
flownn Attention!
Your solution 238049911 for the problem 1914E2 significantly coincides with solutions artemfad/238024787, karitkar7/238026318, manikanta2004/238028742, heckeruwuu/238042370,flownn/238049911, ayush_jhajharia/238050136. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790.
It is visible with naked eye. I can't understand why you are still claiming ...
Anyways, I ran MOSS on all 6 submissions ..
And you can check result here Plag Check Results
Though many solved it using the same logic, your implementation is the exact same which could never happen unless you had copied it.
I recently received a notice regarding a potential rules violation related to my submission for problem 1914D in the [Div 3] contest. Upon reviewing my code and the solutions mentioned in the notice, I would like to emphasize that my solution was developed independently, and I did not intentionally violate any rules. I also want to confirm that I did not use any common sources, and my code is not based on code snippets or logic from other participants during the competition. I understand the importance of maintaining a fair and competitive environment, and I take these rules seriously If the notice mentions unintentional leakage, I want to clarify that I did not use any online platforms with public access to my code, such as ideone.com with default settings I am committed to upholding the rules and integrity of Codeforces, and I am open to any additional steps required to resolve this matter. If there are specific guidelines or actions you recommend, please let me know, and I will ensure prompt compliance. Thank you for your attention to this matter, and I appreciate your assistance in resolving it. Sincerely, tripathiharsh1102
When would the editorial be out, now that the hacking phase is also over?
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
The tutorial finally comes out!
I have received an email from the system regarding my solution to Problem C matching with other users. I have done my code by my own and I did not share my code to anyone also but I don't know how my code is similar to others. Please return my rating.
As some of you, i got RE on test 24 for E2 problem. I didn't know that comparator must return false on equal elements. Even thou, I'd like to know WHY this submission got ac without changing the operator. 238177631
Providing a comparator that does not satisfy strict weak ordering to
sort()
is undefined behavior.So getting a correct answer is one of the possibilities.
Ohh thnx. Even tho, i got surprised that only chanching the #define int long long and removing the empty constructor got ac. Well, i will not leave anything by change again.
I've observed a discrepancy in the rating increase on my account. After solving three questions, my rating only increased by 32 points (from 970 to 1002). However, I've noticed other users who have gained a higher rating increase, such as 53 points (from 1065 to 1118) after solving two questions. I want to express my concern and kindly request a reevaluation or clarification on the rating calculation process. I understand the importance of fairness and accuracy in such systems. Could you please assist me in understanding the reason behind this difference? I appreciate your attention to this matter and look forward to a resolution. Thank you.
So far, I am satisfied with the situation of the citizens of our country. But we could do better. We are Russians!