Привет, Codeforces!
В 24.10.2019 18:05 (Московское время) состоится Educational Codeforces Round 75 (рейтинговый для Див. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Так же от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Привет, Codeforces!
Мы хотели бы пригласить вас на курс Михаила MikeMirzayanov Мирзаянова "Advanced Algorithms and Data Structures", который пройдет в Барселоне с 6го по 24е января 2020 года.
Курс будет состоять из 3х недель обучения (5 дней в неделю). Программа включает в себя ежедневные лекции и практические занятия. Это будет познавательно и интересно!
У вас будет шанс познакомиться и пообщаться с Михаилом,который будет рад поделиться своими знаниями и историей создания Codeforces.
Мы рады предложить специальную цену 1,000 евро* для всех пользователей Codeforces.
Регистрируйтесь по ссылке ниже и мы свяжемся с вами! Торопитесь! Всего 10 мест свободны.
* Стоимость не включает проезд или проживание.
Мы также хотели бы порекомендовать вам статью, опубликованную в нашем блоге на прошлой неделе о 5 причинах, из-за которых традиционные университеты не могут идти в ногу со временем.
UPD: Начало раунда отложено на 30 минут.
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | neal | 7 | 199 |
| 2 | Anadi | 7 | 205 |
| 3 | risujiroh | 7 | 208 |
| 4 | imeimi | 7 | 229 |
| 5 | jiangly | 7 | 273 |
Было сделано 96 успешных и 196 неудачных взломов.
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | cxk0707 | 0:02 |
| B | wangziji | 0:05 |
| C | Bohun | 0:06 |
| D | guyan | 0:16 |
| E1 | TwentyOneHundredOrBust | 0:15 |
| E2 | TwentyOneHundredOrBust | 0:14 |
| F | Radewoosh | 0:19 |
UPD: Разбор опубликован
I hope the statement will be clear and simple this time .
Your hope prevailed :)
yeah ^_^
We are happy to offer a special price of 1,000 EUR* for all Codeforces users.Is it more expensive for Codeforces users than for other people? 1.000 EUR without accomodation and travel. Wow
Ожидаем традиционно высокий класс Educational раундов, так сказатб.
Can anybody tell me the difference between
Educational Codeforces Round XXandCodeforces Round XX? Thanks in advance.Educational rounds (Edit: and div 3 rounds) are in ICPC format (Each problem has same score) + has 12 hours open hacking phase after contest. Other Codeforces rounds are in CF format, different problems have different scores, which decay over time.
Thank you very much!!!
Sometime the contest wasn't an educational contest , but it also has 12 hours open hacking phase.
That is Div3 Round
Thanks.
could you please tell what does hacking phase means?
You can read other participant's solution and suggest an input that could make their code to fail or to give a wrong answer. If you achieve that you have hacked the other participant solution and he/she loses the points of the problem. I believe you obtain some points also
https://www.quora.com/What-is-the-open-hacking-phase-that-starts-after-an-educational-round-in-Codeforces
Please try to put an interactive problem.
They are interesting to solve.
Problemset has already been prepared
Or has it?
Yes, I agree on some part with you, they are interesting to solve, but the very code for maintaining the query limit, and doing query at various steps is a bit frustrating,not to forget the flushing of output.I cannot copy paste the test cases :(
Don't name it as frustrating call it as challenging.
I think MikeMirzayanov should conduct a Data Structure and Algorithms course in India.
I think MikeMirzayanov should once conduct a course on DSA in India.
Yes, it would have much registrations.
Any particular reason why you mentioned India?
"Because everyone wants to learn".
So other countries people don't want to learn?
Did I say that? I am saying that he should also conduct once in India.
Some people just want to watch the world learn.
Because India has highest number of people who want to do coding. Maximum participation is always from India
Yeah, but how many people will participate because it certainly will not be free
As enthusiastically as they participate in ICPC(" It is also not free ").
See charges in the blog entry a special price of 1000 euros, I don't know how this charges will translate into INR but it will be high, how much are you ready to pay if you get a training from him?
I think Money never comes in between learning!
Yeah, you are right at this
Is it just me or nobody can see any top rated users??? not a single user in the page.!
same here
delayed!
The start of the round is postponed by 30 minutes.
Начало раунда отложено на 30 минут.
Why?
How Could a Game Developer even Write a comment ?
I don't like when contests are delayed
It ruins the organization of our days. 30 minutes is a lot.
But I can understand, if there's an issue with the problems. Better to delay + fix. :/
Yeah !
I wanted to give the round badly but it looks like I can't :( because I have to catch a train by 23:00 IST. All the best to everyone out there and I wish everyone a high rating :)
Your train has been delayed by 30 minutes
I wish that indeed was the case xD
But you'll know about it 15 minutes before departure
It's frustrating to wait for another half n hour.
But it was life saver for me as the prev time for contest was clashing with the dinner time in my college XD
It nearly clashes with every college's dinner timing...but we can manage
Why delay :/ Now I won't be able to participate.
Delayforces is back 8)
It's for the better
Hooray! Now i can finish my dinner.
Same for me Yaay.
In fact, I had to go to sleep later because of the contest been put off :( (start at 23:05 here)
keep in touch
I think it is better to delay the contest, than to have huge queue time's or unresponsive contest page....
let's look at the timeline
coincidence? i think not
Вот и повод потратить 1к
A Bad Day :(
I had a very bad day too. Didn't have a good idea for B & C. That's strange because these days I spend hours practicing on much harder problems. I found D much easier than C. I spent too much time on C and B and couldn't come up with a solution.
Finally, near to the end of contest, I submitted solutions for B & D and it got Accepted. However, my ranking is currently 1900 something and I would probably get back to blue. It was a really bad day!
Well,I think my template of NTT needs changing :(
I am still unable to solve C in Contest. WTF am I?
I wasn't even able to solve B, even though I believe I came up with a correct solution! Such a disappointment for me as well. :(
Let's practice more together :'(
How to solve D?
Binary search for the answer.
I was doing the same(binary search) but Wa on test 2 can you explain your idea ?
Yes, of course. So, to check if one answer $$$X$$$ is valid, we need to have at least $$$n/2 + 1$$$ numbers >= $$$X$$$ in our set of numbers. After having all this numbers, we exclude the ones that decrese the most our sum (from $$$X$$$ to $$$l_i$$$).
How do we know that if X is valid, then X-1 is also valid?
maybe u missed that for employees that you are assigning as >= median they may have L more than the median value thats what stuck me on test 2.
I thought E1 was pretty pointless, it would be better if it was replaced by a task with difficulty between D and E2?
The questions were really nice they challenged my implementation skills, kudos to the setter
What was testcase 2 in problem C?
Is F solvable without FFT? I know a solution where you need to calculate $$$(1+2 \cdot x)^a \cdot (1 + 2 \cdot x + x^2)^b$$$ or something like that—is it the only way to do it?
I solved it using NTT in $$$\mathcal{O}(kn \log{} n)$$$.
First if we look at coefficient of $$$x^j$$$ in $$$(1 + 2 \cdot x)^a$$$ then it is equal to $$$\binom{a}{j} \cdot 2^j$$$. Similarly coefficient of $$$x^j$$$ in $$$(1 + 2 \cdot x + x^2)^b$$$ is $$$\binom{2 \cdot b}{j}$$$.
Now it's enough to use one NTT/FFT to evaluate this multiplication. But I think it was possible to get accepted on solution you described.
What would be the right way to approach E1 or E2?
We can approach it in a greedy fashion.
First of all, consider each voter as a pair (Mi, Pi) and sort all the pairs in ascending order of the Mi values.
Now lets iterate in the reverse order (i.e from the voter with highest Mi value to the one with the least).
We want to be sure that we are buying a vote only when its necessary, do be sure of this lets define whats the necessary condition of buying a vote.
Suppose we are at index i (when iterating backwards), and have purchased cnt votes from the suffix of voters [i + 1, n], and in the worst case scenario we can buy votes from every voter in the prefix [1, i — 1], thus getting a total of i-1 votes from them. So at best we can have (i — 1 + cnt) votes.
If (i — 1 + cnt) < Mi, we are forced to buy a vote thus this is our necessary condition.
To buy a vote we can use a minheap which at any index j stores the values Pk for all voters k from j to n, whose vote we have not bought yet. If after checking for the necessary condition to buy a vote at index i, there is a need to buy a vote, we can take the minimum value of Pk from the heap and increment cnt and add this cost to our result, otherwise we keep iterating backwards.
Implementation of the above idea: 63349135
I found that sorting cost $$$p_i$$$ for the same $$$m_i$$$ dont matter, but I cant tell why. Some one have idea?
Can anyone provide more formal proof? Thank you
https://wcipeg.com/problem/ccc17s2p5 E2 problem...
WA test 2.
Checked your submissions on your profile, TC 2 hit you hard.
Darn. I got WA on TC 2 for each of B, C, D too before AC, but this was...
How to solve C ?? and D, was it binary search ?
For C, note that if you divide the number into vectors of odd and even integers, you can see that you will always be able to get any merged sequence of those two vectors. Then just merge as in mergesort. For D, you can just binary search and use greedy.
I did the same, but why this code gives TLE? any help.
https://codeforces.me/contest/1251/submission/63335135
Thank you :)
You were making a vector of a large size for every test case. In this case, it would be easier to push_back elements, and would also pass the limits.
Can you explain 'D' in good detail?
For D, you do a binary search on the value of the median. The upper and lower bounds on the median value can be deduced from the minimum and maximum possible values of the medians without the constraint of the sum. Now we need to check whether the median m is achievable. For that we need to check if we can add some w_i's to the l_i's so that w_i + l_i <= r_i and the sum of the w_i's is not more than the total money — sum of l_i's, and the median is equal to m. So find those i's with l_i < m <= r_i, and also those j's with l_j >= m. We can find how many numbers we need to set equal to m using this, and the best way would be to choose the i's with the largest l_i's from the first set of i's we had. This is the essence behind the solution.
C: Make a vector for even numbers and vector for odd numbers
Now we can see that the number who will print first is the first number of odd numbers or the first number of even numbers
And same for the second number.
Be careful when you use all of odd numbers or all of evens numbers
My solution for B that passed the pretests-
Count the number of 1's in all the strings ( let's call it c1) Count the number of 0's in all the strings ( let's call it c2) If c1 and c2 are both odd and there is no string given of odd length — answer is n-1 else answer is n.
Is this correct and if yes can someone please explain why?
For B, for the n-1 strings, we can do this - For each of the first n-1 strings, traverse towards the middle and check if it is a palindrome. If there is a change, just swap with the first element of the nth string. This gives you n-1. Now the answer can only be n or n-1. If there is any odd length string, you can do the operation mentioned above keeping that string as the last string and doing stuff to the middle element (instead of the first element). If there is no odd length string, you can get away with parity arguments and show that the answer is n-1.
Why is that strategy always optimal though?
Can't there possibly be some setup where there is no odd string and picking greedily from the last is sub-optimal?
From the strategy given, the answer is either n-1 or n, as in the earlier post. My solution was to check if the last one had an even number of 1s or not. Let us suppose that the last string has an even number of ones. Construct the string from the ends and towards the middle. Let r be the reference to the first element of the first string. If you find a difference, at the left and the right indices, then one of them must be equal to the element at r, wlog, let it be 0. Now since there is an even number of ones in the last string, between the indices left and right (both exclusive) there must be an odd number of both 1s and 0s. So we can swap the element (element at right or left) that was not equal to the element at r with the element at r, and then swap the digit (which was originally at r) found between the indices left and right with the element currently at r. This whole operation keeps the element at r fixed, and also preserves the fact that the substring from 0 to left is the same as the reverse of that from right to size-1. We can keep doing this till left and right are separated by at least 2 elements. If the number of 1s is even, we would end up with 00 or 11 in the end, and this would provide a construction for n. Now suppose that the number of 1s is odd, and there exists a construction where all n strings are palindromes. In that case, every string would have an even number of 1s and even number of 0s because every string is of even length. But this is a contradiction, and hence we are done. The answer is thus < n, and therefore must be n-1.
Let's grab all 0's and 1's, and remove them from their spots. Then, wile we have at least a pair of 0's or a pair of 1's, keep putting them into the free spots symmetrically (skip the middles of odd-length strings, and call them just middles). If we are done with symmetrical positions, continue filling the middles as much as we can. At some point we will only have {0, 1} or {1} or {0} or {} left.
If nothing is left (=both c1 and c2 are even), hooray. If only one 0 or 1 is left (=either c1 or c2 is even), that means we have only one position left, and it has to be some middle — and we can fill it with that number, hooray. The last case is when both c1 and c2 are odd, and then we have {0, 1} left. There are 2 cases how this could happen: either we had two middles left free (then we can fill them, and this requires having at least 1 (in fact, there will be 2) string of odd length), or we have two free symmetrical positions left in some even-length string. In the latter case we indeed cannot complete it, because all strings are of even lengths, and therefore, to make all of them palindromes, all 1's and 0's have to be paired, which is not the case.
https://codeforces.me/blog/entry/70802?#comment-553430
At a certain time during the contest, there are more people who have solved E2 than that of E1, that's interesting.
It's because of people with rating more than 2100. They don't need to care about rating as the round is unrated for them. So maybe some of them didn't bother to submit their solution of E2 at E1.
In the last contest I was using an already deleted pointer, and this solution passed E2, but gave RE on E1. I was going nuts before I found that mistake.
How to solve problem B?
Pure bruteforce works lmao https://codeforces.me/contest/1251/submission/63319464
Notice that to construct a palindrome you need two of the same character so each time subtract two. I am pretty sure the answer is either n or (n — 1) but I was too lazy to think.
Oh and also length 5 palindrome = length 4 palindrome + any character so just let it as length 4 :) (ABCBA) <-> (ABBA) + (C)
if there is an string with odd length then all of the strings can become palindrome.(ans =n) else (all lengths are even) you count number of 0's if its odd you can fix at most n-1 strings else (its even) you can fix all of them and answer is n
Why if there is an string with odd length all of the strings can become palindrome?
Because the middle digit in the odd palindrome becomes kind of an option so you can use it to help other strings become palindrome.
I got this, but the second case when number of zeros are odd, why we can fix at most n-1?
when you have odd number of zeros there will always be a string with odd number of zero and odd one (since all string are even o+o=e).. This string cant be a palindrome, hence n-1.
https://codeforces.me/blog/entry/70802?#comment-553430
Check it out
solutions for A,B and C
... keep a iterator i set to 0.then if a[i]==a[i+1] then don't add a[i] in answer and increase i by 2 else add a[i] in answer and increase i by 1
...1.Notice that if i and j are 2 indices with same parity with i<j then in the final number the index of i will be less than j. 2.problem reduces to find the lexicographically smallest sequence which has subsequence a,b where a=[i:array if parity(i)=odd] and b vica versa. this can be computed in O(n)
...notice that the rearrangement can be made in any way subject to the condition-total sum of the number of zeroes is same as in initial one. now let x be count of zeroes and y be count of ones
first sort the sequences by length and then try to fill maximum with the x and y such that it is palindrome in greedy way
I can't write binary search in a proper manner. $$$Binary\, search$$$ gods, take me.
I can't either, it never converges >:(
Workaround: make break condition (r — l > 3) and check each value from [l, r] after that instead. Always works :) :) :)
I ended up doing this sh*t too:
If you are looking for a maximum $$$x$$$ that satisfies certain condition ($$$func(x) = true$$$), always keep the range such that $$$func(left) = true$$$, and $$$func(right) = false$$$. It is then quite easy to update:
Can u tell the condition for finding minimum value... Thanks..
func(i) = arr[i] < arr[i + 1]
Just reverse the condition for left and right;
Always keep the range such that $$$func(left) = false$$$, and $$$func(right) = true$$$
answer = right
check out the topcoder tutorial
E is duplicate of a canadian problem: https://dmoj.ca/problem/cco17p5
Can any one help me to find the test case where Exactly my code is failing?
Problem A : https://codeforces.me/contest/1251/submission/63335924
UPDATE:Found The test case :aaakka ->Ans : a
Why are contestants allowed to hack their own submissions? Shouldn't this be disallowed? You should be able to hack anybody else's test case but not your own.
include<bits/stdc++.h>
using namespace std;
define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
define pb push_back
define all(a) a.begin(),a.end()
define lb lower_bound
define ub upper_bound
define pii pair<int,int>
define ld long double
define int long long int
define F first
define S second
signed main() { fast; int t; cin>>t; while(t--) { int n; cin>>n; string s[n+1]; int on = 0,zz = 0; vector<pair<int,string>>vp; for(int i=1;i<=n;i++) { cin>>s[i]; int sz = s[i].size(); vp.pb({sz,s[i]}); for(int j=0;j<sz;j++) { if(s[i][j] == '0')zz++; else on++; } } int ans = 0; sort(all(vp)); for(auto it:vp) { int nn = it.first; if(nn&1) { if(zz&1 && on&1) { if(zz>=on) { if(zz>=nn) { ans++; zz-=nn; } else { int rem = nn-zz; zz = 0; if(on>=rem) { if(on == rem) { if(on%2 == rem%2) { ans++; on-=rem; } else break; } else { ans++; on-=rem; }
} else break; } } else { if(on>=nn) { ans++; on-=nn; } else { int rem = nn-on; on = 0; if(zz>=rem) { if(zz == rem) { if(zz%2 == rem%2) { ans++; zz-=rem; } else break; } else { ans++; zz-=rem; } } else break; } } } else if(zz&1) { if(zz>=nn) { zz-=nn; ans++; } else { int rem = nn-zz; zz = 0; if(on>=rem) { if(on == rem) { if(on%2 == rem%2) { ans++; on-=rem; } else break; } else { ans++; on-=rem; } } else break; } } else if(on&1) { if(on>=nn) { on-=nn; ans++; } else { int rem = nn-on; on = 0; if(zz>=rem) { if(zz == rem) { if(zz%2 == rem%2) { ans++; zz-=rem; } else break; } else { ans++; zz-=rem; } } else break; } } else { if(zz>=on) { if(zz>=nn) { ans++; zz-=nn; } else { if(zz<=0) break; int rem = nn-(zz-1); zz = 1; if(on>=rem) { if(on == rem) { if(on%2 == rem%2) { ans++; on-=rem; } else break; } else { ans++; on-=rem; } } else break; } } else { if(on>=nn) { ans++; on-=nn; } else { if(on<=0) break; int rem = nn-(on-1); on = 1; if(zz>=rem) { if(zz == rem) { if(zz%2 == rem%2) { ans++; zz-=rem; } else break; } else { ans++; zz-=rem; } } else break; } } } } else { //cout<<ans<<" "<<zz<<" "<<on<<endl; if(zz%2 == 0 && on%2 == 0) { if(zz>=on) { if(zz>=nn) { ans++; zz-=nn; } else { int rem = nn-zz; zz = 0; if(on>=rem) { if(on == rem) { if(on%2 == rem%2) { ans++; on-=rem; } else break; } else { ans++; on-=rem; } } else break; } } else { if(on>=nn) { ans++; on-=nn; } else { int rem = nn-on; on = 0; if(zz>=rem) { if(zz == rem) { if(zz%2 == rem%2) { ans++; zz-=rem; } else break; } else { ans++; zz-=rem; } } else break; } } } else if(zz%2 == 0) { if(zz>=nn) { zz-=nn; ans++; } else { int rem = nn-zz; zz = 0; if(on>=rem) { if(on == rem) { if(on%2 == rem%2) { ans++; on-=rem; } else break; } else { ans++; on-=rem; } } else break; } } else if(on%2 == 0) { if(on>=nn) { on-=nn; ans++; } else { int rem = nn-on; on = 0; if(zz>=rem) { if(zz == rem) { if(zz%2 == rem%2) { ans++; zz-=rem; } else break; } else { ans++; zz-=rem; } } else break; } } else { if(zz>=on) { if(zz>=nn) { ans++; zz-=nn; } else { if(zz<=0) break; int rem = nn-(zz-1); zz = 1; if(on>=rem) { if(on == rem) { if(on%2 == rem%2) { ans++; on-=rem; } else break; } else { ans++; on-=rem; } } else break; } } else { //cout<<it.second<<" "<<ans<<" "<<zz<<" "<<on<<endl; if(on>=nn) { ans++; on-=nn; } else { if(on<=0) break; int rem = nn-(on-1); on = 1; if(zz>=rem) { if(zz == rem) { if(zz%2 == rem%2) { ans++; zz-=rem; } else break; } else { ans++; zz-=rem; } } else break; } } } } } cout<<ans<<"\n"; }}
Been scratching my head for over an hour, trying to find out a mistake in my D solution. The idea of my solution is the same as discussed by many in the comments. Got WA on test case 2.
Can someone please help me find it?
My submission: 63336144
Been scratching my head for over an hour, trying to find out a mistake in my D solution. The idea of my solution is the same as discussed by many in the comments. Got WA on test case 2.
Can someone please help me find it?
My submission: 63336144
I did the same thing and got WA :(
mid_sum += (mid_ls.size() - (n / 2) + lc)Maybe cast mid_ls.size() to int? Maybe an overflow happens, because size() is unsigned.
It probably isn't this, but maaaybe?
I'm surprised, it worked! Thanks!
Earlier I had the practice of typecasting size_t every time I used it, but then sometimes I used to think that anyways, it's going to typecast by itself, then why bother! Well, I guess I know now why to bother!
Thanks again!
AC submission: 63345119
This guy https://codeforces.me/submissions/amr_abdelazim is hacking his solutions of his own fake account https://codeforces.me/profile/Amr_Abdelazim01 . He tried very hard to hide the coding style of both account but it is revealed to be same in these 2 solutions https://codeforces.me/contest/479/submission/59876211
https://codeforces.me/contest/474/submission/63271187 Kindly look into the matter cheaters like these are ruining the platform.
In problem D i did not find the function to be monotonic as for many cases I found the function to be discrete.Can anyone help me how there is solution by binary search for such a case.
Start with the lowest possible answer. That will be the case, when all the employees get their lowest possible salary, and the median salary will be the median of the list of
lof all employees.Now try to increase the answer by 1. For the sake of simplicity, imagine that currently, all the employees have distinct salaries.
CASE 1: Now if the
rof employee havingsalary = median salaryis greater thanmedian salary, then you can directly increase that employee's salary by one, and your overall median salary will increase by one.CASE 2: Otherwise, let's suppose that the
rof the employee having hissalary = median salaryis itself equal tomedian salary. In this case, we will try to find an employee whose current salary is less thanmedian salary, but whoseris greater thanmedian salary, then increase that employee's salary tomedian + 1, so that the overall median salary will increase by one.If neither of the above case is possible, then it is just not possible to increase the median salary anymore.
Suppose that the maximum median is $$$m$$$, and you sorted employees in ascending order of their given salaries, where the $$$\lceil\dfrac{n}{2}\rceil^{th}$$$ employee is given salary $$$m$$$. To show that you can achieve all the medians down to the lowest one, you will always need to decrease one or more of the salaries of the first $$$\lceil\dfrac{n}{2}\rceil$$$ employees so that their maximum becomes $$$=$$$ the new median. If a new median $$$m_2$$$ can't be obtained because $$$l>m_2$$$ for some employee, you can swap him with an employee among the last $$$\lfloor\dfrac{n}{2}\rfloor$$$ employees whose $$$l\leq m_2$$$ (and his $$$r$$$ is obviously $$$\geq m_2$$$ because it is $$$\geq m$$$). If no such employee exists, then there are at least $$$\lceil\dfrac{n}{2}\rceil$$$ employees with $$$l>m_2$$$, and the median can't be decreased more.
https://codeforces.me/contest/1251/submission/63338046 https://codeforces.me/contest/1251/submission/63344390
These are two of my submissions for problem D. The 1st one gave run-time error on test-2 and the 2nd one got accepted. The only difference between these 2 submissions was in cmp() function. (I used > in 2nd one whereas >= in the 1st one)
Can anyone please help me figure out why did 1st one give run-time error whereas the 2nd one got accepted?
This is expected behavior. See https://stackoverflow.com/questions/45929474/why-must-stdsort-compare-function-return-false-when-arguments-are-equal
Got it. Thanks!
You can never use = in a comparator function because if a=b it will return true for comp(a,b) and true for comp(b,a) which is ambiguous behavior. A comparator should be such that if it returns true for comp(a,b) it must return false for comp(b,a).
Got it. Thanks!
Help! What does "Unexpected verdict" mean in the verdict of hacks? This verdict comes out at hack #594802.
Does that mean I have hacked the std solution or the validator?
It is fixed now.
Thanks! Now up to 16 solutions of F were hacked by me. It's amazing that there are no such tests prepared by the authors.
This guy is just unbelievable see this hacked solution https://codeforces.me/contest/1251/submission/63344943
He deliberately put the if condition to print 1 so that he can hack his own fake account solution . and see this https://codeforces.me/submissions/Amr_Abdelazim01
He hacked his fake account solution almost 12 times with different if conditions to print 1. Strict action needs to be taken against users like this https://codeforces.me/profile/amr_abdelazim
These are all the fake accounts that I have discovered so far whom the owner have hacked by putting a if condition to print something nonsense when the input is something specific like if(string=="dfsfdfh45") print("456");
https://codeforces.me/contest/1251/submission/63335128
https://codeforces.me/contest/1251/submission/63316807
https://codeforces.me/contest/1251/submission/63342216
https://codeforces.me/contest/1251/submission/63341635
https://codeforces.me/contest/1251/submission/63344050
God people will do anything for the rating . People like these should be banned.
They punished themselves by spending time on the most useless effort in the world, because hacking does not even influence rating in Educational rounds.
Oh I didn't know that seems like they are also unaware about it . But this tactic is brought to light now who knows for how long people having been using tactic to gain rating through hacking in other rounds.
.
Is it wrong? Why so many negative votes. Please correct me atleast
Let the number of strings with odd number of ones and odd number of zeros be $$$a$$$, and the number of strings with odd length be $$$b$$$. Answer is $$$n$$$ if $$$b \geq a\ \%\ 2$$$, else $$$n-1$$$.
Reason: Only strings with an odd number of both bits can't be made into palindromes by themselves, but two such strings can swap bits to make each other palindromic. That leaves at most one string if we have an odd number of such strings. This string can only swap bits with strings of odd length, which will make the number of both bits even, and hence make the string potentially palindromic. So at most one string can be left potentially non-palindromic if we do not have strings of odd length.
It is not wrong. Maybe it's too lengthy to read. Also, when a negative vote comes, lot of people just pounce on downvoting. Like when there is one piece of garbage on road, everyone starts throwing the garbage at that place, thinking thats the designated place.
This is sad, as it was the first solution that I've ever written here on Codeforces. I thought that I should explain it in complete detail.
in problem D why almost all solution use the same formulae in binary search that is mid=(l+r+1)/2 and the low=mid and high=mid-1?? My question is why not they use mid=(l+r)/2 and then low=mid+1 and high=mid-1 based on the condition.. But second give wrong answer..Why?? Pls help Thanks in advance
low = mid + 1, high = mid — 1 works
first thing you need to take while(low <= high) because you are changing low = mid + 1 and you need to check case when they equal
and second thing is answer would be low — 1, why, because you are every time taking low + 1 when it works then, low would be final answer + 1, then result is low — 1
I prefer 2nd Style :v
How to solve E1 with DP?
Can someone explain the solution for problem C in easier manner.. Thanks in advance...
the order of appearance of even\odd numbers in the sequence will never change because you cannot swap two even\odd numbers so it remains the same. so the easiest way is to make two sequence of even and odd number and every time display the smaller
Can someone please explain the binary search for D with an example, it will be really helpful. Thanks in advance!
link to Ac code
Ok. Looking through the hacks of the round, I've noticed that there are some users who are hacking submissions made by accounts that are clearly their own alt accounts.
Though this isn't a huge deal in Educational Rounds, where hacking is mostly irrelevant, but I think it amounts to cheating in regular rounds, where you get 100 points for a successful hack. Imagine creating 10 accounts, who all submit 5 hackable solutions, and then your main account hacks them all to gain points.
What do you guys think?
It isn't possible to hack just anyone's solution — they must also be in the same room as you. Getting 10 alts in the same room as you claim has extremely low probability. Anyway, would be better if you could post examples.
That is seriously a stupid way to increase the rating. I would rather spend time improving myself rather than spend time getting my alt accounts in the same room :p
[submission:63342242]why this code has been hacked? [submission:63356037] they have the same code,but the later Accepted.
please publish the editorial
Where is the solution?
editorial pls
Please publish editorial
Can anybody please explain to me why this code is giving TLE. (Question C) Link: https://codeforces.me/contest/1251/submission/63324481
Use
ans += odd[b]instead ofans = ans + odd[b]. For strings always use+=to append.Thank You. Can you please explain the reason behind this?
Suppose we have two strings,
sandtof and we want to appendtto the end of thes. If you writes = s + twhat it does is that it creates a new string (that is invisible to you which means you don't have access to it by a variable name but it exists) which holds the resulting concatenated string. To create that invisible string it will copysandtwhich basically means it iterates over both of them once which again means the time complexity would be $$$O(|s| + |t|)$$$. On the other hand when you use+=it does not need to iterate overs, it just allocates enough amount of memory to appendtwhich is like iterating overtonce, with time complexity of $$$O(|t|)$$$. Your TLE solution was $$$O(n^2)$$$ because of the reason that you were basically iterating overanswhile appending to it.Thank You so much.
Will there be an editorial published?
Thanks for fast editorial.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Can someone please help me finding bug in my solution for the problem E2. It's giving WA on test case 3, the test case is really large so I'm not able to find out which input is giving WA.
UPD: Debugged it now
Link to my code
Can u explain your idea? pls, thanks in advance.
We will approach the problem in a greedy fashion.
First of all sort the pair vector(input) in increasing order of the number of votes required.
Now make a multiset (it's similar to set but it can store multiple elements which are same) which is initially empty.
Traverse from the bottom, and one by one push the current element into the multiset. Note that, say if you are at an index $$$i$$$, and the candidate requires minimum votes, $$$M_i$$$ and the cost of buying it is $$$P_i$$$. And you have currently bought a total of $$$v_1$$$ voters.
To be sure that by the end of the traversal the current guy will vote us, we need to check if $$$(i — 1 + v_1) >= M_i$$$. If the condition is not satisfied, buy the vote of the guy in the starting of the set (cheapest till now), add his cost to your answer and erase this guy from the multiset.
Iterate backwards.
balanced problems, thank you.
Please link the editorial directly to the contest dashboard.
Problem D has a greedy tag on it. Can anyone please provide a greedy solution?
http://codeforces.me/contest/1251/submission/63422680 can some one tell why this code is giving me tle to problem 3 thanks in advance