Hello Codeforces!

On Mar/23/2023 17:35 (Moscow time) Educational Codeforces Round 145 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **6 or 7 problems** and **2 hours** to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

*Hey, Codeforces!*

*We're excited to announce that registration for the Leagues of Code Summer Camp is now open! This year, Harbour.Space University and Leagues of Code are organising a programming camp in Menorca from July 1st to the 15th!*

*Our Summer Camp is a training program that will teach participants competitive programming. We are inviting students ages 10 to 18 interested in improving their skills or seeking intensive, high-level training. Participants will be divided into classes based on their level and previous experience. Classes will be held in English.*

*Join a coding camp that brings you the brightest stars in tech!*

*Here is a summary of the camp :*

*Duration: 2 weeks**Dates: July 1st to 15th**Place: Menorca**Levels:*

**Zero**:*Our "Zero" course is designed for anyone without programming experience. Through interactive lessons and engaging activities, they'll learn the fundamentals of coding and build a strong foundation for future learning***Beginner**:*Our beginner coding course is designed for participants who have some basic programming knowledge but want to take their skills to the next level. The course covers programming fundamentals and builds on prior knowledge, focusing on problem-solving, critical thinking, and project-based learning***Intermediate**:*Become a pro-grammarians by diving into the main concepts of web and game development. No coding experience? No problem! We'll help you get started, and by the end of the bootcamp, you'll be a coding ninja with a cool project under your belt!***Advanced**:*Ready to put your brain to the test? Our camp will have you solving algorithms like a pro and competing like a champion with the guidance of world medalists. By the end of camp, you'll be a coding champion with a trophy in your virtual hands!*

*Ready to join our Summer Camp in Menorca? We have a 30% discount for Codeforces participants using the code CODPARMEBO30.*

**UPD:** Editorial is out

"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.

This time there should not be any issue...

Hope contest will provide positive delta to all.

open pleaseHappy 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?

https://codeforces.com/blog/entry/21496

educational ones are somewhat easier

hahaa

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 *_*.

oh really

Hoping there will be no network issue today!

Hope to perform better

You are going Pupil Now. Congratulations and Good Luck for Future.

Thank you

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?

(Everything is 1-indexed) Case 1: k is 0 fill whole array with -1.

Case 2: k is of the form (n*(n+1))/2. Let x = (n*(n+1))/2. Fill the first n elements of the required array with 1 and the remaining ones with (-1000)

Case 3: k is not of the form (n*(n+1))/2. Find highest index i such that (i*(i+1))/2<k. Let count=k-(i*(i+1))/2. Fill first count elements of the array with 30 and remaining elements upto i with 1. Fill ith index with -31 and rest of the array with -1000

thanks got it

Did you actually get it? My solution was too complex

yeah number of subarray in n length is n*(n+1)/2 , i understand in this way

yep, you got it

How to solve B?

Output sqrt(n-1)

output sqrtl(n-1) :)

Draw a 2d grid. You can fill the grid in two ways:

Way 1:

`|x|+|y| = odd`

Way 2:

`|x|+|y| = even`

Then 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.

Thank you. It's really like a filled square. And the area of the square is a square. You could have guessed by that, too.

Way 1:

`|x|+|y| = odd`

Way 2:

`|x|+|y| = even`

Used these formulas only. Here are some math on it.

## sequence go in this way

Note : here for even distance 0 -> there is only one point.

if we loop over this for some starting numbers we will get to know that it follows the sequence of square over maxCost.

Like

`maxCost, max num of points plotted (0, 1) (1, 4) (2, 9) (3, 16) (4, 25) (5, 36) (6, 49) (7, 64) (8, 81) (9, 100) (10, 121) (11, 144) (12, 169) (13, 196) (14, 225) (15, 256)`

Based on this the answer would be

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.

Yes.

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?

Hint 1Try to solve by putting only one $$$0$$$ at the beginning and remove all other $$$0s'$$$

Hint 2Try 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$$$

Hint 3It'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

I also came across this problem few years back I figured out these two ways to get that done.

1. Declare the dp vector

`a(n , vector<int>(n , -1))`

in the main itself and pass by reference to every function using this vector.2. Declare a global dp vector<vector> a and then clear and resize the vector based on each testcase constraint

`a.clear()`

`a.resize(n , vector<int>(n , -1))`

or in one liner`a.assign(n , vector<int>(n , -1))`

Note-> don't forget to clear the vector after each TestcaseIf there is any better way let me know

Problem B and Google CalculatorSolved 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.

Guessdivide the test cases with corresponding outputs and see the magic

hint:

hintwe basically place the points in a rhombic shape

solutionn--; ans=sqrt(n);

shifting to bing after this contest

can anyone provide a python solution for the points on plane problem. I think sqrt gives an error here in python.

Use Binary search to find the square root and if its a true square then output result-1 else result.Check my solution

Thank you for this approach. However, I got a usual answer using root but it has some strange behavior. However, it is accepted entirely.

I have got this soln from the comments.

Check this

Hardforces

## 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

Tq... Given a great test case... Tq

:)

