Привет! В Jun/03/2024 17:35 (Moscow time) начнётся Codeforces Round 950 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов, после её завершения все успешные попытки будут перетестированы на успешных взломах. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Задачи были придуманы и написаны нашей командой: myav, Gornak40, ibraevdmitriy и Vladosiya.
Также большое спасибо:
MikeMirzayanov за помощь с идеями и системы Polygon и Codeforces.
Be_dos, Dominater069, 74TrAkToR, BucketPotato за красное тестирование раунда.
KseniaShk, cry, tolbi, ScarletS, nika-skybytska, sevlll777 за жёлтое тестирование раунда.
mahdi.hasnat, Phantom_Performer, mainyutin за фиолетовое тестирование раунда.
natalina, FBI, OldBrilliantMate, MADE_IN_HEAVEN, mz1 за синее тестирование раунда.
Romakolesn за бирюзовое тестирование раунда.
Всем удачи!
P.S.: Мы знаем об ошибке, возникшей при обновлении рейтингов за Educational Codeforces Round 166. Она будет исправлена до этого раунда. UPD: Мы её исправили!
UPD: Разбор
first one to comment on this blog.I hope the problems will be interestsing so everyone can enjoy them.
first one to commment on this blog hhh.i hope the round will be interesting so everyone can enjoy it.
Date and name of the round is incorrect or is it only me who is seeing round 925 instead of 950
Fixed it, thanks!
Vladosiya back to CM
Can anyone explain me how penalty works in Div 3. "Note that the penalty for the wrong submission in this round is 10 minutes.", I am confused what this 10 minutes means.
it's the penalty for a wrong submission in this round
In Div. 3 the most important thing is the number of solved problems. If 2 participants have the same number of problems solved, then a "penalty" is computed for each of them. The penalty is the sum over the solved problems of the number of minutes from the begining of the contest up to the accepted submission (I think that if you send 2 or more accepted submissions then the last one is the penalty giving one).
Penalty can also be accumulated by making wrong submissions, i. e. 10 minutes/penalty points per submission. Thus if you submit 3 wrong submissions and a correct one after 50 minutes from the start of the contest, your penalty will be $$$3 * 10 + 50 = 80$$$ for this problem. Do this calculation for each problem, sum the penalty and you get your total penalty.
It is best to have small penalty (i. e. solve problems fast with less errors).
Actually, every submission after the first accepted one does not count, so the penalty is (the number of wrong submissions before the first accepted submission) * 10 + (the time in minute the first accepted submission was made). This is why you can freely submit multiple solutions if you have any doubt in your previous accepted solution without worrying about the penalty in Educational / Div. 3&4 rounds (as opposed to normal Div. 1 or 2 rounds where the earlier solutions become WA penalty).
Thanks everyone for clearing my doubt.
Hopefully last rated div 3 for me
same
isn't it already unrated?
nah I signed up as a specialist
Well most probably you will become expert brother, congrats !
Excited for the milestone Codeforces Round 950! A big milestone for the community! :)
you're 50 rounds too early
Setting problems for each of the 950 rounds is not an easy task. It's worth celebrating every milestone. Big thanks to all the problem setters, authors, testers and MikeMirzayanov!
bro is teaching an expert about problem setting (aura -1000)
Anyways, he is right. Problem setting is a hard task
ik he is right, i have done problem-setting in few clg contests, but what's the sense of celebrating 950 ? has he been celebrating each round if that's the case
You are right, but you wrote about problem setting, so I commented about that.
agreed sir
I like when FBI tests the round ! I feel more secure
Problems are getting more difficult these days. I can solve at most B in div-3, div-2. Are testers creating more difficult questions? Previous questions were easier than recent ones, and question difficulty was according to Div, but now the scenario has changed.
As the problems change and adapt, we too must become stronger and evolve into more superior problem solvers
POST CONTEST UPDATE: i did not in fact get any stronger ;-;
احلى مسا عليك ياعم vladosiya يلي مصر كلها بتستناك تنزل بالديفاية
Please pray for my friend to be blue in this contest. Best of luck Mahi vai
hoping to return back the blue handle
My post contest discussion stream
To be honest in Div 3 its more difficult to increase rating than Div2 as in Div 2 you solve 2-3 problem is equivalent to solve 4-5 problems in Div3 and I think its also the case that many high rating people give it with their fake accounts.
have you considered that maybe the problems are easier?
lol
Statistically, and for reasons it's the opposite; lower divisions are easier to gain rating due to new accounts usually being overrated (note that the performance is calculated based on effective rating, not displayed rating).
People are often excited about their first unrated Div3. But I'm excited about my first rated Div3 as an expert. Good luck to all the participants!
People are often excited about their first unrated Div3. But I'm excited for my first rated Div3 as an expert. Good luck to all the participants!
Edit : They probably did me unrated haha, all good!
they unrated me too lol. tfw you can't div 3 abuse as an expert
Hurray!!! my 100th contest. lets see how it goes fingers crossed
Expert in 100th contest :) All the best !!
Thank you :D, again fingers crossed
Good luck everyone!
I am not sure I understand the participation rules. I recently hit 1600, but I do meet both criteria for being a trusted participant. However, when I enter the contest, it shows me "Out of competition".
I also wonder why the 'official standings table' only seems to show people under 1600.
It even states '[trusted participants only]' when I uncheck 'show unofficial', while not showing contestants ranked [1600,1900), so there seems to be some mismatch between the definition used by the standings and the one in the announcement.
If I understand correctly, to be in the official standings table you need to currently be in below 1600 and never have been above 1900. This is probably to allow people who briefly used to be expert but not people who were much higher at one point
Interesting, thanks!
Doesn't that mean that a contestant with top rating of 1900+ and current rating below 1600 will somehow both be rated and unofficial at the same time?
Edit: Oh, I guess it would not be that weird, since e.g. new accounts would be in the same boat. Still pretty funny to have unofficial participants who are rated.
It's not unofficial, it's "trusted" which basically means that the person belongs in a div 3 contesr
I mean unofficial as per the 'show unofficial' checkbox on the standings page. So if you wanted to see only the rated contestants, there's no easy way to do so, right?
Actually a good question which I unfortunately can't answer
YES NO forces
I am too dumb to understand the problem statement of problem C...
I understood the problem and when I build the approach, on checking the test cases I find out I was wrong and then tried again the same thing, similar things happened 4 to 5 times and now I think the test cases are wrong
i asked the authors,, "what is suitable sequence???"
they replied,, "It is the sequence which satisfy the problem statement"..
&& it was very helpful....
"Hmm Yes the Floor Here Is Made Out of Floor"
one thing you learn the hard way: it is almost always you who are wrong, not the testcases
How terrible problems to me!I should rest to think myself.
couldn't solve == terrible problems
You are right.Perhaps it's due to losing too many points and having a bad mentality.I should pay attention to my own problems
MAYBE hashmapForces
ORDERED!!
Excited to see the forest.
what competitive programmers think outside is like
Firstly ,i loved the problems but there might be too many problems of high difficulty, spent a lot of time solving F2 which was fun in its own way and didn't have any time left to read problem G.
F2 and G are nice simple to understand and practice some techniques. Overall round feels quite hard for rated participants
Miss G by just 1 second. Emotional damage
What was the intuition behind E?
The rows and the columns of b must be permutations of the rows and the columns of a. If you think about it, when you switch columns, you are just changing the order of the rows and when you switch rows, you are changing the order of columns.
what is time comlpexity to find vector in set if vector is sorted?
when swapping rows , u will swap the entire rows , when swapping columns , u will swap entire columns...
so elements in same row will tend to remain in same row and elements in same column will tend to remain in same column...that's all..
So won't taking the sum of each row and column and then checking whether those sum exists in both suffice?
you can see my code , it is quite clear ig.. I created two maps , first one for storing rows corresponding to every element in b and second one for storing columns for every element in b...
I just iterated in matrix A twice , first row wise and then column wise
when i iterated row wise , I checked that every element in the same row of a matrix should have the same row in b as well (I already have the rows of every element in b matrix pre-computed)
Did similar for columns as well...
264014966
fix first row and first column of b.
then check others
Can you elaborate a bit more on this?
If you fix the 1st row. You cant make any column swap later, because any kind of column swap will change your 1st row.
Do same for 1st column.
Then you can't swap anything else.
You can just check weather you got the sequence or not.
I spent 85 minutes on Problem E and cannot find the error: **** int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll t=1; cin >> t; while(t--) { ll n,m; cin >> n >> m; ll r1[n],r2[n],c1[m],c2[m]; for (ll i=0;i<n;i++) { r1[i]=0; for (ll j=0;j<m;j++) { if (i==0) c1[j]=0; ll x; cin>>x; r1[i]+=x; c1[j]+=x; } } for (ll i=0;i<n;i++) { r2[i]=0; for (ll j=0;j<m;j++) { if (i==0) c2[j]=0; ll x; cin>>x; r2[i]+=x; c2[j]+=x; } } sort(r1,r1+n); sort(r2,r2+n); sort(c1,c1+m); sort(c2,c2+m); bool flag=true; for (ll i=0; i<n;i++) { if (r1[i]!=r2[i]) { flag=false; break; } } for (ll i=0; i<m;i++) { if (c1[i]!=c2[i]) { flag=false; break; } } if (flag) { cout<<"YES\n"; } else { cout<<"NO\n"; } } return 0;
Your Answer: Yes
Correct Answer: No
Thank you
CODEFORCES wants us to communicate only in YES and NO
And sometimes MAYBE (problem B)
Maybe
I spent whole time figuring why there was RUNTIME in F , test case 3
E<C<D
Can someone explain why the answer to problem C in test case N5 is 'yes'? As I understand it, modifications should be applied in the same order, so all the modifications will be used on the first number, leaving no more modifications for the rest of the array.
It can be used on any number. Just last element in $$$D$$$ should be present in $$$B$$$
I think E was too easy to be a Div 3 E. Loved solving F1. Thought F2 was on similar lines of F1 but it was actually way more difficult. Overall a nice problem set!
If people didn't go for sequential solving, then E would be hugely accepted in this round.
are you kidding me , this happend with me again, solved F just after 15 mins contest ends.(same happend in round 949)
got 2 wrong in problem C, only if that didn't happened
++ same here
Here is a video Solution for Problem F
Is E that easy as comment suggests i think it's way easier than C. C is just an observation then use a greedy approach
Very cool problems for education, and according to today's DEFG and some recent Div3s, I think the problems are hard enough to make the round rated for Experts.
Agreed. But had experts knew it would be rated they'd approach round slightly differently
I don't have much experience with Codeforces, does anybody know what rating we could expect for problem C?
(I know that it won't be released for a few days, I just want to have an idea; I don't know if it's closer to 1000 or to 1800)
Maybe around 1100.
Not more than 1200 I would say
You can check on clist
Maybe too noob today, I failed to solve D, and it wasted me too much time and I failed to solve F1 in time:(
Luckily I'm out of competition.
Can somebody please tell me why my solution is wrong? Thanks in advance!
First, I reorder the columns according to the first row, and then check if all rows are same by converting them to string.
You do not add separators when concatenating numbers into a string, so
1 11and11 1are the same to you.Example test:
Really nice problemset! Kudos to the authors and coordinators for creating such an interesting round.
[Sorry, I was dumb and realized that my solution is actually correct, ignore what I said]
if the condition is already satisfied without removing any element, then i think you can just remove the last element.
Huh, but what if I need to remove more than one element?
Oh wait, I'm dumb lmao. Sorry all. After I remove it, I check the array after removing immediately to see if any of my removal is good, so there is no way that I will get to the point of removing more than one element
Can someone please help me in figuring out what's wrong with my solution to problem C?
https://mirror.codeforces.com/contest/1980/submission/264011923
I am calculating elements in
barray which aren't there inaarray. Now I check if the elements in thisdiffare there in d array too (also ensuring that the count of each element in diff is less than its corresponding count in d array). Finally I am checking that there should be at least one element in b which is equal to d[m-1].Thanks in advance!
erase erases all occurrences , you should find the val first and then erase 264052322
Oh fricc. Thanks a lot man!
It's fine Tanka
There is also a cool alternative since C++17 called extract which removes only 1 instance of an element from multiset
That's neat. Thanks!
YES NO YES NO
MAYBE?
nah pray for expect
can someone help me on D problem? I have wrong answer test N2(testcase 56). I am not sure but maybe my whole idea is incorrect, my idea is to solve this using dinamic programming, starting from the last.
https://mirror.codeforces.com/contest/1980/submission/264027336 this is my code
problem G is nice, too bad i started contest late :(
unordered hacks again
i was so happy that i got +85 delta. Now 3rd got hacked of unordered :(
how do u know of delta ?
carrot extension
I have wrong answer on problem D, and can someone help? I'm tring to solve dinamicaly, maybe my idea is wrong, I don't know for sure. https://mirror.codeforces.com/contest/1980/submission/264027336 this is my code. pls help
https://mirror.codeforces.com/contest/1980/submission/264046924
you can check with i +- 5 use one for loop :) 263959259
is it not sufficient to check only a[i],a[i+1],a[i-1]
checking only for i-1 , i , i+1 is sufficient , AC submission : https://mirror.codeforces.com/contest/1980/submission/264071477
can someone help me with another submission of same problem , idea is same just a little change in implementation. please find the comment where the doubt is elaborated https://mirror.codeforces.com/blog/entry/130032#comment-1155519
can anyone point out where i am going wrong?
Solved 5 problems in Div-3 for the 1st time
Failed in this contest desperately (-1000 aura)
It was unrated for me (+100 aura)
Still what did I do :(
rated for me but still failed
I did worse :(
what was the idea in D
You traverse the array, from 2 to n. The first index where gcd(a[i], a[i+1)<gcd(a[i], a[i-1]), you can either remove i-1, i, or i+1. You do all of it, and check if any of them gives you a favourable outcome.
bruh, it's just brute forcing all possible ways, and I thought gcd calculation would be a heavy operation and there should be a clever way to solve the problem
Well there may be a more mathematical side to the problem, but i guess in DIV3 its about logic and implementation ,however its not true everytime.
YES_NOForces!
After a long time, a contest that went well for me :)
YesNoForces Round.
Can someone explain how was i hacked? https://mirror.codeforces.com/contest/1980/submission/263943355
https://mirror.codeforces.com/blog/entry/62393
Can you tell me why this code gives invalid input during hacking.
Is there any other blog answering same question on python as Using any data structures such as Counter of collections ,sets or dictionaries,all get hacked to show TLE on system testing.
How to G(I'm not gonna be making hacks but if ure concerned just dm me instead of replying)
I can able to to solve problems till E after the contest with first submission but I can't do that during the contest time.Moreover I feel very shaky and make silly mistakes and blunder during contests. It this my fate / bad luck only or is there any lack of my skills on it?
It there, anyone please help me to overcome this frustrating conduct, share me some tips and strategies if you used to face these conditions before.
Advance thanks to you. May almighty bless you.
The solution is actually to take it slow. Even though there is a time limit, obviously, you aren't getting much from being fast if you make mistakes. Whereas if you focus on being slow and steady you make a lot less mistakes while gradually getting faster to the point where you are doing things fast and correct after a lot of practice.
So, recommend me the practice way. Do I practice from problemset section or participate in virtual contests? Which will be better for me?
You should give virtual contests, since you don't have the fear of making wrong submissions, once you are a little sure you will listen to your gut, that would surely build up your confidence!
You need to step it down a bit in regular contests and even if it slightly negatively affects your rating, you will learn a lot. Virtual contests are not a good solution because they do not normally cause the same pressure as regular ones
hello guys , would really appreciate if someone helps me through this , in round 950(Div 3) problem D , my approach was to brute force the implementation of how one element should be removed and then the gcd should be checked . The logic seems right because today I tried to submit the same logic with a slight change of implementation and it got AC . But I'm still unable to understand why was first approach failing.
First approach : to check if the currGcd is smaller than the lastGcd if so remove either ith element or i-1 or i-2 from the original array , did this by marking it -1 and then restoring the ith element that was marked as -1 after the recursive call where I check the gcd of the new array. I'm pretty sure that the mistake is in the -1 marking and restoring the element since its the only part that is changed in AC solution, but I'm unable to think of a case.
Link to the approach : https://mirror.codeforces.com/contest/1980/submission/263995703
Link to the AC approach with slightly different implementation : https://mirror.codeforces.com/contest/1980/submission/264071477
EDIT: Got the mistake it is if the first element has to be market -1 , in that case lst will be 0 according to the first approach , but the gcd of (0,a[1]) would always be a[1] , instead it should be such that I completely ignore the above mentioned gcd since i have removed the element (marked it as -1) so either start the loop in that case from i = 2 of else lst = 1e9 + 7 , prime number grater than any of the possible elements , hence the gcd of them being 1 always which would not hinder gcds
Can anyone please explain why Counter of collections in python(pypy3-64)often leads to Time limit exceeded on some questions even though the logic and time complexity is completely fine.(I am really annoyed by this problem as this has happened to me that questions were accepted initially but on larger test cases later,they were hacked or Faced TlE,and if I submitted them on different language like python3.8.10 or submit the same logic in another data structure ,the get accepted.) Ps:I found that it is not the problem only with Counter,but also sets . like in this question 1927C - Choose the Different Ones! ,[submission:245138579]is not accepted ,whereas [submission:245382629]is accepted as sets used are removed to lists.
can someone explain why does O(n) solution in C using python dict get hacked?
Same issue with me as I posted above,I think that python sucks in data structures as it has happened to me multiple times .I sincerely wanted to switch to C++ for coding but I do not have the time for it as i am proficient to write code only in python .I urge Vladosiya to either please clarify or give our solutions fair judgment.
same here i only enjoy coding in python and i think our solutions should be getting a fair judgement same as everyone else's, Vladosiya please look into this.
It's actually Python's fault: first of all, dict is not O(n) it's just average complexity of O(n) because it's a hashmap. But as others mentioned it can get as bad as O(n^2) which can be hacked. C++ has regular map (nlogn red-black-tree) and unordered_map (a hashmap) where the latter can be hacked as well... There is no discrimination against python here and I assume that if you implemented your own red-black-tree in python, even mediocre, you'd not get hacked. What happened here is just Python's problem that it doesn't offer a built-in nlogn stable map by default.
Edit: you can use OrderedDict in python I think
OrderedDict is just list of pairs, not a tree map
UPD: Mistake
oh, my bad then, thanks
edit: it's still a hashmap just preserves order so it's not what I thought it to be anyways
dictuses hashing, and has worst case time complexity of $$$\mathcal{O}(n^2)$$$ when you insert $$$\mathcal{O}(n)$$$ elements.Counteris a subclass ofdictso it's essentially the same. The way to make the worst case is well-known and is almost surely used by the hackers during open hack phase.can you please suggest any alternative for such cases,so that the alternative should do the same logic but in good time complexity?
The safest way would be finding a solution that does not use hash-based modules like
dict,set,Counter, etc. There are many custom libraries for balanced binary search tree that guarantees $$$\mathcal{O}(log(n))$$$ per operation, or something similar to such structures. If you really need to use hashes, using a custom hash function with randomization would work.Can you please tell then why konstantin_rokossovsky's solution to 1974C - Beautiful Triple Pairs i.e. 261980102 is accepted?Should it also not face TLE?or the Test cases for testing were not good enough to reject the solution?
Just a small bit of change in the keys invalidates hacks on another keys. I think that is also hackable, but since people don't have all the time it's probably just neglected.
I did not understand,can you please elaborate
Oh wait, didn't notice that it's from a different problem. In that problem's case the range of $$$a_i$$$ prevents hacks, because for sufficient amount of hash collisions you usually need a wide element range, and in that problem the constraint is only $$$10^6$$$, so it's difficult to produce hacks. I think only Java's
HashMapwas the only one prone to it.But the constriant for this problem was 2 * 10 ^ 5 for both n and m. So isnt it less than 10 ^ 6? Why did the hack work for this problem?
In this problem the constraint on the element's value was $$$10^9$$$, which is far greater than $$$10^6$$$. You need a wide range for the values to make many collisions when the hash's bucket size is large enough to cause significant slowdown.
Here is example of unhackadle dict: 247436179
Well, veeeery unlikely to be hacked to be precise
https://mirror.codeforces.com/blog/entry/101817
This was something I learned from this contest. For integer keys in particular, they are easily hackable. Using an XOR on top of your key like this might make it more resilient as mentioned in the linked article.
Someone else suggests str(key) is also a workable transformation.
Thanks!was helpful indeed
sortedcontainersis the typical starting point.But there is not any in-built library for sorted containers in python(atleast not for CP,I heard that you have to download it from Github pages for usage on your device.)
Oh, I thought it was available for import on the CF judge, pretty weird that it isn't!
First time attempting a contest, although I had made this account a long while back. I gave this contest yesterday and solved 2 questions, but I am still unrated. Can anyone please help me understand why? (Clicking on my contests link, no contests are displayed, but when I filter the search to unrated, this contest shows up). Can anyone tell me what I have to do to make at least the next contests that I give become rated, things are a bit elusive here.
Don't worry, ratings are just not in yet. They always take a few hours and in the case of this contest we had a 12 hour open hacking phase after the contest itself. The ratings are probably going to be updated later today
Can anyone please this solution for C :- 263941647
why it got hacked by TLE?
Lesson Learned... Use a prime number to make your Counter/dict/set in python SAFE... The collision problem is very interesting (and honestly quite dirty), but I guess we all (or most of us) have to learn the hard way... It seems quite impractical in real world use to use a prime number (for example in Python I saw someone use p=109008647)... Which will save you from a hack, but again in the real world how useful is it? Probably not much... Unfortunately that means I don't get credit for 1 of my solutions this time around... (Better to learn now than later I guess).
Good suggestion. But maybe simply using an ordered data structure is better :)
In python you can use OrderedDict instead of a normal dict, you will get a slightly worse time of O(log(n)) instead of O(1), but you will be much safer overall.
P.S I am not sure but I think I've read once that this prime trick is also hackable, but I can't remember the methodology.
UPD: OrderedDict are no good also, never the less, SortedDict is the python equivalent to std::map in c++.
I think as OrderedDict is also a hashmap ,it can be hacked as well,and it is also O(1) (and not O(logn)).I do not find any improvements in using OrderedDict instead of Counter
You are correct, OrderedDict are no good also.
Just made a quick search, found that the one I meant is SortedDict
This one is indeed sorted and takes log(n) per get/delete.
Problem with this SortedDict is that it cannot be used on codeforces. You can only use it locally on your system.Hence,it is of no use as a competitive programmer.
So strange. Any ideas why?
I don't know precisely ,but it is not any standard library that is itself incorporated into python.Instead it was rather a project whose focus was to develop some data structures in python like sorted sets of c++,which are in C++STL,so that they can use it freely during CP.Feels like python is useless where data strucutres are concerned :(
I wish I can be Specialist
You will be
thanks for your wishes
At this delta in your first rated rounds? You'll probably end up way higher.
Can someone please explain me the in-depth intuition on how to solve problem C, whats concepts are involved?
For the array
d, we can observe that some elements are useful while others are not. For those elements that are not useful, we wish they could be overwritten. That is, for the current element, if it is useful, then the useless elements before it can be moved here and subsequently overwritten by the useful element. Ultimately, we need to check whether arrayahas transformed into arrayb, and at the same time, there are no useless elements left.The essence is that you can customize the first index for each pair of the "modification operations". Your job is to Restore the array as much as possible...by customizing wisely. Used Google Translate, my English is not good
Most importantly we need to transform the original into the target, so for every position where they differ we need one operation with value specified by the target array. If there aren't enough, then it's impossible.
If there are enough operations, we still need to make sure all the other operations don't destroy our progress. We know we can do multiple operations on a single index, which allows us to overwrite unnecessary/bad operations. So we look at the last operation. If the value doesn't exist in target, then we for sure cannot end up with target since it will be written at some index. Otherwise, all the unnecessary/bad operations can be overwritten by the last operation and we're happy.
Hi, i failed to solve problem C. Can someone help me what am i doing wrong? Its giving tle for hidden tc 7
(Python User) here is my code
it's correct code. You have TLE. On this task problems with TLE on python
i still cant understand why because similar codes got accepted but my code is failing.
like for this submission code is ac and for my code where i also made some changes thinking that it will be ac code is still having tle on tc13. Can you tell why so
system test is not already end
on this problem some people use dict or Counter which the time gets for it O(1) instead or OrderedDict with O(log(n)). Solution with OrderedDict are not hacked
try pypy, that being said even my pypy solution was hacked so idk.
use OrderedDict instead of Counter
will OrderedDict make code any better as it maybe having some overhead as compared to Counter and this case imo both the codes i have linked in the above comment are almost identical and i dont see anyway why my code failed there.
I agree with u, i have the same trouble, but users Counter and simple dict got TLE for this reason((
when are those tc added which are successfully hacked? Is it during hacking time or after system testing?
after system testing
some issues on task C with python(TLE)
I think the test case from hacking are not added yet because my solution was hacked yet when i run the same code it is accepted .it shows the contest status as finished and standings as final. Please, fix this so that contestant can review and improve their code easily.
Thanks
System testing hasn't started yet.
i see that now, standings were shown as final standings, which seems misleading if system testing is pending.
Please do something about the cheating Vladosiya, MikeMirzayanov. Its on a massive level, people are getting negatives just because of these, and it really demotivates the cause of such a platform. Please try plagcheckers, or anything which might be suitable.
why is the problem c hacked a lot? can someone explain?
Because many people used Counter of collections as data structure for maintaining occurences of elements,but it is in worst case O(n*n).It is pretty easy to find the worst case for it as it is quite standard.I myself got hacked as I ignored that fact.only those solutions passed which used their own hash function.(This was all for python submissions,I do not know about those in other languages).
what kind of hash function would work for thus problem then? i am newbie and first time something like this has happened to me. I am still very confused lol.
you can also see this for python :-
https://mirror.codeforces.com/blog/entry/101817
Why you put a question like E which is directly available on geek for geeks https://www.geeksforgeeks.org/check-if-a-given-matrix-can-be-converted-to-another-given-matrix-by-row-and-column-exchanges/ Here is the link for the solution . If possible please remove this question from the contest Vladosiya pls look into this. As people shared this blog with their friends too and no plagiarism can be applied on it
What happened to my problem C solution? 263930829 I didn't use unordered_map or that sort of thing, I used multiset, and I think this is a O(nlogn) or O((n+m)logn) solution. Why it got TLE?
It's because of
multiset.count, related blog: https://mirror.codeforces.com/blog/entry/122960OMG, luckily I learn this trap in an unrated round, thank you orz
Are there any similar pitfalls?
[I already learnt how unordered_maps/sets and multiset.count give TLE and FST, the hard way.]
How to do G? I've looking at others solutions they used trie to find the maximum or, please do explain
it's a bit advanced for ur level, maybe solve other problems first
my bad, I misread bitwise 'exclusive' OR as bitwise OR, now I solved it. Try solving for bitwise OR, it's probably much more difficult problem. it's well within in my level bro I have 7 solves
Bro, with cheating one can full a div3(not saying u cheate), and I also read it as OR, that's why I said it's too advanced, thanks for the pointing at the xor
Why is the system-testing incredibly slow for this round?
most probably because of problem c. they added a lot more test cases for it. more than 100.
Does anybody know why Edu/Div.3/4 System Testing takes a lot longer than Div.1/2 System Testing?
1) more participants 2) easier tasks -> more submissions
isn't system testing taking longer than usual today
I gave the contest yesterday. It was my first contest. I solved 2 questions A and B and they were accepted also. I am still unrated? Why is that so?
Wait till system testing is completed
I am new here. What do you mean by system testing?
after the contest, codeforces runs another set of tests to double check the codes, which will take a bit more, wait till tmrw and definitely will be updated
How to G
On my profile this contest show as unrated and i solved 2 questions in contest. Can anyone tell me why it is happening.
Ratings are not in yet because there were TONS of hacks for problem C (because people were using hashmaps) and if the hack is successful, the test gets added to the test pool. What that means is that it took a lot of time to rejudge all submissions with all those tests which takes a lot longer than usual since you sometimes have 10 tests but here you probably had way over 100 which means that judging problem C took longer than an entire contest usually does. Tests were only finished less than an hour ago so it will probs take a few more to update ratings but you will get your delta :)
I want to know why my rating is increasing by very few points. Like a 800+ rating candidate with rank around 22k in this contest got +72 in his ratings. But my current rating of 722 only went up to 727 , even though my rank in this contest was 21.5k around. This similar kind of issue has happened to me in previous few contests also.
The higher your rating is, the harder it is to get a higher rating .
Each account has both the displayed rating (shown in user profile) and the effective rating (hidden; used for rating calculation), where the former starts much less than the latter and rapidly catches up during the first 6 rounds of the account, so a new account always 'looks like' that it gains a lot of rating at the beginning.
Tl;dr: https://mirror.codeforces.com/blog/entry/77890
I have some questions about how the hacking system works.
I'm asking this because my solution for C got TLE after system testing. I learned about implementing a "safe hashmap" after I saw a lot of people get their solutions for C hacked. Then I resubmitted my solution with the new hash function after the contest, which was accepted.
Do Div 1 and Div 2 contests typically not have a hacking phase? Are hacking phases just a part of Div 3 and 4?
Finally, can anyone submit hacks to solutions? Even if the hacker is not participating in the contest or isn't rated/trusted for the contest?
Submission
Can anyone tell why this solution got TLE?
you used unordered map
Can anyone plz tell that in this contest i submitted my solution of problem B that is choosing cubes and it got accepted. Now after the contest it is showing wrong answer on test2 but it got accepted in the contest itself. Not only this when i now submitted exactly same solution it got accepted on test 2 als0. How is it possible?
Your code has an undefined behavior. In
if(a[k] == num),kcan go out of bounds ofaand therefore anything unexpected can happen.Ok thanks for replying but now it is accepted so is it that in contest it detected but now it not.
It's not about detecting it or not, it's just that anything can happen depending on your luck. For example, you can 'luckily' pass the tests if any of going out of bounds didn't actually cause any issues on the program's logic, but if you're unlucky then the program can read a false value from the outside of the vector and think it's a real value that leads to a wrong branch. In another case it can just immediately get segmentation fault, or even randomly get into an infinite loop, etc. You just can't predict what will happen.
problem d, solution 1 — 263972949 failed system test (TLE), solution 2 — 264171599 passed all the tests, code — same in both letter by letter, only difference — solution 1 submitted on Python3 while solution 2 submitted on PyPy3, result — got a "-1" in place of a "+"
I have solved 2 problem in this contests why it gives negative 17 points to me.
Rating changes depend on how you performed in the contest ~ your rank in the contest and your current rating and not on the number of questions solved.
.
How did you gain +111 rating in educational round 166 when its showing you solved 0 questions?
Cheater, skipped bro. Rating recalculation did not happen yet.
Hi @codeforces team & @Vladosiya, Well recently i have got a message from your side that there is a plag detected in my code of problem F1 and its a violation and i was asked to submit proof of that there are solution/editorial which are available before the contest.
So for this problem i have a reference of few questions that i have solved previously in other platforms i.e. Atcoder and leetcode and by the reference of which i was able to solve the question. The link for the problem is being attached below:
https://atcoder.jp/contests/abc216/tasks/abc216_d
https://leetcode.com/problems/remove-covered-intervals/description/
Also just now i saw i also got it for D problem, Which i feel is incorrect as it is a basic logical question. Although i dont have any proof for Problem D as it is a logical, mathematical/constructive algorithm based problem. But i assure that my solution is better for both the problem statement, as i have gone through every id solution that is provided by you in the mail. And in both the question my solution is different from any other participants.
So yes the allegations by your team is wrong. I appeal you for revalidation of my code. And i also appeal to please remove me from plagiarism category as i have never been involved in such acts before.
Hope I can get 2000* rating in 2024!