Всем привет!
Приглашаем Вас принять участие в Codeforces Round 744 (Div. 3) – раунд для третьего дивизиона, который состоится во 28.09.2021 17:35 (Московское время). Раунд был составлен совместными усилиями меня и MikeMirzayanov, и мы очень надеемся, что задачи вам понравятся и покажутся достаточно интересными.
Отдельно хочется поблагодарить MikeMirzayanov за помощь как в составлении, так и в разработке задач для раунда. Это второй Div. 3 раунд, в создании которого я принимаю участие, но только первый, в котором я готовлю задачи полностью, так что без его руководства я бы потратил на это гораздо больше времени.
Помимо этого отдельная благодарность nizamoff, andreumat, QAZZY, Vladosiya, CtrlAlt, vladmart, Igorjan94, okwedook, ashmelev и Aris за тестирование раунда и фидбек по задачам, а также Gassa и geranazavr555 за вычитку и корректировку условий – благодаря вам этот раунд стал заметно лучше, чем мог бы быть без вашего вклада. Ну и наконец, спасибо всем, кто примет участие в раунде! Раунд будет содержать от 7 до 8 задач и расчитан по сложности на участников с рейтингами до 1600, однако все желающие с рейтингом 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-часовая фаза открытых взломов. Мы постарались сделать сильные тесты, что, однако, не гарантирует, что фаза взломов будет безрезультатной.
Вам будет предложено 7-8 задач и 2 часа 15 минут на их решение. Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке – это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Независимо от того, являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Всем хорошего настроения и удачи!
UPD: Выложен разбор задач!
Is there a way to become a tester if there is no communication with codeforces admins?
For such rounds, I myself usually write requests to test those who have a long history of participation (years), have no incidents with code matches, and so on. I will write to you in PM :-) Thanks!
Thanks! I would be grateful if you give me at least one chance.
is there a specific level for the tester Would someone below expert be useful
Hello MikeMirzayanov, my code was only once found plagiarised a few years ago because I was stupid back then and from that point on I haven't cheated at any platform. Can I still dream to become a tester at codeforces in some contest in the future?
I think specialist isn't enough for testing maybe some authors would I have seen newbies test sometimes maybe it's good to see what a beginner could do but generally it's not very useful because the more skilled the tester is the more possibility he can find issues with the problem
And I did that stupid mistake like 3 times not to gain any raiting I would never gain 1 raiting like that but I participated while I had terrible focus and i didn't want to lose so much rating before Scpc and got caught the last time and that made me feel like shit and I didn't do that again since that time but I guess it's too late to fix that who cheated once isn't trust worthy anymore because it's possible to not get caught if you put some effort on it they wouldn't trust you even if you won't do that again because maybe now you could cheat without them knowing :(
It's also one of my questions.****
@nizamoff your pp is awesome.
what is pp?
Profile picture?
i think it is "butt"
My first unrated round.
I love seeing your progress chart. Inspiring
i hope to be specialist after this round ..
It may be a rare 8-problems div 3 round!
Also it's rare to see something like this : same same same same same same same same same same same same same same same ....... code.
different people 🤯
OH MY GOD! I can't wait for this div 3 contest! I heckin' love div 3 contests!
BatChest! I heckin' can't wait to become cyan!!
As a contestant, I hope the time complexity of me becoming an expert is $$$O(1)$$$.
10000000000000000 is $$$O(1)$$$...
As long as the space complexity of your corny jokes remains $$$O(1)$$$. :P
Will a non-trusted participant be rated? New one here can not be trusted.
Yes it would be rated for non trusted participants with a rating below 1600
Just failed School's selection round for NOI.
Just relax and keep going.I really admire that you have the opportunity to participate in information competition in the stage of middle school. The future will be full of light and hope,Just keep going. I believe as long as you persist on learning programming, u can become the person u want. No matter NOIP first level, or NOI gold medal,u still have the opportunity,u still have the hope and energy!!!!!
This is one of most awaited contest for me , a week without contest on codeforces is hard :( .
I hope I can become blue after this round.
Same for me. Best of luck!
I hope I can become cyan after this round.
I hope I become green :)
honestly, many of us was waiting for this round, thanks
Very nice! Looking forward to my first rated round
I wish that i become Specialist after this round. Upvote for best wishes. Thanks and Good luck to all.
Oops!! downvoted by mistake
it will be hard but wish you success!
A round after more than a week. Wish ya'll the best of luck.
Always better to participate in contest instead chatting with gf. Hahaha
What is a gf?
I see you're a man of tradition
yes, man of culture indeed.
Will this round be easier than the last Div.3 contest?
This was my first comment, and I don't know why this is so downvoted why is it downvoted?
If you are less than Expert. Then there are high chances for your comment to get downvoted. This happens with me too.
Edit: thanks for proving what i said above.
I am on a streak lately, I became 5* on Codechef few days back and qualified for hackercup T-shirt too, I hope my streak continues!
Wish Me Luck!
UPD: Didn't do very good but since I avoided negative delta so I think the streak is still on.
Loved the gradual increase in difficulty in the last contest conducted by +doreshnikov , hope to see a simillar round today!
There is too much of a difficulty gap b/w A and B !! B is not at all a regular Div.3 B problem.
B was an easy one if you have solved pancake sorting on leetcode . Here instead of reversing the array, we have to rotate it and with that less constraint even a brute solution will be accepted
Any problem can be described "easy" in someone's perspective. But it wasn't an ideal Div.3 B problem.1.
Yes, I agree E1 was much easier than B.
implementationforces
Sorry to bother folks who are participating in today's round, but today's round requires a serious plag check, problem B had a sudden surge in submissions from 3K to 7K in just 5 minutes. Like seriously? I don't think B was an easy one to solve for most folks below the 1300 rating (I got it right after like 5-6 attempts).
i agree
Just because you can't doesn't mean anyone else can't.
Firstly, who said I didn't? Secondly, I am referring to the sudden surge in the submissions for B in such a short time, not about who's able to solve the problem.
I was able to do it mate
While Polycarp is on vacation Casimir is taking over.
Today's round had nice problems (especially F and G). Thanks to MikeMirzayanov for amazing m2.codeforces.com platform (I had connection problems and the lightweight version was very useful). :D
Enjoyed this round. Especially E2.
Holly… Amazing div. 3 round! Btw. anyone knows why cf-predictor is down?
Mike must have closed off Codeforces API to reduce server load.
How to solve E2 ?
Suppose l_i is the increase in the number of inversions if you add i_th element to the beginning and r_i is the increase in the number of inversions if you add i_th element to the end.
It's easy to observe that neither of l_i or r_i depend on the order of first i-1 elements. So, just add min(l_i,r_i) to the answer at each step.
For E2, first apply coordinate compression.
Then, using a segment tree/binary index tree, calculate whether prepending or appending the element is better. It's better to prepend the element whenever there are more processed things greater than the current element. Better to append the element whenever there are more processed things less than the current element.
130179241
It's better to prepend the element whenever there are more processed things greater than the current element. Better to append the element whenever there are more processed things less than the current element.Is there a proof for this process working greedily? I mean wouldn't the answer change for the (i+1)th element change depending on where the ith element is placed? A bit confused over this intuition. (The position of the ith element may add to the inversion count of the (i+1)th element)
Not really, the
ithelement can only be either added to the beginning or the end, so the only thing that matters is among the first(i-1)thnumbers,how many numbers are smaller than theithnumber if you are adding it to the beginning, and how many numbers are greater than theithnumber if you are adding it to the end.You can also solve it using:
Is there a way faster than nlogn for E2? I was so happy when i came up with a multiset, but it still TLE
I used coordinate compression + segment tree. Multiset won't work as you can't find distance in constant time. There is something called ordered set, maybe use that. I haven't used it personally.
wait, does
distance( ms.begin(), iterator );take linear time?Yes.
I did use ordered multiset
You can view my Submission here
Thank you mate I didn't know about that, Here is my submission using ordered_multiset submission
Well I learnt something, thank you guys!
Loved the contest, The Problem D on this contest is similar to a previous Div 3 round D problem.
Link to the similar problem : https://mirror.codeforces.com/contest/1506/problem/D
I request everyone , who read the problem D or solved it to go through it also once.
The concept required to solve both the problems are similar.
It is such a nice question on the application of Heaps(Priority Queues).
Good round. BTW, how to solve G?
The final answer will always be less than $$$2*max(Ai)$$$ so you can make a 2-d dp of $$$n * 2e3$$$ where $$$dp[i][j]$$$ will give the minimum length of remaining part of segment on the right assuming that you are at $$$j$$$ distance from the start of the segment after processing first $$$i$$$ values.
Code
If I am not wrong, in your soln you have assumed there exists a soln when we never go to any -ve number. Can you give proof of this?
P.S. Correct me if I am wrong.
I initialised the first segment at positions greater than 0 as well to handle this case.
So, you took all the points from [1,2e3] as possible starting points. Cool trick. I figured out that max ans will be 2e3 but didn't know how to maintain both the boundaries as well as current location.
Thank you!
Thanks a lot! I solved G!
Did I just participate in a div-2 round?
No
What would be problem rating of E1 ? 800 ?
why nlogn solution give TLE on E2?
My segment tree solution passed. So, you must be doing something wrong.
i was using policy based data structure. Its complexity is logn i guess?
You have to read the documentation on policy based data structures, but I won't be surprised if
order_of_keyorcountis $$$\mathcal{O}(n)$$$.countin a multiset is $$$\mathcal{O}(k + \log N)$$$, where $$$k$$$ is the count returned.order_of_keyis $$$\mathcal{O}(\log N)$$$.Note:
find_by_orderis also $$$\mathcal{O}(\log N)$$$I think he has TLE because of
mss.count(). He should usestd::map. I think his code will be like:Yes, it gains AC: 130194814
Why ans1 = pos . I think it should be more than that numbers less than a[i] will be in multiple frequency but your ordered set constains them only once
I have ordered multiset, because in
using orsetI have comp $$$\textbf{less_eqaul \lt \gt }$$$How are you Handling Duplicate elements?????
std::mapIs your op_set ordered multiset or similar to multiset.??
ordered multiset
Time complexity of
mss.count()is logarithmic in size and $$$\textbf{linear}$$$ in the number of matches. So I think your solution is $$$O(n^2)$$$130192451 — AC with some changes to your code
It was because of multiset's count function, it can go up to O(N) (N : number of occurrences of the number). Should have used a map to count the occurrences.
where to access the editorials of #744 (Div.3)?
Round#744 Editorial
Great round. But I would have appreciated some drawings in G, as in C.
RIP my rating . I was trying right shift in problem B :')
RIP
#metoo
Such a waste of effort . After 1 hour , I have realize that .
C,D,E1 all took 1 hour just . B took whole the time and feeling terrible for this >_<
It took me 1 hour to solve problem C, but 21 minutes to solve D,E,E1, and E2.
It took me 37 minutes to solve ABDE1 and 1.5 hour to solve C. 20 minutes to solve E2 (after the contest). Amazing!
I also did the right shift first, after I just changed the value of shift offset from d to r-l+1-d.
I didn't able to solve any question By the way I try solve the first question but unable
the next time will be good :D
As I remember, Problem D was already used in past contests with different statement but same idea
It would have been better if F had integers upto $$$10^9$$$ instead of 0's and 1's .
The problem would have been similar to this and we would have to just process Range AND Queries on individual components
My reaction seeing that the guy name was Casimir:
The problems were literally all over the place.
Even deciding which ones to solve was more difficult than E1.
How to solve G? something like dp?
Can someone elaborate the problem C please, still I can't understand what it wants!!
It's asking you to check if you can construct a grid solely using 'V' shaped patterns of size K or greater.
4 7 1
why here answer 'NO', There is a V shape from position 3 3 of size 1
Because the first '*' in the first row is not a part of any V. The smallest V (K = 1) consists of 3 '*'s.
THE EASIEST E1 EVER! :)
Can someone help me to figure out the mistake with my logic/code for problem E2?(thanks in advance)
Logic: During each insertion, let the current element be K, we add min(number of elements strictly lower than K, number of elements strictly greater than K) to the answer. I implemented this using PBDS multiset.
my submission
I too have an almost identical solution (and an identical result).
Considering that I created it with only ~15 minutes remaining, there must an embarrassing mistake somewhere in there.
My submission
ordered_set contains unique elements only once so this code fails for duplicate elements
ordered_set contains unique elements only once so this code fails for duplicate elements
I changed it to multiset by changing less to less_equal in the following segment:
From:
To:
Oh! they it may work, I always use pairs my code is similar to you.
you are not doing mp[v[0]]++;
my code works flawlessly now, thanks a lot bro
T~T,It was another very violent topic, and then I saw that I finished it in three minutes, but I felt good on the whole
How to solve G?
A to F easy solutions with Code and Explanations Happy Coding.
Just check if the Count of B equals (length of the string)/2.
Iterate this algorithm n times.
For each, i from 1 to n find an index of the minimum element from the array i to n , lets name it ind. and left shift the whole subarray i to ind (ind — i) times.
For each element {i, j} of the matrix go as far maximum upwards in both left and right until both the top elements of the V (tick) are '*', if the size of this V > k mark all the elements we currently visited in a temporary matrix.
If there is a '*' left in the string which is not marked in final temp matrix return no else return yes.
Just always chose 2 people which have maximum meeting hours left.
Iterate the given list left to right
Take a deque.
If it is empty push the current in the deque. If the current element in deque is less than the front push it in front of deque else simply push in back of the deque. Bonus :- how to solve a different problem if elements are not unique.
Similarly iterate the given list left to right If deque is empty push the current element anywhere.
Maintain a gnu pbds ordered set which gives us a number of elements less than a current element in a vector. so for each upcoming element find a number of elements that were less than and greater than the current element with the help of the ordered set now if the number of elements less than the current element is greater push the current element to the back of the deque and add greater as ans to the inversion count else do the opposite push the current element in front of the deque and add nuber of lesser elements in the answer to inversion count.
Connect nodes i to (i + d) % n in a graph. Find all the cycles in that graph. if the bitwise and of all elements of any cycle > 0 return -1;
else
put all those elements in the exact form of their appearance in the array to make it cyclic append the same elements array twice and let's say if there are n elements in the array.
find the shortest path of each one to the nearest 0 in the cycle. take a maximum of all such shortest paths.
with this method, we will really make all elements 0.
Bonus, assume that elements are not necessarily binary then also the below code and algorithm can be modified easily.
@Fawkes For problem 2 (B) the problem statement mentions:
Any sorting method where the number of shifts does not exceed n will be accepted.`` So did this mean that when we take one interval i.e from I to n (like in your soln) we can only shift max n times or did it mean that the total number of shifts shouldn't exceed n?because if we take the example: 5 4 3 2 1 then for I = 0, we shift 4 times, and then I = 1 we shift 3 times so the total would exceed n, no?
You may shift by more than 1 in a single operation. In your example, you pick shift by 4 (as a single operation) and get 1 5 4 3 2, which fixes 1 in it's correct place in 1 shift operation.
I see, so it mean that the sum of all the interval shifts i.e
<< xsum of all suchx's can exceed n but the total number of times we perform this shift must not exceed n, correct?Exactly. :D
what is the reason to decrease two big values by only one can not it be decreamented by minimum of these .I mean to say min(i1[0],i2[0]). why does not this process give best answer
while(pq.size()>=2) { pair<ll,ll>pp1=pq.top(); pq.pop(); pair<ll,ll>pp2=pq.top(); pq.pop(); v=min(pp1.ff,pp2.ff); c+=v; if(v>0) ans.pb(mpr(pp1.ss,mpr(pp2.ss,v))); pp1.ff-=v; pp2.ff-=v; if(pp1.ff>0) pq.push(pp1); if(pp2.ff>0) pq.push(pp2); }Imagine three people with times: 6 6 2.
You would answer 6, since you would pick both persons with a = 6. But the real answer is 7, those two people with a = 6 should talk with each other 5 times, and the last person should talk to both of them separatelly.
Why am I not able to hack any solution or even been able to lock any problem during Codeforces Round #744 (Div. 3) ?
Div 3 is different from Div2 and combined rounds. Here, you get a hacking phase of 12 hours after the contest ends.
Nice round, with great problems.
Although the order of problems could be better, the problems were great!
Thanks :)
Most unbalanced div $$$3$$$ round ever :(
The difficulty was like $$$A \lt E1 \lt B \lt D \lt C$$$ as I felt.
What was the key idea for A?
In problem $$$A$$$, you can either remove $$$(A, B)$$$ or $$$(B, C)$$$, that means you've to remove $$$B$$$ whenever you're removing $$$A$$$ or $$$C$$$, so the $$$\text{count}(B)$$$ should be equal to $$$\text{count}(A) + \text{count}(C)$$$ to make string empty at the end.
You just have to check that.
Thanks.
In problem F, I have used the fact that once some a[index] becomes 0, it will always remain 0 and will turn a[(index+d)%n] to 0 as well..
So, at each step if there's no new index where 0 is formed.. ans will be -1, else we can store these new indices to use them in the next step till all indices are converted 0.
So, if at each step "X" new indices are formed.. the process will go on for N/X iterations .. making it X*(N/X)
I am not pretty sure about this complexity and method.. Can someone provide a counter case/hack it, or affirm it ?
Submission
Your approach is pretty much similar to my approach. I did multisource bfs. Time complexity of my solution is $$$O(n)$$$.
Link to my submission
Yeah right!! mine is also in a way multisource BFS only.
Who made these test cases? E1 hacks are going insane with very straightforward hack.
Can you give an example? I don't know what makes so much solutions to fail :0
The downfall of E1...
Can someone explain approach for C plase
Try to find potentional center cells,say
{x,y}and calculate the minimum of its left and right arms, sayd. Ifd>=k, add a tick in another grid of sizedat{x,y}. After you have done this for all potential center cells, check whether the original grid and the grid you made are same or not. My solution:130153692B submission WA I was trying to solve be for more than 1 hour but it was still giving the wrong answer. The codeforces engine was giving a different answer and my machine was giving different. Mine was correct. I later submitted the problem with very minor change and it got accepted. It was some undefined behaviour I guess, if anybody could explain why that happened, I would be really grateful. Accepted Solution
please take a look into hack #758216, the result is "unexpected verdict".
(I mistakenly submit invalid input, then I got such result. Maybe the validator of G is wrong.)
I have tried a video solution for the problem F: https://www.youtube.com/watch?v=8qC3qyQsE8s Hope it will help you if you need it.
Hi any one could help me to solve problem D, give me the idea or full code, this is my code i got WA, cause their is no tutorial, thanks in advance, and sorry for my English. void solve() {
int t; cin >>t; while(t--) { int n; cin >>n; vii v(n); lp(i, n) { cin >>v[i].f; v[i].s = i+1; } sort(v.rbegin(), v.rend()); vii ans; int i=0, j=1; while(v[i].f&&v[j].f) { ans.pb({v[i].s, v[j].s}); v[i].f--; v[j].f--; for(int a=j;a+1<n && v[a].f < v[a+1].f; a++) swap(v[a], v[a+1]); for(int a=i;a+1<n && v[a].f < v[a+1].f; a++) swap(v[a], v[a+1]);
} cout <<sz(ans)<<"\n"; rep(i, ans) { cout <<ans[i].f<<" "<<ans[i].s<<"\n"; } }}
When posting your code, try to include them in spoiler and block tags, so that they maintain their indentation. As for
D, the basic idea is to use amax heap, (priority_queue in C++). The idea is to take two indices with the maximum sociability every time and have them meet each other. Their sociability decreases by one everytime, so, you decrease that and if their sociability is still greater than 0, push them back into the max-heap.can you please explain as to why letting two with the max sociability meet each other would result in maximum no. of meetings ?
We would want to make sure that the number of meetings is the maximum. Taking the indices which currently have the maximum sociability does this, because everytime, we are decreasing the sociability, so the indices that have maximum sociability changes after a point of time, which means meetings are scheduled as long as they are possible. Let us take a counter-example: say,
A={1, 2, 3}. Now, if we considered the indices with the minimum sociabilty, we will be able to schedule only two meetings->(0-1) and (1-2). On the other hand, if we considered indices with the maximum sociability everytime, we will be able to schedule 3 meetings->(2-1), (2- 1) and (2-0).Хорошие системные тесты для задачи E1 :)
I would like to report a system bug in problem G.
When I submit my solution, it gets time limit exceeded at test set 22. But when I looked at test set 22, it have three test cases, and first one array length is 10000. But problems says the total number of G does not exceed 10000, so it is not a valid test set.
I look at others solutions passed during contest, and the total number is 18. So test set 22 is not generated by authors, but by hackers after the contest.
Then I tried to generate an invalid test set (3 test cases with total number of n 30000) and hacked others code (I only hacked people who are not officially participate the contest), they all succeed.
Therefore, please remove these test sets that sum of the n > 10000, and rejudge these hacked solutions for problem G. It is unfair for participated who solved problem G but exe time is larger than 333ms.
It's rare to see something like this : same same same same same same same same same same same same same same same ....... code.
different people 🤯
you are right lots of cheaters got high ranking but it is worthless if you dont know the logic and directly submit it.
Thnx for great round, even though I wasn't so luky. Anyway I may have misunderstood problem B, I used Bubble sort considering swaps as d = 1 circular shifts, on paper it all make sence but yet it get me wrong answer on test 2. this is my submission 130155379 , could any good one of you help me with it ?
Swapping adjacent elements is not an efficient way of sorting the array.
To go straight to the point, the maximum number of operations/shifts your program could need is $$$\frac{n(n-1)}{2}$$$ when the the array is in the form $$$a_1 \gt a_2 \gt \dots \gt a_n$$$.
By the way the number of such swaps needed to sort the array is the same as the number of inversions in the array if you want to look into that.
I'm new here, so the round should be rated for me but, the contest is showing itself in the unrated section in my profile contests, also I'm not in the standings. I did solve 4 questions during the contest. Can anyone tell me what's this issue?
Did you register for the contest?
yes
Lesson: READ. READ ALL PROBLEMS.
Better Lesson: See the submissions in dashboard to find next easiest problem.
What is invalid test in Hacking? I have also used endl but dtill getting this error?
Validator 'validate.exe' returns exit code 3 [FAIL Expected EOLN (test case 1, stdin, line 3)] close
Is it only for me or for everyone that codeforces is acting wierdly today ..It is tryng to covert to russian all the times.
Send ur generator
there's strict check for tests. I guess you added extra space in the end of line
Could anyone please help me understand why I got TLE in E2? I used Fenwick tree + coordinate compression, so this should be O(nlogn) but somehow it fails in testcase #18.
My attempt from the contest (or slightly modified version that's easier to read).
Same here but with seg tree, I really don't understand
Omg found it, man. It's because of the unordered_map. Here is the solution with unordered_map and Here is the solution with map. The first one fail with 2 seconds while the second passes with 343 ms. Like BROO. Why is this happening? I thought unordered_map is faster than map :(
Damn, you're right... Wow, this feels terrible.
It is always sensible to use map over unordered map. You may think that unordered map can give you O(1), but cases can be generated to exploit it's hashing method which will result in Collison everytime you want to use it which will be O(n). Long story short, use map which guarantees O(lgn).
Of course I would do that but I didn't know about it. I just thought the unordered_map is just a map where the keys are not in order. :) Fml
but if tests are not generated to kill hashing method, unordered_map runs faster than map.
Totally. I think the idea is that in most cases an additional log(n) doesn't matter enough (and doesn't give TLE) so using std::map over std::unordered_map would be strongly preferred for me in the future since it makes me not worried about anti-hashes.
It is actually possible to use unordered_map without worrying about collisions, here : how to avoid getting hacked using unordered_set
I think E1 is more suitable for the difficulty of B than the actual B...
Hi !
is there any one who can help me with this ?
in problem B , the first test ,my output to testcase 3 is : 2 : 1 3 2 — 3 4 1 but is gives me a WA : wrong answer Element a[0] = 4 is greater than element a[1] = 1 (test case 3)
but its not logical ! if you shift the elements in the way that I said , the array will be sorted !
can you find my mistake ? my submission : 130240370
I guess what you are referring is the Jury's answer. for every [l,r] that you're considering you do cout<<l<<" "<<r<<" "<<1; instead do cout<<l<<" "<<r<<" "<<(r-l); The question says left shift so all the number are shifted towards the left and the first number goes to the last. According to your intepretation the opposite happens. 130115425 have a look at this for reference
THANKS !
I have solved four questions in this contest and having rank between 2500-3000, but now they are saying that I have copied the solution of the problem, but I haven't. I am coding in ideone.com, is there any problem with it. I thought after this I will have a 1300+ rating. please help, how will I convince that I do not copy any solution...
-_-
In D, the most common solution that I have come across involves heaps and priority queues. However, in my initial approach I used DP by modelling the problem as the 0-1 Knapsack Problem. I 1st calculated the sum of the sociability of all the people in a test case, and since each talk would require the sociability of both the participants to decrease by 1, the maximum possible talks in a meeting is
(sum of sociability)/2Therefore, the size of the knapsack can be set equal to(sum of sociability)/2and the weights set and the values set will be the same, i.e., the input array of sociability of each person. Therefore, by finding the maximum weight that can fit inside the knapsack, we can maximise the number of talks in the meeting. However, my solution fails on the 69th test case of the 2nd test set. Here is my submission. I would appreciate any help in pointing out the flaws in my logic or implementation.Solutions to all problems in video format :)
solutions
thanks, i subscribed too.. keep it up
Nice contest with interesting problems.
Hello, I solved 1 problem in Div 3's contest yesterday. But my rating went down. What is the reason?
Your rating depends on your previous rating and your rank, not on how many problems you solved. Read this for further understanding.
Failed system testing for Problem E2, could someone tell me why this is TLE? The second last test case also had
200000length but it passed well within the time limit. My codeIt is the unordered_map in the worst case time it's time complexity for insertion can be O(n) and not O(1). https://mirror.codeforces.com/contest/1579/submission/130266275 just by using map your code gets AC
thanks, that's tragic. makes me wonder when the unordered_map shouldn't be used since i even passed the pretests so didn't give it a second thought
Sometimes you might want to use pbds hash maps, like cc_hash_table and gp_hash_table. There are helpful tutorials on CF — the authors even mention how to prevent excessive hash collisions, which might be helpful for the casual unordered_map as well.
I followed this blog and was able to pass the test cases. should I just keep it in my template? haven't seen anyone using this though
I've seen ppl using this; personally I've used it a few times. But in this very case, it wasn't needed — note that ordered_set is very slow, but it is enough to complete this task. The operations we need to support are "add x to the set" and "count how many elements that are < / <= are on the set". If we somehow distinguish equal values appearing on distinct positions, we can complete this task simply with order_of_key queries. My suggestion is, instead of adding x to the ordered_set, add f(x) = (x * BASE) + pos, where BASE is some constant (sufficing BASE > n) and pos is the position of the added value. Now, for all values y < x, f(y) < x * BASE, and for all values w > x, f(w) > x * (BASE + 1) — 1. As you can see, the queries are pretty straightforward now, and we don't suffer from unordered_map etc.
To conclude, sometimes changing the values might be easier and more efficient than the hash function.
Can someone please tell me the approach for F and G.
F: If a position has a value of 0, it will never change. If a[i] = 1 and a[i + k] = 0 (where k is the length of rotation), then we can make a[i] = 0 in one turn. (maybe you need to switch a[i] and a[i + k], I don't remember if the rotations are left or right oriented)
Let's build a circular graph of n vertices. If a[i] = 0, then dist[i] = 0, else set the initial distance of vertex i to inf. Then use a multisource BFS from all vertices with dist = 0 to compute the answer — the edges start at vertex i and go to vertex number i — k (mod n). Whenever a vertex labeled with 1 is accessible from a vertex 0, we add him to the queue, update the "distance" etc. The answer is the maximum distance over all vertices (or -1, if for any vertex v, dist[v] = inf holds after the computation finishes).
Thank you it was helpful.
when will the editorials be released? (sorry for being a little impatient)