in C++20 inbuilt sqrt() is giving wrong answer but in C++17 it's accepting?? sqrtl() worked for C++20

yes and because of that i got 3 penalties

same Then i use sqrtl() instead of sqrt()

Yeah, for this reason, I got 6 penalties. Whoever uses C++17 they got correct in using sqrt(),but I using same in C++17(64) ,I got wrong.

yes and because of tha I got 6 penalties.

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

this problem taught people to guess the solution, however it's useful

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.)

You want your points to be as close to origin as possibleThrow: for n = 4 , you try (0,0) ; (1,0) , (0,1) , (1,1) now you (may) see your max equals 2 which might sway you away from trying this particular approach.But sometimes, it pays off to calculate a little deeper. Do not abandon your approach so easily

Catch: Are there 4 points (with integer coordinates) who are at max 1 distance from (0,0) == YES!! the key is abandoning the origin and choosing points diamond(/rhombus shaped). (0,1) (1,0) (-1,0) (0,-1)for n = 5 to 9 you need to fill in (x,y) , based on what we saw earlier (without a formal proof) it's paying off to use points in a diamond shape first.

for n = 10 you see you have to use one of the (+- 2, +- 1) so it was deduced without "formal proof" that the ans should be sqrt(n-1)

This was the "observation process" for me. Hope that helps. (++ we hav the same name hehe)

by taking multiple test cases and plotting it. you will easily conclude that for n=2,3,4 you got 1, for n=5,6,7,8,9 you got 2 which is sqrt(n-1)....

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

easiestproblems 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

got 3 penalties in que 2 because of using sqrt() instead of sqrtl() fml

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

Why???

Spoilernice contest

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.

It should be unrated, same happened with me.

How to solve Problem C. Sum on Subarrays

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?

during contest i'was getting demotivated, But after looking some overview of pros like you now i'm happy

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.

thankyou so much for this

thanks

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.com/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

Thank you!

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.

Where to learn this technique ? any resources As iam a beginner , Mention any resources or articles to this concept or resources for other concepts That helped you

Thanks!

USACO Guide is a wonderful resource and roadmap for competitive programming. You can learn lots of algorithms and techniques there.

Thank you !

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

Try c++14

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.com/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.

Ohh sure, wont happen again, I was just curious about it so did it. :) Btw I am consistent and my records says more than enough :)

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.com/profile/SCOR_PION] and [user:https://codeforces.com/profile/__LuFFy] accounts are fake and are getting used for hacked submissions

Btw, __LuFFy was hacked first time today :)

He is genuine guy just the curious one. I was suspecting him too. Then i saw his graph looks decent hardworking guy to me.

Thnx and yes, I wont be trying this anymore :(

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.com/blog/entry/114270

Please check out and make sure this won't happen further

I encountered a wierd situation. The following code gives WA on test 2:

import math

for _ in range(int(input())):

But when I replace "if m*m == n:" with "if m*m >= n:", then the code gets Accepted. But since m = math.floor(math.sqrt(n)), m*m can never be strictly larger than n, so m*m >= n implies that m*m == n.

What am I missing? Thanks for help :)

Awesome Problem F!

Solution SketchMain 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):

greedy stepis to go to the next immediate node with just enough fuel, $$$a[j]$$$, to cross with price $$$2a[j]$$$. When you reach it, you have $$$0$$$ fuel remaining again.greedy stepis to go to the next node with just enough fuel, $$$a[j]$$$, to cross with price $$$a[j]$$$. When you reach it, you have $$$0$$$ fuel remaining again.greedy stepwould be to go the first $$$1$$$ that comes after the stream of $$$2$$$'s, with just enough fuel. When you reach it, you have $$$0$$$ fuel remaining again.greedy stepis to go as far as possible, andone more stepto the right. This ensures that the fuel is $$$0$$$ when we reach the node.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]});`

and`array<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):

SpoilerAfter 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 .

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.

SolutionFirst 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.com/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.com/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

failto let AhmedSayed. hack all of them? This is weird...Oh wow

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.

If you still do not get it then just make observations by my given test cases and you'll be infering the solution itself

Where's editorial

Question c Why did my code make an error at the test point of 17 48： https://codeforces.com/contest/1809/submission/198828047 but When I modified the output rule, it passed： https://codeforces.com/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):

ohhh，thank you; my attention is on the seventh test point (:

Update in Ratings?

Why AC code getting WA ??

AC: https://codeforces.com/contest/1809/submission/198912757

WA: https://codeforces.com/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..

Nice.. i missed this

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 ?

Dont think so, hello Green for me.

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

updated....for once i thought it was unrated now I am glad

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.

Congratulations, buddy!

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.

OK thanks

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?

SpoilerI 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

Where is My Points :(

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

Thanks to Edu Round, I am Finally green now and I want to be consistent now for some time So please give some suggestions,folks Thanks!

I really liked problem E, it reminded me of IOI21 Candies.

Hi I have a problem. My submission is https://codeforces.com/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.

can someone tell why i am getting memory limit exceeded? https://codeforces.com/contest/1809/submission/199859980