Привет, Codeforces!
В 23.03.2023 17:35 (Московское время) состоится Educational Codeforces Round 145 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Привет, Codeforces!
Мы рады сообщить, что регистрация на летний лагерь Leagues of Code открыта! В этом году Harbour.Space University и Leagues of Code организуют лагерь программистов на Менорке с 1 по 15 июля!
Наш летний лагерь — это обучающая программа, которая научит участников соревновательному программированию. Мы приглашаем учащихся в возрасте от 10 до 18 лет, заинтересованных в улучшении своих навыков или стремящихся к интенсивному обучению на высоком уровне. Участники будут разделены на классы в зависимости от их уровня и предыдущего опыта. Занятия будут проходить на английском языке.
Присоединяйтесь к лагерю программистов, в котором примут участие самые яркие звезды программирования!
Вот самое главное о лагере:
- Длительность: 2 недели
- Даты: с 1 июля по 15 июля
- Место: Менорка
- Уровни:
Зеро: Наш курс "Зеро" предназначен для тех, кто не имеет опыта программирования. Благодаря интерактивным урокам и интересным мероприятиям они будут изучать основы программирования и создавать прочную основу для будущего обучения
Начинающий: Наш курс программирования для начинающих предназначен для участников, которые имеют некоторые базовые знания в области программирования, но хотят поднять свои навыки на новый уровень. Курс охватывает основы программирования при уже имеющихся знаниях, уделяя особое внимание решению задач, критическому мышлению и учебным проектам.
Средний: Станьте программистом, погрузившись в основные концепции веб-разработки и разработки игр. Нет опыта программирования? Без проблем! Мы поможем вам начать, и к концу буткемпа вы станете программистом-ниндзя с крутым проектом за плечами!
Продвинутый: Готовы испытать себя? В нашем лагере вы будете решать алгоритмы как профессионал и соревноваться как чемпион под руководством медалистов.
Готовы присоединиться к нашему летнему лагерю на Менорке? У нас есть 30% скидка для участников Codeforces, использующих код CODPARMEBO30.
UPD: Разбор опубликован
"Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."
"Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."
"Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."
"Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."
"Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."
"Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."
"Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."
"Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."
Then donate to CodeForces? I don’t get why you are complaining when you are using the website for free anyways, and the website is ran by a small group of people.
Hope contest will provide positive delta to all.
Happy Educational Round 145!!
Хочу пожелать всем удачи на предстоящем соревновании! Надеюсь, я смогу решить две задачи!
Can I cancel my registration? I dont think I can attend today for the new, rescheduled date.
If you don't submit anything your rating won't change. Also you can cancel your registration by going to ghe registrants page, and press the X sign next to your handle
Hi, what is the difference between a normal div 2 and an educational div 2?
educational ones are somewhat easier
From my experience(last 3 years). You are most probably going to see some good Maths/dp problems in edu rounds.
almost 30k registered in edu round *_*.
Hope to perform better
I want to request a feature where participants can submit their own authored and properly documented solutions. I know people do share the approach they used to solve the problem but I feel if something other than editorial is available, it can be helpful to each and every one.
thread with comments is usually not too long + people upvote some interesting solutions, so i dont quite understand why you need it
It would be nice to quickly find approaches to the particular problem you need. Ctrl + F doesn't always work since people phrase their questions in different ways.
Leetcode does this and I would say it is very good. You have access to detailed explanation of solutions in different methods and languages. Codeforces users are generally more experienced so I guess we can find solutions on our own, but sometimes I still struggle to find solution (if the editorial is hard to understand) for 2400+ problems.
I received 10 penalties because I set INF to 1e16 for problem D. Feel free to laugh :') https://imgur.com/a/F5VcnwL
when that error came up I got almost sure that the contest is cursed. I submitted at 10 seconds remaining am I the last correct submission though.
Same here Sir But for problem C.
how to solve c?
C is a constructive algo based problem. There are usually multiple ways to solve these kind of problems
i'm weak in constructive can u tell your logic?
How to solve B?
Output sqrt(n-1)
Draw a 2d grid. You can fill the grid in two ways:
Way 1:
|x|+|y| = oddWay 2:
|x|+|y| = evenThen binary search upon the answer
Can you explain in more detail. I understood that the sum is accumulated as follows (let's say when starting from 0)
n = 1 + 2*4 + 4*4 + 6*4 + 8*4 + ...How to use binary search to find on which element we will get n?n = (1+K)^2
Yes, after I wrote out all the prefix sums, I can see that it is k^2. But until that, you won't understand it. BAD PROBLEM.
I think visualizing it will be more understandable for the solution. Consider k is the answer, you can put chips on:
k = 0 : (0, 0);
k = 1 : (1, 0), (0, 1), (-1, 0), (0, -1);
k = 2 : (0, 0), (2, 0), (1, 1), (0, 2), (-1, 1), (-2, 0), (-1, -1), (0, -2), (1, -1);
If you draw these points on the 2D grid by each k, you'll find it's a square with 1 increment on the length of side and 45° rotation with growing k, and maybe you will find the farthest points are with cost k.
adityagamer why only fill odds or only fill even. Can we not have some combination of odd and even? like (2, 0) (-1, 0)??
Notice that, if you have 1 chip you can put it in (0,0) therefore answer is 0. If you have 4 chips you can put them in (1,0), (1,1), (0,1), (0,-1). If you have 9 chips you can put them (-2,0),(-1,1),(0,2),(1,1),(2,0),(1,-1),(0,-2),(-1,1) and (0,0). You have to notice that solution is ceil(sqrt(n))-1.
My approach in D was to iterate on the number of elements to remove, If we remove i elements then we'll remove those which contribute most to the number of inversions(leftmost 1s or rightmost 0s) Is there something wrong?
Edit : Just saw some solutions of other people and looks like I went completely off tracks..
i try some inversion contribution type things in d problem But i didn't get anything Any hint for d problem
I used standard dp with memoization for: position, whether there was a previous 1 in the array, and whether we swapped
After trying some cases, you will found out that swapping elements $$$\ge 2$$$ times is worse than deleting an element. Therefore, you only need to check the minimum number of elements to delete for not swapping and swapping once.
Try to think about greedy, what is the relationship in position between numbers that should be removed, and those that should be kept?
Try to solve by putting only one $$$0$$$ at the beginning and remove all other $$$0s'$$$
Try to solve by putting $$$i$$$ $$$0s'$$$ at the beginning and remove all other $$$0s'$$$ for each $$$i$$$ from 1 to number of $$$0s'$$$ in $$$s$$$
It's useless to swap $$$1$$$ if it will be swapped with more than one $$$0$$$
Can someone teach me or refer me to a resource where I can learn to make my DP not ugly? I learned DP on Leetcode and for multidimensional DP I will do something like:
int dp[MAX_N][b][c][d] = {};
memset(dp, -1, sizeof dp);
But this doesn't work on Codeforces because testcases may be <= 1e5 and initializing the DP array for this many testcases results in TLE. So on Codeforces like this contest's problem D I ended up using:
vector<vector<vector<vector<vector>>>> memo(s.length(), vector<vector<vector<vector>>>(2, vector<vector<vector>>(2, vector<vector>(2, vector(2, -1)))));
But surely there's a better way to do this, right?
instead using memset,for each testcase manually set dp state as -1 for only n(size of array) positions in dp array.
Because there are always constraints like, for all testcase sum of n will be <=3e5 or something
Thanks, this sounds much easier
In c++ 20, you can write multiple dimensional easily. For example for 3d, you can write:
vector a(n, vector(n, vector<int>(n,-1)));Thanks, this is a lot cleaner
But if we want to pass it in function then we have to write in old fashion ?
Solved the problem in 90 minutes because google calculator cannot make proper square root
So true, I solved it with sqrt but I don't have proof.
I still don't understand how root of number is connected
You can create square of x * x points with (x-1) maximum value for all the points
I don't have proof but I drawed it for different even and odd values.
include<bits/stdc++.h>
using namespace std;
define endl "\n"
define ll long long
int main() { ios::sync_with_stdio(false); cin.tie(0);
int t; cin>>t; while(t--) { string s; cin>>s; map<char,int>mp; for(auto i:s) { mp[i]++; }
if(mp.size()==1)cout<<-1<<endl; else if(mp.size()==4)cout<<4<<endl; else { if(mp.begin()->second==1||mp.begin()->second==3)cout<<6<<endl; else cout<<4<<endl; } }
}
Why this code don't work 1st problem... Can anyone help me out?
1 1022
correct output:4 Your code output: 6
in C++20 inbuilt sqrt() is giving wrong answer but in C++17 it's accepting?? sqrtl() worked for C++20
How did so many people figured out answer for B is sqrt(n-1) is this some known concept or if someone could share how they landed up on this solution.
checking the last sample test case
I just draw it on the plane, and noticed that max distance changes over powers of consecutive numbers(1^2, 2^2, 3^2 etc.)
In the beginning 5min, the server was heavier than usual, hope the situation becomes better until the coming Div1+2.
Hi, a totally unrelated question but it would be great if you could help me. Can you look at my profile and tell me whether I am doing something wrong coz I feel like I am unable to solve D questions of DIV2's. I usually practice in the range 1400-1900(sometimes 2000, but not often).
I get it I need to solve harder problems to solve 4th question but then should I stop solving < 1600 rated questions and just focus on the harder ones?
Thanks!
When practicing, you should not solve easy problems. I won't give an exact rating because it depends, but the easiest problems you should solve when practicing should probably take you at least 45 — 60 minutes to solve completely (from first reading the statement to getting AC). Obivously I'm not saying that you're not allowed to solve some easier problems every now and then if you find something you'd like to solve, but know that it is really effective if you just focus on the harder problems.
Also remember that it is (almost) equally important to be able to solve easy problems fast and with very few or no wrong answers in contests. The best way to practice this is by doing contests; the second best way is by doing virtual contests. But I'd still say that most of your practice should be doing hard problems if you want to improve quicky. It will take a lot of effort but I promise it is worth it. And don't feel demotivated if you can't find the time of motivation to solve hard problems on some day. You should practice when you feel like it and you should not force yourself to do it (unless you actually want to, but then it's your own choise).
I'll try to stick too it.. but most of my <1600 rated problems are for speed practice :/. I try to do a couple of 1700-1900 ranged questions everyday so that I actually feel myself struggling a lot and then I do a couple of managable ones to improve speed
First of all, the difficulty of D2D is not so stable. Sometimes it's 1400 and sometimes 2400. So it's better to aim to solve Xdiff than Xth question.
In my experience,
Your stable rating is about 1700, so stop practicing <1600 is bad idea because you can't find the things you don't know(or you can't do), and also can't practice speedsolving. keep going!
I see, thanks!
Seems like I am on the right path
I'm waiting for the proof of B.
I think it was more of guessing than educational :((
Here is a solution without guessing
It will create a series of 4,8,16,24,36,48,64,80,....
We can rewrite the series 4*(1,2,4,6,9,12,16,20,25,30,...) which is a quater squre.
Here are two picture
n^2 points fully fills a diamond with cost n-1. in other words, the minimum cost for n^2 is n-1, and n-1 cost hold a maximum of n^2 points. so if (n-1)^2<x<=n^2, minimum cost for x would be n-1.
kinoud how to see that n — 1 cost will only have maximum of n^2 points?
hint: if (x,y) is selected, then its up, down, left, right should be empty. if you draw lines: up--left--down--right--up, they forms a diamond with area of 2. so every selected point covers an area of 2. and no two selected point cover shared areas.
I think the round should be made unrated
yes it should be unrated because at beginning of the contest there was a lot of traffic on site due to which it took a lot of time to load the problem and also showed gateway error.
Problem B might be my least favorite problem ever, hopefully I can understand the solution when the editorial comes out, not just have people say they've guessed it :D
Use pen paper its very easy to understand.
OOOOOOOOOOMG!I finally passed a C in div2
Badly stucked in B.
Other than a terrible Div2 B, this was a great contest.
Agreed, I drew a square pattern on a piece of paper, brute forced the answer to n = 9, then decided to take a guess and output sqrt(n-1).
No, B was great. It is not the authors' problem that you can't use sqrt function properly.
B is so hard. how does it get so many ACs? What's the solution for B? I used binary search for even and odd count of points on one side and do a sum series. But it's so complex. What's the easier solution?
I used pen and paper for when ans = n — 1. I was able to draw n * n points. in each quadrants n points.
...(sorry for multiple comments caused by internet connection issue)
First time solved div2 A-F in 1.5 hours. (1801B - Buying gifts: What did you say?)
A: We can count the occurence of each color. There are only 5 ways to divide 4 bulbs into different colors: 1111, 112, 22, 13, 4. The answer for these situations are 4, 4, 4, 6 and -1.
B: The optimal way to place chips: choose an upper bound k, place chips on all points (x, y) with |x|+|y|<=k and (k-|x|-|y|)%2==0. We can find the optimal k by binary search.
C: We consider array {s[i]}=a[1]+a[2]+...+a[i], where 0<=i<=n, then {s[i]} will have exactly n*(n+1)/2-k inversions. First we let s[i]=i, the initial inversion number is 0. Then we swap some pairs of adjacent elements to increase the number of inversion. We can do this like what we do in bubblesort: first for j=0...n-1 do swap(s[j], s[j+1]), then for j=0...n-2, then for j=0...n-3, and so on. Every swapping will increase inversion number by 1. When we reach n*(n+1)/2-k we stop swapping and output {s[i+1]-s[i]} as answer.
D: It's optimal to use at most 1 swap operation (that's something like 00010111 -> 00001111). We need to choose an index i, remove all occurences of 1 on its left, and remove all occurences of 0 on its right. But if there are something like ...[1]0|11..., instead of removing [1], we can move it to right by swapping and save 1 coin. Similar for something like ...00|[1]0... , so we can solve the problem by prepare prefix-sums, suffix-sums and look for all choices of i.
E: Consider for all pairs of (c, d) with same value of t=c+d. Let v1 and be the current volume of water in the first and second tank. Then in the whole process, we have 0<=v1<=a and 0<=v2<=b. since v2=t-v1, we can write the second inequality as t-b<=v1<=t, then we have max(0, t-b) <= v1 <= min(a, t). Then for all possible values of c in this range, the lower bounds and upper bounds of v1 are the same, so we can let f(v;i,t) be the value of v1 after we do the i-th operation if v1=v before the operation and v1+v2=t, then the answer is the composition of functions f(_;1,t), f(_;2,t), ..., f(_;n,t). We can observe that every possible compositions can be determined by a tuple (f0, x1, x2), which means:
-if x<x1, f(x)=f0.
-if x1<=x<=x2, f(x)=f0+(x-x1).
-if x>x2, f(x)=f0+(x2-x1).
For each value of t we can find the answer for (c, d) with c+d=t by doing function compostions by some caseworks, and we can solve the problem in O(n*(a+b)+ab).
F: The optimal solution is: Fill fuel for the remained journey at cities with b[i]=1, and fill fuel to reach the next city at cities with b[i]=2. Thus when we leave a 1-city, we have at most k-a[i] liters of fuel for following 2-cities, which means we can save min(k-a[i], a[i+1]+...+a[j]) liters of fuel, where [i+1, j] is a maximal block of 2-cities. So the answer of all 1-cities are the same, and for some 2-cities we need to consume more fuel because we lost the opportunity for saving fuel.
Holy hell, the inversion model and solution for problem C is really cool. Now the model approach (which was written by me) looks lame.
This also allows a linear time solution for problem C(as it just boils down to building a permutation with k inversions): https://codeforces.net/contest/1809/submission/198841950
My solution can also be improved to linear, although I wrote it in recursive fashion without improving, so it works in $$$O(n^2)$$$. When designing this problem, I envisioned an approach which gradually reduced the problem to smaller values of $$$n$$$ and $$$k$$$.
Basically, I consider two cases:
If you still do not get it then just make observations by my given test cases and you'll be infering the solution itself
What is this notation, {s[i]}=a[1]+a[2]+...+a[i] or {s[i+1]-s[i]}?
First: 0, a[1], a[1]+a[2], a[1]+a[2]+a[3], …
Second: s[1]-s[0], s[2]-s[1], s[3]-s[2], … which is same as a[1], a[2], a[3], …
Is there a simple proof that at most 1 swap is optimal? I have a proof but it doesn't feel direct enough.
Can you explain your proof?
I have an idea but I'm not sure if it is correct or not.
Think about when you have 2 swaps.
Case 1: Swap same element [Example: 100]
You can just remove the 1 instead of swapping.
Case 2: Swap different elements [Example: 10 ... 10]
After swapping both pairs, the second 0 will still be after the first 1, and it would be more optimal to just directly remove the second 0.
And how did you notice that the number of inversions corresponds to the subarrays of the required sums? Thank you.
Sum of subarrays = difference of prefix-sums
This is a useful technique for many d2B-d2D problems.
why not only remove ones in d why both zeroes and ones????
For example: 1111110111111 we can remove the single occurence of 0.
there's no way to get a correct answer on B unless you binary search the square root, did none of the testers notice this?
You can solve B by this observation: one way to start placing chips is to start at [0,0] and then place chips a total distance 2 from the first one on positions [0,2], [1,1], [2,0], [1,-1] etc., forming a kind of a "star" this way, following this pattern you can place 8 + 1 starting chips, then each next amount of chips is greater than the previous one by 8 and the distance is going to increase by 2, so we end up with an arithmetic series which total sum is equal to:
1 + (k / 2) * (8 + (k-1) * 8), this should be equal or greater than the total amount n of chips that we want to place. After solving the quadratic, the minimum distance would be equal to 2 * k.
Another way to start is by placing 4 chips on positions [1, 0], [0, 1], [-1, 0], [0, -1], this way we can minimize the initial cost of placing chips to 1. Similar to the previous case, each next step we can place 8 chips more than the last step, each time increasing the total cost by 2.
In this case we end up with sum looking like this: 4 * k^2 = n, so the total amount of times k we should place portions of chips should be equal to k = sqrt(n) / 2 (careful with the rounding). The total cost in this case will be 1 + (k-1) * 2.
After we calculated the cost for each of two methods we should take the minimum one, that is our answer.
...(sorry for multiple comments caused by internet connection issue)
Anyone know B test2 5002nd input?
wrong answer 5002nd numbers differ — expected: '999999999', found: '1000000000'
sqrt issue.
its 10^18, its a problem on their side, i think, i have msys 2 gcc, i ran it on my device and got the right answer, any compiler except gnu c++17 gives wrong answer. I hope they compensate for that specific test case. EDIT: Sorry, this is a noob question, it worked using sqrtl(), though i don't understand how even sqrt gave the correct answer on c++17
maybe its not 10^18 i test it, my ansower is 999999999 not 1000000000
198838252
i get it, like 1000000000000000000L-50L
Why in problem B, data
1
1000000000000000000
The answer is 31622776 is an unsuccessful hack?
Sorry, I made a mistake myself. I outputted a 1e17
We found a guy **https://codeforces.net/profile/LUFFY_02** LUFFY_02 he has created three fake accounts __LuFFy LuFFy___ -LuFFy- he use to do correct submission from his official account and hacks his solution in fake accounts by putting a edge case on test cases for getting successful hacks. 198783958 198783958 198784476 198784572 198783173 198780641.
Well, I did that first time today, to see how much it's gonna change.... There's no +ve delta for hacks right? So this wont be a issue if I did it today just to see how much it affects :/
Yes, there's no positive delta for hacks, but in according to the contest rules you're not allowed to use more than one account. Although this didn't really cause any harm, you shouldn't do it again.
If you did this in div2. You would have probably gained a huge amount of points. That's equal like solving another problem.
I saw that too, this [user:https://codeforces.net/profile/SCOR_PION] and [user:https://codeforces.net/profile/__LuFFy] accounts are fake and are getting used for hacked submissions
He is genuine guy just the curious one. I was suspecting him too. Then i saw his graph looks decent hardworking guy to me.
Unethical hacking attempts are going on in this contest. I'm unsure if the hacks contribute to the rating for this event, but similar hacks can be performed in other contests. I have explained how this is being done there. https://codeforces.net/blog/entry/114270
Please check out and make sure this won't happen further
Awesome Problem F!
Main idea is binary lifting, but in a very clever way. We can decompose any optimal path in the form of "greedy steps" (except possibly the last step):
That any optimal path can be decomposed into these greedy steps, except possibly the last step, can be easily seen by an exchange argument. So from a fixed node, in an optimal path, we go to a fixed next node. We have stored the next node we go to, and the price of going to the next node.
Now that we have the transitions, we know which path to follow to get one optimal solution. So the solution for each node is just to follow this path. To speed it up, we can use Binary Lifting.
198831015
Spent 1.5 hr making useless drawings for B.
Cyan color will suit me.
same experience. B ruined my contest :)
same lol. if i had skipped B I would have solved C and D... welcome to the club bro
Us moment
Am i the only one who solved D by DP , maybe i overcomplicated it :(
I don't think anyone solved D with an uglier DP solution than mine. 198822901
Can you explain your dp state ? @AdityaG
I did too, 198854887
Can you please tell what does the line
array<int, 2> ans = min({dp[n][0], dp[n][1], dp[n][2]});do?Does it assign the minimum $$$2$$$ values out of those $$$3$$$ to the array?
Hi! dp[n][0], dp[n][1] and dp[n][2] are all instances of array<int, 2>, so it compares all of them and returns the minimum of them. Think of it as sorting those 3 elements (except with direct comparisons instead of sorting) and returning the first of them.
So what is the difference between
int ans = min({dp[n][0], dp[n][1], dp[n][2]});andarray<int, 2> ans = min({dp[n][0], dp[n][1], dp[n][2]});?The difference is that the first line won't work at all, since all of the elements you are comparing are array<int, 2>, so it will return an array<int, 2>. I'm storing it in such a way because it allows us to maintain both the total number of operations and the number of deletion operations, which I guess isn't needed. You can reimplement it with long longs instead of array<int, 2> used everywhere.
OK Yes, understood.
My bad, didn't even look at the global declaration.
Thank you!
Could someone help me out with how to combine observations in problems like D, I was able to find out that if I perform a swap operation, both the numbers should reach their correct positions , like on 0010111 -> 0001111 , but I wasn't able to do anything after that. I don't understand why I can't come up with a solution even after getting good observations. Please help
I will omit the part about importance of proving observations. Considering the fact that you and I are green as hell, I think having at least "proofy" gut feeling of correctness, or being unable to construct counterexample should be enough to solve ( guess).
Your so called observation: if I perform a swap operation, both the numbers should reach their correct positions. What do you exactly mean by that? One way to interpret: perform swap only if it yields to correct position. But then it means that all of the performed operations are deleting, excluding only maybe the last operation. I won't continue because your observation is wrong anyway. What I intended to show by writing all of this is that, as you could not evolve your idea even if it is wrong shows me that you can't interpret your intuition in terms of strict statements and/or you don't really understand what observation means, have little to no experience of proving statements. I think you should try proving all of your observations or construct counterexamples during practice. At first it is hard, but as you gain experience in proving things, and gain experience, it will really become a second nature. Good observation for this problem will be (don't read if you want to try again):
After sorting, array looks like that 0000000111111. Array "breaks" into 2 parts — zeroes and ones. Consider that line dividing zeroes from ones — let's call it breaking point. Next observation: it is quite easy to tell whether it is optimal to swap to "good" position or delete element if you know the breaking point in the answer. Idea of solution: we could brute force all of the possible breaking points, and calculate cost of sorting for each of them. After that choose the smallest value among them.
Ohhk I get it , btw thanks for help .
Good luck bro
Yes u were right there that I was thinking all operations before this were deletion, and anyhow by some kind of deletions I was thinking to make the string look like 00010111 so that my last step performs a swap .
Using sqrt function doesn't work if you use C++ 20 but works if used in C++ 17. Could someone explain what's wrong here?
About problem F:
Don't get me wrong, I'm not trying to say that this problem should not appear in the contest, it's ok and seems like a lot of people liked it, but there is much harder version of this problem from joi 20-21. It's a really cool problem, for those who solved problem F, I recommend to solve it as well, here is the link and you can submit here.
is there any english editorial of it?I'm not sure, I didn't find it. But here is a short solution. I hope it will help in case you don't know what to do.
First of all you write a stupid $$$O(nq)$$$ solution. To do this, you need to find for each position the closest cheaper position to the right of it (let's call it $$$next$$$), and then from $$$i$$$ you either go to $$$i + 1$$$ and buy as much energy as you can, or you go to $$$\min(R, next_{i})$$$ and buy energy only to get to it. Here $$$R$$$ is where we want to get.
Now for each query $$$[L, R]$$$ you want to find last position where you bought energy (let's call it $$$pos$$$). To find this position, you can find the suffix of $$$[L, R]$$$ where you can buy energy to get to $$$R$$$ and among them you need to find the cheapest. From the algorithm above you can see that you had none energy in that position. So you can split your query on segment on two suffix queries ($$$[L, n - 1]$$$ and $$$[pos, n - 1]$$$) and take there difference (also you need to add the price you paid to get from $$$pos$$$ to $$$R$$$).
Now the hardest part of the problem. You want to iterate from $$$n - 1$$$ to $$$0$$$ and maintain the answer for each possible capacity to get from the current position to $$$n - 1$$$. To do this, you will need to maintain the stack that you used to find the closest cheaper to the right. And if you, for example, keep the answers in some segment tree you will need to recalculate them only while popping from the stack.
Now look to the brute force solution that was described above. You want to do some changes in your data structure to get the correct answers for $$$i$$$ knowing the answers for $$$i + 1$$$. Using this stack you will know what is the difference in strategy for $$$i$$$ and $$$i + 1$$$ and it will be not too hard to handle them.
in Educational Codeforces Round 145 (Rated for Div. 2) in problem 1809B - Points on Plane during the contest i have submit code with C++20 and had Wrong answer on test 2 and after the contest i submit it again with C++17 and had been Accepted 198780726 Wrong answer on test 2 198858827 Accepted anyone to say why?
It depends on bits that a version uses. Try not to use sqrt: https://codeforces.net/blog/entry/107717
I solved B using binary search...didn't think of any other methods during the contest. Learned a lot! Epic round huge thanks to the authors!
In Question C, It's giving wrong output on test case 7,i.e, n = 17, k = 48 my output is 2 4 6 8 10 12 14 16 18 -79 -500 -498 -496 -494 -492 -490 -488 this output is having exactly 48 positive subarrays. but codeforces is showing wrong answer. It is request to codeforces to see this issue asap as my rating will affect vastly in this case. here is my submission link : https://codeforces.net/contest/1809/submission/198828726
I just view your submission and it show that you wrong in this case (codeforces also comment why you fail): n=30, k=319
Damn I suck at Geometry, my brain froze at B :(
Why is this guy Mido. submitting all these different solutions ( 198880211, 198880252, 198880324, etc) for Problem A while giving different edge cases that would fail to let AhmedSayed. hack all of them? This is weird...
Great contest! I have a editorial video (dicord discussion) on this contest, where problem A, Problem B, Problem C and Problem D have been discussed. you can view it here- video editorial!
Thanks!
Educational contest（×） Reverse pair contest（√） problem C and E are good as problem conversion exercises
Failed to notice in D operation 2 is always better than swapping as long as the swapping letter is not consecutive
Though it makes me wonder: what if the costs of two operation is given in the form of a, b? I think I got a solution but not sure about it.
Where's editorial
Question c Why did my code make an error at the test point of 17 48： https://codeforces.net/contest/1809/submission/198828047 but When I modified the output rule, it passed： https://codeforces.net/contest/1809/submission/198884256
When all the subarrays need to be positive you are still printing a negative value at the end in the first version.
testcase (you print 3 values for this, n = 2):
Update in Ratings?
Why AC code getting WA ??
AC: https://codeforces.net/contest/1809/submission/198912757
WA: https://codeforces.net/contest/1809/submission/198912608
I got into similar issue during contest. I have used Math.sqrt()[java], but not sure why it was failing in 2nd testcase.
I used
Because you can get sqrt(25)=4.9999..
The only difference is the language chosen. Check the differences in both versions.
sqrt is floating point (using the double type), and the c++ specification doesn't require double to be accurate enough to solve the problem.
The implementation is allowed to use higher precision for calculations if available and 32bit x86 tends to use 80bit floating point for intermediate results, 64bit will usually keep everything at 64bit. If you want to know exactly why then https://randomascii.wordpress.com/2012/03/21/intermediate-floating-point-precision/ is a good read.
B is a Good problem
Is this contest unrated ?
same code :
WA : c++ 20 : 198836355 AC : c++ 17 : 198857463
got same. Use sqrtl instead of sqrt
cout<<(long long) sqrtl(n-1)<<endl; this will get AC in both.I doubt C++17 is more precise for sqrt.
==
No.It returns long doulbe
Upload the editorial please. Can someone explain how to solve E. I can't come up with any kind of logic
cy
Did anyone else miss the fact that $$$1\leq b_i \leq 2$$$ in problem F? :(
I know it can be solved without that restriction, but that simplifies the problem a lot.
How do you solve it if $$$b_i>2$$$?
Check this comment in the blog :)
Please release editorials soon.
I am also waiting for the editorial to be released... I think it will be released after the rating changes updated..
Was this round unrated because the blog says this was rated ??
wait bro, rating change will reflect soon
When will the ratings be updated? I am so much excited to cross 1200 for the first time.
Same. First time crossed 1900 after more than 3 years of solving. Very happy.
First time breaking 2100(+118),can't wait anymoreeeeeeeeee
Where did you know the changes? The CF Predictor seems crashed.
I use the Carrot https://pan.baidu.com/s/1UZfeXfrDviZYUb8naMmqDQ?pwd=1111 (using BaiduNetdisk)
But isn’t carrot rating prediction much higher every time compare to actual rating changes? What about you?
Ah,mine never differs more than 3 once the hack ends
Same, I have been checking every few hours. Hope they don't make it unrated, there really is no reason.
Hi guys, I hope I'm not bothering you with my question, but I've seen that I haven't been classified in this last contest, could someone tell me why...
It is not rated yet, later than usual.
So the rates still don't be updated yet?
Anybody knows why is it not rated yet?
Keep waiting ;0
Have the final tests run? I don't see any failed system test, only hacks
Can anyone please suggest a good Rating predictor extension or website..? The waiting for this rating update is too long.....
I use carrot (https://addons.mozilla.org/en-CA/firefox/addon/carrot/) for rating prediction
Chrome link: https://chrome.google.com/webstore/detail/carrot/gakohpplicjdhhfllilcjpfildodfnnn?hl=en
How accurate carrot is for rating prediction. I felt like it predicts much higher +ve delta than actual +ve delta that you will get actually.
From using it it's been pretty accurate, maybe at most about an error of +-5 points. Since it's calculating the changes based on the current results the eventual rating change can fluctuate a bit due to people being removed from the rankings for whatever reason. Also Carrot will probably have some weird predictions on the first 6 contests since it 's calculating rating change based on the visual rating rather than internal rating
For me, it's worked good.
The difference between my actual rating and predicted rating usually less than 30 (I guess). Sometimes it's my actual rating > predicted rating and sometime it's opposite.
Note: The final result after system running may change a lot because some reasons (some contests has many failed final tests)
For example:
In Codeforces Round 859 (Div. 4) it predict I will +67, but the real is +51
In Codeforces Round 857 (Div. 2) it predict I will +20, but the real is +38
thank you so much...
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Can you please check why is there a rating update delay? MikeMirzayanov
Why it take longer time for educational rounds rating update?
I need +42 to reach specialist, and the carrot extension is showing + 56. Hope, I reach in this contest only, even if I miss by few points, after this contest, I have confidence that I would definitely reach specialist in the next one!!
how accurate is the carrot predictor, I read up above that it becomes more accurate after 6 contests or so you know how accurate is it
Can someone tell me how much times does educational round takes to update the rating ig there is a delay as compared to other contests?
latest this year,just wait x_x
Xd
I am sorry guys, since i am mastering, Mike gonna make all of you wait 1 more day
Finally!
I noticed something weird regarding rating changes. Me and the person next to me both got the exact same rank (226) and our initial ratings are only 1 apart. However, our rating changes are significantly different (+137 vs +172). Heres the picture for reference https://imgur.com/a/vU5nqyT.
Does anyone know why this happened?
I suspect it's because it's only frgnhite's 6th contest, and their true rating was not shown prior to the contest. Users start from a rating of 1400, but it is shown as starting from 0 (to not discourage people), and so, are shown a reduced rating to show progress. After each of the initial few contests, this reduction is reduced, until eventually (at 6 contests maybe) it shows their true rating.
Oh I see, that makes sense
Can someone explain me this rating change ??? Like I just saw a higher rated coder who got higher rank than me got more rating changes??? Also some peoples with 0 problem solved and wrong submissions got +ve del???
For the first situation that's natural...if the rank is high enough why not...? For the second the first 6 contests of each account works in particular with a base line of 1400(that's if you just meet the level you'll precisely reach it after 6 participations,+500/350/250/150/100/50),and in the quick ranking one gains more rating points(turning negative to positive inclusively). Pretty hard to get a negative rating change in this peroid
I really liked problem E, it reminded me of IOI21 Candies.
Hi I have a problem. My submission is https://codeforces.net/contest/1809/submission/199501601 and it told me that in test 2, the 22nd test point I got wrong answer. The input is "22 232" and my output is twenty-two 2 and one -41. I think my output is correct, can anyone help me?
okay I figure it out. I am an idiot. That's why I cannot get a medal in ICPC.
include<bits/stdc++.h>
~~~~ using namespace std; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; int k; cin>>k; int i=1; vector v; while(((i*(i+1))/2)<=k){ v.push_back(2); cout<<2<<" "; i++; } int s=v.size(); i--; int x=k-((i*(i+1))/2); int val=2*(v.size()-x)+1; val=-val; cout<<val<<" "; i++; while(i<n){ cout<<-1000<<" "; i++; } cout<<endl; } } ~~~~~ ~~~~~~ //
why this solution is wrong for the question C. Sum on Subarrays