Привет, Codeforces!
В 15.02.2021 17:35 (Московское время) состоится Educational Codeforces Round 104 (рейтинговый для Див. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Отличные новости, Codeforces!
Как мы и обещали в прошлый раз, мы вернулись с новой возможностью получить стипендию!
Мы стали партнерами Coherra, чтобы открыть двери для увлекательной карьеры в сфере технологий для самых талантливых людей.
В сотрудничестве с Coherra мы предлагаем полную стипендию для обучения в магистратуре "Front End Development" в Harbour.Space, во время которого вы будете проходить стажировку на позиции front end-разработчика в Coherra!
О стипендии:
➡ Работа в самых интересных технологических городах Европы
➡ Размер стипендии до 22900 евро для обучения в Harbour.Space University
➡ Компенсация за стажировку в Coherra
➡ Возможность работать в Coherra полный рабочий день после окончания учебы
Ранее мы сотрудничали с другими компаниями, такими как OneRagtime, Hansgrohe и Remy Robotics, чтобы расширить возможности молодых талантов по всему миру и помочь им построить карьеру в сфере технологий. Мы уже заполнили несколько вакансий с нашими партнерами, в том числе:
- Место full stack разработчика в OneRagtime занял Alejandro Martinez из Мексики
- Место innovation designer в Hansgrohe занял Giorgi Zhuzhiashvili из Грузии
Мы всегда рады видеть членов сообщества Codeforces, которые присоединяются к семье Harbour.Space. Подайте заявку сейчас, чтобы получить шанс учиться у лучших в этой области и начать свою карьеру!
Следите за новостями в LinkedIn, чтобы не упустить новые возможности. А так же загляните в наш Instagram, где мы делимся событиями студенческой жизни и историями успеха наших учеников.
Удачи в вашем раунде и до встречи в следующий раз!
Harbour.Space University
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | Muffinhead | 7 | 211 |
| 2 | noimi | 7 | 271 |
| 3 | LayCurse | 7 | 279 |
| 4 | satashun | 7 | 333 |
| 5 | nhho | 7 | 366 |
Было сделано 90 успешных и 1286 неудачных взломов.
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | BOOBA | 0:01 |
| B | noimi | 0:04 |
| C | MurasakiShion | 0:07 |
| D | peti1234 | 0:06 |
| E | Bhaiya_ko_nahi_batana | 0:12 |
| F | uwi | 0:51 |
| G | renascencepjw0510 | 0:27 |
UPD: Разбор опубликован
I wish this contest took place today. For single guys like me this could have been the perfect valentine :'(
But you are not thinking about singles who would have received negative delta.
But he did not say that positive delta is a necessary condition for a contest to be the perfect valentine.
For most of us it is, I would not call a large negative delta contest to be perfect for me and you would agree there would be participant falling into this category.
What is the reason behind Educational round not having any testers?
hackers are testers :D
I hope that the conditions will also be short and clear as in the last round :)
statements :)
sorry for bad english
I will do a stream after the contest, on https://twitch.tv/AnandOza
Can you please shift to YouTube, you'll certainly get a larger watch base over there. Who watches coding videos on twitch anyways?
Twitch is objectively better than YouTube for streaming
Maybe, but I don't understand very well why people are so obsessed with streaming. I mean, It would be much better to make and edit video editorials and then submit them. Viewers could ask questions in the comment section or the author could make a live broadcast for Q&A.
It is more interesting for the content creator to stream and chat live with the subscribers than to record alone and then answer questions in the comments. Moreover, the content quality actually goes up if you are streaming, because all the frequent questions are answered directly in the video and not somewhere in the comments where you have to find them first.
I upload my broadcasts to YouTube later, and post screencasts on YouTube as well. Feel free to subscribe at https://www.youtube.com/c/AnandOza.
Can we expect short statements? It would be very pleasant to see short statements on the problems :)
Can we expect strong pretests? It wouldn't be very pleasant to see FSTforces. :) (FSTforces makes +136 for me) forgive my poor English:)
Just 1 day earlier and this contest might be my savior in the day that wasn't born for a single like me
A Valentine's Day date with codeforces. :)
Yesterday was 3 years since my first contest, that was a Valentine contest. As luck would have it, problem A was the most difficult in the history of the Div2 rounds, its difficulty was 1400 !!!
Meme of that round:
1379A - Acacius and String is rated $$$1500$$$.
I don't check all rounds. But still it was one of must difficult A in div 2
Ok,But this Div2_A is 2000 rated
Less than 10% of success
All I wanted from Mike:
You want negative delta?
Reverse psychology, you know, all the time I was hoping for a good positive delta to become master (while also practicing), but you know what? Screw it! Let's have $$$fun$$$!
So... I decided to take $$$a few$$$ days off! And now I just want chill around and do stuff I like.
Same feelings, bro.
...
Is it not true that the round is Rated?
Is it (not true) that the round is Rated? => Is it false that the round is Rated? => is this contest unrated? This is what we expect from div2. A problem.
H
Hello guys finally i am back after a pause of 20 days because of my faulty laptop but hey... i have practicing on paper a lot ....so i hope today i become specialist . As always good luck to all. Keep Coding!!
welcome and good luck
huh
You say that you don't, and yet you care enough to comment!
Can somebody recommend me some basic problemset on DP and Graphs. I am able to solve standard problems but I struggle a lot on codeforces. Please recommend some good resources for the same too.
for DP check this out
you can solve problems at https://cses.fi/
Valentine’s Day is the programmer’s holiday.
Really Excited for this contest, in last 2 contests I dropped down my from my Specialist spot. Hope I will regain it in this Contest. Good luck to everyone <3
those cyans who will be blue today will regret tomorrows div3
Is this TypeRacerForces?
I didn't like a single one of the problems, and probably no one did. Is there a joke I didn't get? Why did you do this?
I think starting from E they look nice to me
What? Did you even read E? It was easy, horrible and uninteresting.
I think I am not able to solve it
Face reality: "Educational" means "to boring to be used in standard contest".
nah bro educational means educational, "too boring" ain't educational.
I think I burned my every brain cell solving C. Atleast I succeeded.
How come (sqrt(2 * n + 1) — 1) / 2 isn't the solution in D?
2*n-1 not 2*n+1 :)
I know it's a dumb question, but I'm still not getting how.
We have:
a^2 — b = sqrt(a^2 + b^2)
a^4 — 2a^2b + b^2 = a^2 + b^2
a^4 = a^2 + 2ba^2
a^4 = a^2(1 + 2b)
=> a^2 = 1 + 2b
b <= n => 2 * b <= 2 * n + 1
I'm sorry again if I made some mistake, but please correct me in the place I am wrong.
c=b+1 so actually b<=n-1.
Oh, I solved the system of equations wrongly, shame on me. Thanks for explanation.
Hear me out!
$$$(d(m^2+n^2))^2=(d(m^2-n^2))^2+(d*2mn)^2$$$
then either:
$$$m^2+n^2=d*(2mn)^2-(m^2-n^2)$$$
or
$$$m^2+n^2=d*(m^2-n^2)^2-2mn$$$
first one gives
$$$2m^2=d*4m^2n^2$$$
so
$$$1=2dn^2$$$
which is impossible
the second one gives
$$$(m+n)^2=d(m-n)^2(m+n)^2$$$
which gives $$$d=1$$$ and $$$m-n=1 \lt = \gt m=n+1$$$ so basically solutions are of form
$$$(2a^2+2a+1, 2a+1, 2a^2+2a)$$$
it is (sqrt(2*n-1)+1)/2-1
I can't be the only one who found D easier than B?
And easier than C as well ...
I had a very easy solution to C
I just searched it on Wolfram Alpha
link please
Yeah for me D was easier than B and far easier than C. How did you guys solved C?
Parity of sum
i+j. If the number of teams is even, game of teams $$$2k$$$ and $$$2k+1$$$ $$$(k=0...\frac{n}{2})$$$ is a tieMy solution is very different and I am yet to prove why it is correct Basically we can find a formula $$$n(3n - 3 - 2s) = \sum{t_i}$$$ where $$$s$$$ is score of each team and $$$t_i$$$ is number of ties played by team $$$i$$$. Here comes my unproved assumption that each team will play same number of ties. Now to minimise total ties maximize score and then I just greedly assigned wins, loses and ties and I don't know why this is correct
By giving explicit constructions, we can show that it is possible to have $$$0$$$ ties if $$$n$$$ is odd, and $$$n/2$$$ ties if $$$n$$$ is even. So, to prove correctness, we only need to show that when $$$n$$$ is even, then $$$n/2$$$ ties is the best number of ties possible.
Claim: If $$$n$$$ is even, then the minimum number of ties must be at least $$$n/2$$$.
Proof: If there are exactly $$$T$$$ ties among all $$$\binom{n}{2}$$$ matches, then the total score of all teams must be $$$3\left(\binom{n}{2} - T\right) + 2T = \frac{3n(n-1)}{2} - T$$$. Since each of the $$$n$$$ teams gets the same score, this number must be divisble by $$$n$$$.
We now use the assumption that $$$n$$$ is even. We can assume that $$$n = 2k$$$ for some positive integer $$$k$$$, and hence, $$$\frac{3n(n-1)}{2} - T = \frac{6k(2k-1)}{2} - T = 6k^2 - 3k - T$$$. This must be divisible by $$$n = 2k$$$. It is easy to see that this is true when $$$T = k = n/2$$$, and there is no smaller possible value for $$$T$$$. $$$\square$$$
I believe that this solution gives another nice proof of why the number of ties is optimal (since it argues in terms of in-degrees and out-degrees of a vertex which need to be equal).
From this, we can also show that for any optimal configuration with even $$$n$$$, each team must have exactly one tie.
Indeed, from the proof above, we know that the total score of all $$$n$$$ teams is $$$6k^2 - 3k - k = 6k^2 - 4k$$$, so the total score obtained by each team is $$$\frac{6k^2 - 4k}{2k} = 3k - 2$$$, which is not a multiple of $$$3$$$. On the other hand, if a team has no ties, then their total score is a multiple of $$$3$$$. So, it is impossible to have a team with no ties. Each team must have at least $$$1$$$ tie.
Together with the fact that there are $$$n/2$$$ ties in total, it is easy to see that each team must have exactly $$$1$$$ tie.
Greedy)))
I misread the statement of problem B :( And stuck on it for an hour...
can anyone explain how to approach question d..like i am failing in the tc.
From the two formulas it follows that $$$c=b+1.$$$ Moreover, difference between $$$c$$$ and $$$c-1$$$ must be a square
1)
a^2 + b^2 = c^22)
c = a^2 - bFrom equation 2, find the value of a^2, which is c + b and then substitute it in equation 1. From there, you will a relation of the form c * (c-1) = b * (b+1). On careful observation, you will see that this can be true only when
b = c-1. So, the problem reduces to counting the number of pythogorean triplets having the length of the hypotenuse and the longest leg differing by 1.As it turns out, such a triplet has the form (2n + 1, 2n^2 + 2n, 2n^2 + 2n +1). Here is the hypotenuse is of the form 2n^2 + 2n + 1 and hence you can easily loop until you reach the limit.
Link to my submission: https://mirror.codeforces.com/contest/1487/submission/107441210
Pythagorus theorem -> a*a+b*b=c*c , a<=b<=c
and eqn in question -> c=a*a-b
solving both equation we will get c = b+1
so let b = m then c = m+1 and a = sqrt(2*m+1)
since c<=n
so m+1<=n => m<=n-1 => 2*m<=2*n-2 => 2*m+1<=2*n-1
sqrt(2*m+1) <= sqrt(2*n-1)
so our ans is number of odds(since 2*m+1 is of odd form) less than or equal to sqrt(2*n-1)
but we have to subract one from our ans since sqrt(2*m+1) cannot be 1(if it is 1 then m = 0, which is not possible).
Hope it helps.
c=a2-b
a2=c+b
3*3=9=4+5
5*5=25=11+12
7*7=49=24+25
9*9=81=41+40
Anyone have a clue what test 18 of E is?
I think that there is a bug with the penalty for wrong submissions for this round. I made one wrong submission for problem B(and got no time penalty) and three wrong submissions for problem C (and got only two time penalty).
Wrong answer on test 1 doesn't give penalty
Oh ok I didn't know that thanks!
Is E just doing DP courses by courses and for storing DP values of previous course in segment tree to get DP values in current course i.e. for DP[i] in current course we will get $$$m$$$ segments in previous course to consider value?
You don't need a segment tree, just a set that contains the previous dp values. For each dish, remove the dp value of dishes that don't go well with it and insert them back afterwards.
We can see that m_i is less than 2000000, so we just sort the DP value of the last course. Then we just select the minimum DP value (and skip the DP value if they can't get well with each other) for each current course and generate a new DP value.
We can solve E with brute force. For each vertice i from 2 to 0 brute the minimum valid vertice (i + 1). And it work O((n + m) * log2(m))
D was searchable
https://www.wolframalpha.com/input/?i=%28a%5E2-b%29%5E2%3D%28a%5E2%2Bb%5E2%29
Does this really constitute searchable? Its literally just substituting and expanding the equation.
Wrong answer on test 40 on E :( This is annoying
The risk I took while submitting C was calculated but I forgot that I'm bad at math (-_-)
[pE] What's the point of having 4 things.
Exactly :(
I really like to have a good dinner with many dishes.
Well, the main reason is that, on 3 dishes, you can iterate on the second one and take the cheapest first and third option that goes well with it.
Maybe the gap between E and the last two problems are a little bit too large(which according to the statistics are solved by 973,14 and 42 participants respectively)
anyway,good problems and strong pretests!
How do you know that pretests are strong?
For example, the pretests of prblem C is absolutely strong. I bet.
How you solve E if you can tell the idea
ParityForces
Yet another round like [some]forces
This contest was not at all educational.
It teaches you "educational rounds are not educational" XD
Educational contests teach you to hack other's codes. This is useful for debugging own code
The formula of D is $$$ b(b+1)=c(c-1) $$$ i.e. $$$ b=c-1. $$$ Difference of squares $$$ n^2-(n-1)^2 = 2n-1. $$$ For all $$$i=3...10^5$$$ write down all $$$n$$$ such that $$$ n^2-(n-1)^2 = i^2 $$$ (or $$$i^2 = 2n-1$$$ or $$$n=\frac{i^2+1}{2} $$$) and use binary search to count the answer
Any ideas why this gives wrong answer in test 24 for E:107463591
Can someone explain the approach for problem E? I think we have to start finding the minimum value from each of the n3 values to n4. Now we will move to n2 and then find the minimum from n2 to n3 for each n2 and so on.... Am I correct? If the logic is same then how all of you optimized?
I wasn't able to code completely but i think following would have worked :
Consider a,b,c,d as arrays consisting of cost of first course, a second course, a drink, and a dessert.
Now in array b , for each index we can add minimum cost in array a.
Similarly for each index in c we can add minimum cost in array d .
In both above we need to consider only those pairs which are not connected . It can be done with multiset .
Now for each index in b find minimum cost in c and take the minimum.
Yeah I am saying the same thing. But isn't finding minimum will be O(n^2)? How are you optimizing it?
Suppose for each value in $$$b$$$ we need to find minimum cost in array $$$a$$$. You can create multiset consisting of pair $$${a[i],i}$$$ . Now you can create adjacency list for array $$$b$$$ such that for each $$$b[i]$$$ it contains all $$$i$$$ in $$$a$$$ which it cannot be paired with.
While traversing $$$b$$$ , at particular $$$i$$$, remove all those pairs from multiset and then take the minimum value . finally add again all those values back.
Similarly for all other parts.
Complexity would be $$$O(max(n,m)log(max(n,m)))$$$ where $$$m$$$ is all the pairs which are incompatible .
You can use multiset to get the minimum value. While looking at the i'th element delete the values of the food which doesn't go with i'th element. Now get the minimum value in multiset. At last of i'th step add those deleted values back into multiset.
Ohh great!! Deleting the elements and then adding the same elements in the multiset, I haven't thought of. Thanks !!
the contest is done. Can I legally upload my solutions to github?
will there be information for the solutions of the problems(unhappy to say I need only for B and C) ?
Thanks for the contest, even though I couldn't perform well, I got to learn a bunch of things!
Kudos to the authors
I don't know why my D solution was giving TLE using C++14 and then got AC after I submitted with C++17. Can anyone please help me out?
wait, your solution's time complexity is O(t * sqrt(n)), and in the worst case it has to do ~3*10^8 , how can it pass?
I've submitted your solution and here is the result:
GNU C++11(or C++14): >2000ms
GNU C++17: 1965ms (surprised face)
Probably some slight difference in the compilation process based on the chosen standard that leads to a small difference in runtimes, or just normal run to run variability, since you are very close to the limit.
Getting input on E was harder then solving real problem
Success in E today depended on how fast you solve A,B,C,D. It was bit lengthy implementation due to large inputs.
Solved B in 45 minutes lol
25 minutes to solve ABCD another 25 to solve E but why are F and G so difficult?! :(
Write macros/functions so that you can input common data formats without much typing.
Why always easier G than F in edu rounds?
upd: sorry, it seems just last two round has easier G, but why?
Solved A in 2 minutes and given rest 118 min to the B, finding patterns in the smaller input. But, was not able to crack it. WTH!! happened to my brain. Ahh... this feeling can't be expressed in words.
C and E where less complecated than B, but all 3 of them index fiddling.
Once you get it the solution for B is not complicated.
I know now, Many times it happened that small things don't strike during the contest. Let's hope today things will go a little smoother.
same here bro b ruined it
Approach for D :
c = a*a-b & c = a*a+b*b
c*c = (a*a-b) * (a*a-b)
a*a + b*b = a^4 + b*b-2*a*a*b
On simplifying,
a*a=2*b+1
Now you can do a binary search for this.
Which formular we need to google or recite to solve D?
I used this https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple
I also did read this page...and then?
$$$c+b=c^2-b^2\implies c-b=1\implies m^2+n^2-2mn=(m-n)^2=1\implies m=n+1$$$
I did not liked the problem, but this explanational formular looks good, thanks!
There should be some easier way to think but I've seen this formula before so I immediately think about this.
$$$c^2 = a^2+b^2$$$
$$$c=a^2-b$$$
$$$(a^2 -b)^2 = a^2+b^2$$$
$$$a^4+b^2-2a^2b = a^2+b^2$$$
$$$a^2(a^2-2b)=a^2$$$
$$$b = \frac{a^2-1}{2} \implies a \ is \ odd \implies a=2k+1\ for\ some\ k$$$
$$$b = \frac{(2k+1)^2-1}{2} = 2k^2+2k = 2k(k+1)$$$
$$$c = a^2 - b=(2k+1)^2-(2k^2+2k)=2k^2+2k+1 = 2k(k+1)+1$$$
We already have $$$ a\le b\le c$$$ (easy enough to check that this is true for every k)
Therefore, imposing $$$c \le n$$$ would suffice.
$$$2k(k+1)+1 \le n \implies k(k+1) \le \lfloor\frac{n-1}{2}\rfloor$$$
Therefore, $$$k \lt \sqrt{\lfloor\frac{n-1}{2}\rfloor}$$$
You have your answer $$$\lfloor\sqrt{\lfloor\frac{n-1}{2}\rfloor}\rfloor$$$ (or 1 less than this quantity, has to be manually checked) in $$$O(1)$$$ :)
sqrt operation is $$$\mathcal{O}(\log{}n)$$$ right?
The pythagorean formula, $$$a^2 + b^2 = c^2$$$, and the given formula in the problem, $$$c = a^2 - b$$$, are enough.
Pythagorean Theorem: $$$a^2 + b^2 = c^2$$$. Then you couple that with $$$c = a^2 - b$$$ to solve for bounds on the variables. I thought it was strange they didn't include that in the problem statement, but I guess problemsetters deemed the theorem fundamental enough, since most people learn it in primary or secondary school.
Well, I remembered pythagoras, the problem was more "to solve for bounds on the variables.".
I assume that was in secondary school, too.
It was for me ¯\_(ツ)_/¯
c^2 = a^2 + b^2
c^2 = a^4 + b^2 — 2*a^2*b
a^4 — 2*a^2*b = a^2
a^2 (a^2 — 2*b — 1) = 0
b = (a^2 — 1)/2
So the maximum value of n was 1e9 so the max value of a would-be sqrt(2*n + 1) would be the order of 1e5(let us call this N). We will maintain 2 arrays, pref[N] and num[N].
Loop a from 1 to N and calculate b and c. If b and c are integers and c <= 1e9, put num[a] = c and pref[a]=pref[a-1] + 1. Otherwise num[a] = num[a-1] and pref[a]=pref[a-1].
For each test case binary search on num and get the index ind such that num[ind] <= n and answer would be pref[ind]. I am leaving the edge cases to you.
The answer is just (int(sqrt(2*n-1))-1)/2
First: By Brute-force, get the answer for $$$n$$$ in range $$$1...30$$$, in one line separated by a comma.
Second: Copy the result, paste in OEIS and you will have this.
Finally: Get the fake Accepted! :)
You don't need a formula besides the ones provided. Just need to know how to substitute one equation into another and do some algebra.
Who else got memory limit exceeded in E?
i used dijkstra for E and got MLE as well.
Due to a typo, I somehow found that
min(v.begin(), v.end())compiles, but will probably give wrong answer. It took me so long to find the typo. Can someone explain why it compiles and the result of it?min function takes two arguments of same type and returns the minimum value of them. It uses "less than" operator to find the minimum. Here if v is a vector then "less than" operator is defined for vector iterator. So it works.
Omg this should be quite obvious! I don't know why I didn't think about this. Thank you for the explanation!
E was so painful to solve!
Same here...haha
Something is special with the number 1337. I see it everywhere :)
It's leet written in leet the langage where you change letters to other character in order search for words doesn't work
Me whole time, during the contest.
Kudos to 6th consecutive negative delta
Lol, Last 19sec saved you from much damage. Kudos for getting AC at 1:59:41.
I solved F using a simple Dijkstra. I have no proof why the number of states is small enough.
Can you hack it or prove its correctness?
The entire state space your Dijkstra routine is exploring is of size $$$O((\log n)^2)$$$. Consider the number $$$x = 9*\mathrm{curr}$$$, written with no leading zero. Then your two operations on $$$\mathrm{curr}$$$, viewed as operations on $$$x$$$, are:
Then it should be easy to see that from a given value of $$$x$$$, there are at most $$$2 \times 10$$$ values of $$$x$$$ that can be reached with the same number of digits, and at most $$$2$$$ values of $$$x$$$ with one digit less. These $$$2$$$ values will (up to inversion of digits) differ by either $$$9$$$ or $$$10$$$. Extending this idea, up to inversion of digits, the ways to remove the first $$$k$$$ leading digits of $$$x$$$ fit within a range of size $$$10k$$$. This leads to there being at most $$$20k+1$$$ of them, which leads to the $$$O((\log n)^2)$$$ bound I claimed.
EDIT: I made a dumb oversight initially, but the idea of this comment should still more or less work. I expect the constant factor is in practice better than what my revised argument suggests, by about a factor of 5.
i was counting the pythagorus tripets where c=b+1 by the loop of pythagoras generator and it is giving TLE error any easier method ??
We have 2 equations. 1) c^2 = a^2 + b^2 2) c = a^2 — b
If we substitute the value of c from 2nd eqn. to first eqn. we get,
a^4 + b^2 — 2*a^2*b = a^2 + b^2 ==> a^4 — a^2 = 2*a^2*b (By rearranging terms) ==> b = (a^2-1)/2 ==> c = (a^2+1)/2 (By substituting the value of b into eqn.2)
We can see that c>=b>=a. For c to be less than or equal to n, a<=sqrt(2*n-1). Also for b and c to be integers a should be an odd number != 1.
So the answer is number of odd numbers from 3 to sqrt(2*n-1)
Yes...use the same function to precompute the all the pairs till 10^9 and store a,b,c in different arrays let's say A,B,C..now for each n..check how many elements in C are <= n as because C will be holding the max element of each triplet of a,b,c. This is not the best method to solve this question but yes this approach works for given constraints.
Why does DFS by complement fail on E :(
submission
Why does DFS by complement fail on E :(
submission
PatternForces
Deleted
how to solve C
The main idea is we can put the teams on a circle. Then if $$$n$$$ is odd team $$$i$$$ won from teams $$$i+1,i+2,...i+\frac{n-1}{2}$$$(with cylic shift). And if $$$n$$$ is even team $$$i$$$ won from teams $$$i+1,i+2,...i+\frac{n-2}{2}$$$ and tie with team $$$i+\frac{n}{2}$$$.
code
Solution. You can fill adjacency matrix with checkerboard pattern (if $$$n$$$ is odd), mirrored by main diagonal. Then every line and every row has the same sum. In case $$$n$$$ is even -- every team must play one game in a tie. Simplest way to put 'tie values' on adjacency matrix such that any two 'tie values' are on the same row/column -- put them on second diagonal by checking the sum of indexes $$$row + col == n$$$. Bus you also need to mirror values by second diagonal (only in case of $$$n$$$ is even).
thanks for your efforts
but after giving 2.5hours+ still i am not comfortable that how this is working ..... i know this is a valid pattern but unable to answers whether i can think this on my own in or after contest..
at the end ..... waiting for editorial.......
You can solve C by induction.
For any odd N we always have a solution , each team will play with N-1 (even) teams , so we can always allot equal number ow wins and losses to each team.
For any even N , each team will play with N-1 (odd) teams. Clearly for equal points , we will have to tie atleast 1 game of each team. Hence , if there are N teams , we will have to tie atleast N/2 games.One such method could be ending the games between (1,2) , (3,4) , (5,6) , ... , (N-1 , N) in a tie.
N = 5 , W = WIN L = LOSS
why this solution is not getting TLE? Link: https://mirror.codeforces.com/contest/1487/submission/107421373
Because the number of time for loop running = 22360*10000 = 223600000 ~ 2*10^8
Please, Can someone help me understand why below output(sequence) is wrong for Que C : Minimum Ties
when input is n = 4
my output(sequence): 1 -1 0 1 -1 0
I'm getting WA on testcase 2, my submission
Thank You!
According to your output sequence, scores are not coming out to be same for all the teams (1->4,2->3,3->4,4->5). I think you are taking the score of match tied as 0.
Why this solution is not getting TLE?
Solution Link:https://mirror.codeforces.com/contest/1487/submission/107421373
Because the total number of times for loop is running = 22360*10000 ~ 2*10^8
With O2 and Intel's good branch predictor, CF's judger isn't too slow
So it isn't TLE
Actually, it still passes without pragma optimize. 2*10^8 is small enough on codeforces when having small constant(you only do a few operations in the loop).
I solved
The O(t*sqrt(n)) solution can be optimized to O(sqrt(n) + t*log(n)) if one precalculates all triples and for each test case does binary search
How do you solve E?
You can build up the answer in bottom up manner.
Step 1 : Try to find answer for all drinks , given that it can go well with a few desserts.
Step 2 : Try to find answer for all courses of Type 2 , given that it can go well with a few drinks.
Step 3 : Try to find answer for all courses of Type 1 , given that it can go well with a few courses of Type 2.
I cannot view it.
I tried giving spoilers , but I don't know what happened , nothing was displayed. Check it now.
You need to write inside spoiler tag!
I know math is very important in competitive programming. But isn't this too much?
Please, Can someone help me understand why below output(sequence) is wrong for Que C : Minimum Ties
when input is n = 4
my output(sequence): 0 1 -1 0 1 1
I'm getting WA on testcase 2:https://mirror.codeforces.com/contest/1487/submission/107460842
YOUR OUTPUT : 0 1 -1 0 1 1
That is
1 2 — TIE
1 3 — 1 WON
1 4 — 4 WON
2 3 — TIE
2 4 — 2 WON
3 4 — 3 WON
Total Points:
1 -> 3 + 1
2 -> 3 + 1 + 1
3 -> 3 + 1
4 -> 3
the game may result in a tie, then both teams get 1 point.
you made the same mistake like me.
did you consider 1(or 3) point for winning and 0 for tie?, right?
i also made the same mistake :'(
Problem D was
https://www.youtube.com/watch?v=3_HLWzG5WSs&list=PLN2B6ZNu6xmcrSTiruKn8Dag8dsTE60HT&index=15
An explanation
https://www.youtube.com/watch?v=zRmUGEONQUk&t=0s
Joke problems in an edu — round . first 4 problems are joke.
In C, I was able to find the solution pretty quickly but for 1.5hrs could not find a way to implement the ordering. Anybody faced the same issue, and then i matched i with i + n/2 (for tie ) and brute forced rest of the pairs and it passed (maybe it will fail later) ... The ordering of win and loss for any pair
I mean how to decide which pair will be loss , win or tie
Here's what I thought while solving problem C:
Consider each team as a vertex in a complete graph. Then you need to direct edges (outwards for a win, inwards for a loss) such that the in-degree and the out-degree are the same for any vertex $$$v$$$, and we need to maximize the number of directed edges. The maximum in-degree or outdegree can be at most $$$\lfloor\frac{n-1}{2}\rfloor$$$ (since there can be at most $$$n - 1$$$ edges incident on any vertex). A construction for this is pretty simple too: For any team $$$i$$$, let it win against teams $$$i+1, i+2, \ldots, i + \lfloor\frac{n-1}{2}\rfloor$$$, where indices are taken modulo $$$n$$$. The construction guarantees that you assign one pair of teams a win/loss at most once, and since there are incoming edges from $$$i-1, i-2, \ldots, i - \lfloor\frac{n-1}{2}\rfloor$$$ (indices taken mod $$$n$$$), the constraints are satisfied as well.
To implement it, you can simply create a matrix $$$a$$$ where $$$a_{ij}$$$ is $$$1$$$ if there is an edge from $$$i$$$ to $$$j$$$, $$$0$$$ if it is undirected, and $$$-1$$$ if there is an edge from $$$j$$$ to $$$i$$$, and print in the order specified in the problem statement.
nice way to think
Couldn't you have a case, in theory, where one player has 3 draws, and another one has 1 win and 2 losses, with them having the same number of points?
Let $$$T$$$ be the number of tied matches. Then in a state with everyone having the same score $$$S$$$,
Middle equality is just summing up scores for each matches (2 for each tied matches, 3 for non-tied ones)
Odd $N$ case is very obvious so I'll skip.
If $$$N$$$ is even, after dividing both sides by $$$N/2$$$, we get
This implies $T$ is divisible by $$$N/2$$$. Since the right hand side is odd, we can't have $$$T = 0$$$, so the smallest candidate of $$$T$$$ is $$$N/2$$$.
This is exactly how I also solved(1st two lines of your comment). but for distributing the win/tie match I didn't thought of anything just did a brute force my_sub. I didn't prove why this way of distribution work
What a nice proof!
As arman.t mentioned, it's not immediately clear to me why each team needs to have the same number of wins and loses in any optimal configuration. In fact, this isn't true if we modify the number of points awarded for wins/ties/loses. For example, if winners get 2 points instead of 3 points (and everything else is the same), one optimal configuration of 4 teams with 3 total ties is as follows:
Edit: On second reading, maybe I misinterpret your comment. Are you saying that a team must have the same number of wins and loses although the number of wins of distinct teams can be different?
Nice catch, I probably should have mentioned why the number of ties is minimized there. Note that if $$$x$$$ is the number of ties, the total number of points is $$$3n(n - 1)/2 - x$$$, and this needs to be divisible by $$$n$$$. If $$$n$$$ is odd, we're done by the construction since there $$$x=0$$$, and otherwise, the first expression is $$$n/2$$$ modulo $$$n$$$, so $$$x$$$ needs to be at least $$$n/2$$$, which the construction achieves. As for your observation, replacing $$$3$$$ with any odd number works, but might not work when we replace it by an even number.
Simple way of ordering for odd value do this way.
-LWLW
W-LWL
LW-LW
WLW-L
LWLW-
For even do this way.
-DLWLW
D-WLWL
WL-DLW
LWD-WL
WLWL-D
LWLWD-
alternate LWs only no complex logic as matrix is symmetric around the diagonal.
Educational round is too harsh.....I solved A and D but still getting a negative delta in pupil.....If it was a point based div2 I could surely have got some positive delta.....Though i am very upset with my low performance of not even being able to solve B and C today...
This round was pure garbage (and I am speaking regardless of my poor performance). First four problems were all of same level. E and onward are of decent quality, but most participants didn't make it 'til that point, because of B/C fails.
How they would do E if they can't do B/C? There is some examples of opposite, but there is few of them
I never stated they would solve them, it's just that the first four problems provided no value whatsoever. When I can't solve a nice D2D, I spend a few hours analyzing it, but I don't regret missing today's B at all.
E. g. I got stuck on B for an hour or so, then solved C and D in no time (messed up the +/- thing in D, but still solved 80% of the problem), does that mean that B was super hard or that I'm stupid, no? There were just too many simple tricky problems in today's round, that's all.
Totally speedforces. You should have excluded one of the problems from A-D, because 4 div. 3 problems on educational contest is very unacceptable There are pupils and even newbies getting negative delta for solving 4 problems, This does not happen even in div. 3 rounds.
That's not true no pupil or newbie is getting negative for solving all 4. (even with absurd amount of penalty).
agreed with the argument that problems were easier than your typical educational round but it's always like this.. some days the problems are balanced, some days they are tough and some days they happen to be lenient.
Can someone explain the logic of problem F? Is it digit dp? If yes then how you used it?
Here is my 1 line code of problem-D ..xD
thats dope maths
Observe the simulation
(n*n)-((n-1)*(n-1)) -----from here u alwz found......consecutive odd value--
5*5-4*4=9(3*3)
6*6-5*5=11
7*7-6*6=13
----------
----------
----------
12*12-11*11=23
13*13-12*12=25(5*5)
And then..... square odd value are the target value.
We can do it O(1) complexity :D
cin>>n;
p=sqrt(n*n-((n-1)*(n-1));
cout<<((p+1)/2)-1;
107489793
code Problem C
Can someone please explain why my code written in C11 got a TLE? T_T
I wonder if it got trapped in an infinite loop or the code is just too slow.
You can test the code yourself with Custom Invocation, right? Your code runs that test 3 in around 1500ms.
Thank you so much for the Hardwork of making this Contest.Really enjoyed and learned new things.
Is this contest unrated?
no
I might cross 1600 based on this edu, will the div3 round be rated for me if I register now as the rating didn't change yet? or rated or unrated is decided based on the rating when the contest starts?
No, I think
When does the rating come out?
Soon
When is editorial coming??
A good contest for me. Finally solving A & B both in educational round. Feeling good
In problem C. For n = 4 according to my approach the output is 1 -1 -1 1 0 0 and the compiler output is 1 0 -1 1 0 1. My output was shown wrong because the score of 1 and 2 are not same. But I didn't see anything difference between (1 -1 -1 1 0 0 and 1 0 -1 1 0 1). Can anyone explain it please?
The scores are not the same. Draw gives 1 point to both teams
Yes I got it now.
That's indeed wrong.
Score distribution for each team(according to your output):
3 - 8 - 5I got it. Thank you.
Can someone explain on how to solve problem E ?
Sorry for my poor English.I will try my best to explain my idea. First,divide the original into three parts:the first with the second,the second with the third,the third with the fourth.Then let's solve the first part:the first kind food with the second.What we want to know is for every food in the second list,which food can be selected with it and cheapest.To do that,we can form a graph and use a map to store all the price of the first kind.Then just iterate every second food,and delete the food that cannot be selected with it in map.Finally,we can easily get which one is the cheapst or clarify there is no food can be selected with it.After this,add the elements deleted before and do again for the next second food.
To calculate the real answer,we can add the selected price with the price for the second food.Then do this for the second food and the third.Finally,the price of the fourth food would be the answer.
Here is my solution link:107496598
Makes sense, but isnt the complexity quadratic ?
This confused me a long time.But the fact is O(n + m) multiply the complexity for the map's cost.You can spilt the procession into "iterate all the edges" and "iterate all the points",these are indivisual parts.So its complexity doesnt overcome the limit.Very interesting part for me.
Sorry for my poor English, but I want to give an another idea for this problem.
So if we want to know the best choice of group $$$1$$$, we must know that for each element in group $$$1$$$ we can choose which element in group $$$2$$$ to minimize the cost.For group $$$2$$$,we should know the choice in group $$$3$$$, for group $$$3$$$,we should know the choice in group $$$4$$$.
Now the problem is how to make the best choice for each group. For one element, we can think that the elements which can't go well with it make some block point in number axis. The block point spilt the whole number axis into some intervals. So we can use some data structure to query the mininum for each intervals. I used Sparse Table to solve it :https://mirror.codeforces.com/contest/1487/submission/107467664
This solution works in the time of $$$O(n \log n)$$$, if you choose the segment tree，this solution would work in the same time.
I think it might be O(n + mlogn) for each one
Sorry u r right(((
COPS IIT-BHU, has prepared a set of video editorials for the problems A to E of this contest.
Do check them out by clicking at This.
Hope you like the explanation
)
When will the ratings be updated? Its almost 5 hrs the system testing has been done.
Does Educational rounds have editorials?
Yes.
When will the editorials be published?
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).