Educational Codeforces Round 171 [Rated for Div. 2]

2 months ago, # ^ |

-10

→ Reply

g_x_j

2 months ago, # ^ |

+37

→ Reply

Equation_Tracker

2 months ago, # ^ |

-11

→ Reply

Asuna_Yuuki

2 months ago, # ^ |

-11

→ Reply

Marubozu_

2 months ago, # ^ |

-11

→ Reply

yashsinha129

2 months ago, # ^ |

→ Reply

crashsaladd

2 months ago, # ^ |

-8

Haha, I broke your silly chain.

→ Reply

prathamalu1

2 months ago, # ^ |

NO you didn't

→ Reply

deepdblm

2 months ago, # |

I got a question, the penalty of time i.e. 10 minutes is the format of div. 3 and it is in this contest which is div. 2 so will the hacks have -ve points on unsuccessful attempts?

→ Reply

BiggestOtaku

2 months ago, # ^ |

No, hacks are done after contest ends so there is no penalty

→ Reply

deepdblm

2 months ago, # ^ |

but it is written 12 hours hacking phase

→ Reply

dark111

2 months ago, # ^ |

12 hours after the contest ends

→ Reply

bihnehminduh

2 months ago, # |

glhf

→ Reply

2 months ago, # |

+19

If I get minus again in this contest,I will leave CP.

→ Reply

Vitaly503

2 months ago, # ^ |

+111

Did you know that 95% of people leave codeforces before their biggest delta ever?

→ Reply

Equation_Tracker

2 months ago, # ^ |

That's why I am still CPing after getting $$$-35$$$ and $$$-8$$$ in a row. (Got $$$+4$$$ is the last contest :))

→ Reply

2 months ago, # ^ |

I am still going to give this contest although got -102 :( in last contest

→ Reply

bjjvsrjjt

2 months ago, # ^ |

-140 and -54 in a row :(, for me

→ Reply

papa-ka-para

2 months ago, # ^ |

means, +250 is waiting for you, only if you practice hard.

→ Reply

picoton

2 months ago, # ^ |

only -43? lol

→ Reply

CaveNightingale

2 months ago, # ^ |

lol. I solved $$$1$$$ problem and got $$$-253$$$ in a contest CF1930

→ Reply

Equation_Tracker

2 months ago, # ^ |

← Rev. 2 →

Thanks. You guys motivated me.

Edit: Motivation overloaded :). Lost $$$37$$$ in the last round (Solved only one question which is worse than my first ever contest in CF)

→ Reply

stakudog

2 months ago, # ^ |

100% actually, even tourist

→ Reply

shxyan

2 months ago, # ^ |

CP is not for rating just telling you, be better you will be higher rated. Its a hard skill, keep practicing.

→ Reply

2 months ago, # ^ |

Don't leave! I'll touch your acc and help you.

→ Reply

pratyush_24

2 months ago, # ^ |

help me also!!

→ Reply

2 months ago, # ^ |

Are you planning to leave CP too? :(

→ Reply

pratyush_24

2 months ago, # ^ |

← Rev. 2 →

+10

→ Reply

2 months ago, # ^ |

Yes, I need your help! :((

→ Reply

2 months ago, # ^ |

Can confirm, wltt touching my account helped me

→ Reply

Osama_Fahim

2 months ago, # ^ |

Please guide me as well what should i do to improve i tried different approaches but It has become a cycel positive delta in few contests and then a biggest -130 or something, and this loop continues for a long time, Please guide me your what can i do looking at my current situation ?

→ Reply

pirate__hunter

2 months ago, # ^ |

-59 in the last 3 contests 😎

→ Reply

2 months ago, # ^ |

-297 in the last 4 contests xD

→ Reply

2 months ago, # ^ |

take a rest/leave when it's no longer feels good. Comeback when you feel it or just leave it be.

→ Reply

2 months ago, # ^ |

Will I leave CP cause I am sure that I will get minus... I solved 0 problem...

→ Reply

Aritro_Sarkar

2 months ago, # ^ |

Take a break

→ Reply

frissky9

2 months ago, # ^ |

Leave CF. Go to LC and atc spend 3 months solving mediums and A-D (on atc) there, and when you come to CF stop solving 800-1000, push yourself, gl

→ Reply

dynato24

2 months ago, # ^ |

meow meow meow meow (what i was made for tune)

→ Reply

2 months ago, # ^ |

i didn't solve a single question in this Edu round, I'm easily having -150 in this contest.

→ Reply

kagelov

2 months ago, # |

I haven't lately been able to see any of the other users' submissions. Everything I see is "N/A" for source code, even for problems I have solved. Any solution to this very annoying issue? Thanks!

→ Reply

wille_und_vorstellung

7 weeks ago, # ^ |

same for me, could you solve the problem??

→ Reply

kagelov

3 weeks ago, # ^ |

I couldn't still

→ Reply

brave-kid

2 months ago, # |

Today is my debut contest with Rainboy strategy , gonna start from $$$D$$$

→ Reply

2 months ago, # ^ |

get ready for -250 XD jk bro all the best hope u do best

→ Reply

kovidsaivemuri

2 months ago, # ^ |

hmm.. brave-kid ohhh ok!

→ Reply

2 months ago, # ^ |

It's extended ICPC rules, it's not beneficial to do this.

→ Reply

Aritro_Sarkar

2 months ago, # ^ |

beneficial if you can make sure that you will solve it and if it is a points giving contest.

→ Reply

brave-kid

2 months ago, # ^ |

I am not caring about rating for now, for now my goal is to get full grasp of $$$D$$$ as soon as possible so that I can become yellow fast

→ Reply

2 months ago, # ^ |

nice I am also gonna use it now in today's codechef

→ Reply

2 months ago, # ^ |

← Rev. 2 →

at least u did it, nice try xD I'm also doing it.

→ Reply

2 months ago, # |

As a contestant, I wish to test the problems live

→ Reply

2 months ago, # |

Doing contest, problem B feels weird AF so imma skip it. Please correct me if it's skill issue.

→ Reply

Chess.Master

2 months ago, # ^ |

It's too standard problem, Just Binary Search the possible values of K, Solve more problems and you will find that it's a very common standard problem.

→ Reply

nguyenquocthao00

2 months ago, # ^ |

Binary search is possible but not necessary. This can be solved in O(n)

→ Reply

Chess.Master

2 months ago, # ^ |

Yes but it a standard binary search problem, The O(n) solution will be hard to implement and we don't need this at all,

→ Reply

2 months ago, # ^ |

Á đù hội anh em KHTN.
Figured that the O(N) solution would be just "stitching" a[i-1] and a[i+1] together for every i and check, right?

→ Reply

nguyenquocthao00

2 months ago, # ^ |

KHTN

→ Reply

dynato24

2 months ago, # ^ |

elaborate please

→ Reply

GUNNER19_2.0

2 months ago, # ^ |

Can you please tell how to solve it in O(n)

→ Reply

2 months ago, # ^ |

O(N) solution for (B): 288645656 I refuse to elaborate, I hate (B).

→ Reply

Ranlen

2 months ago, # ^ |

← Rev. 3 →

I solved it with prefixes in and I think its pretty clear O(n) 288565752

→ Reply

2 months ago, # ^ |

N is only 2000 so i was tired with it and decided to go "Fk it" and yolo with O(N^2).

> inb4 "O(N) exist", I know but I'm too tired with B and I just want to get over with it.

→ Reply

2 months ago, # |

$$$A$$$ is hard ._.

→ Reply

2 months ago, # ^ |

"black circles" flashbacks... 2002C - Black Circles

→ Reply

2 months ago, # ^ |

I was able to solve black circle pretty fast that time this one was hard for div2 A

→ Reply

2 months ago, # ^ |

I learned my lesson after failing black circles.

Do guessing sometimes, trade off between a penalty vs a quick solve + spare time for other problems.

→ Reply

2 months ago, # ^ |

u know what in the black circle problem I was able to visualize how it would be moving so I was able to come up with the distance formula solution but with this one I couldn't visualize what was happening so it took me time

→ Reply

2 months ago, # ^ |

← Rev. 6 →

$$$B$$$ is also hard ._.
Sucked without seeing small $$$n$$$.

→ Reply

2 months ago, # ^ |

Not quite, B is just tricky

→ Reply

2 months ago, # ^ |

Not quite, A is just output.

→ Reply

2 months ago, # ^ |

A is guess-forces

→ Reply

2 months ago, # ^ |

no, the constraint has k<=1414, hinting a factor of root of 2 occurred someherewhich gives an hint towards the formation of square with side length = min(x,y)

→ Reply

2 months ago, # ^ |

well, at least i guessed and got it right

→ Reply

2 months ago, # ^ |

literally

→ Reply

2 months ago, # ^ |

Idk why i'm getting TLE in A. the constraints were pretty lenient for O(N * N) solution 288664487

→ Reply

2288

2 months ago, # ^ |

Actually, the constraints are on X,Y and K in each test case, not on the sum of them over all test cases. So time complexity of O(XY) (or something else that is second order) requires a worst case of 1000*1000*5000 calculations, exceeding the time limit

→ Reply

2 months ago, # ^ |

Yeah, i realised that after fucking up my contest :(

→ Reply

Violet___Evergarden

2 months ago, # |

What the hell is this Problem B?

→ Reply

kmth.7z

2 months ago, # |

+11

took 2 minutes for A and 2 hours for B

hardest B i've ever seen fr

→ Reply

the_last_smilodon

2 months ago, # ^ |

Actually I found A harder than B.

→ Reply

2 months ago, # ^ |

I feel like you either observe the solution instantly for A or you don't at all.

→ Reply

2 months ago, # ^ |

i literally kept testing everything I could think of on A and somehow it passed

→ Reply

2 months ago, # ^ |

Well, you just had to fix any two points of the two lines at the corners of the (x * y) rectangle, then vary the other two on x and y axes. I got TLE tho 288664487

→ Reply

FatihCihan

2 months ago, # ^ |

5e3 * 1e3 * 1e3 = 5e9 , obviously TLE , you should always aim for <1e9 (unless the time limit is huge).

→ Reply

2 months ago, # ^ |

Oh damn, I forgot that test cases complexity too counts.

→ Reply

2 months ago, # ^ |

you did some overthinking, if y>k and x>k you can just make an "L" on the grid, and if k>x or k>y you make an X on the grid xd

→ Reply

2 months ago, # ^ |

← Rev. 2 →

I had that idea but idk why i messed up. This costed me the whole round, because i gave up on A.

→ Reply

_Unseen_

2 months ago, # ^ |

Ahh, so it's not just me? I literally have NO idea how people managed to come up with B's solution in such less time :(

→ Reply

anishray042

2 months ago, # ^ |

I guess since n was low enough for n^2, for odd n we can just brute force as we need to insert one extra number anywhere in the given array. Obviously, only at max 2*n possible values as we want new number to be closest to each a[i].

→ Reply

_FFT_

2 months ago, # ^ |

B is a standard problem, and it took me nothing to figure out the solution.

→ Reply

-dub-otrezkov-

2 months ago, # |

how to solve E?

→ Reply

Chess.Master

2 months ago, # ^ |

How to solve D? Is it a Segment Tree?

→ Reply

2 months ago, # ^ |

It's just some prefix sum stuffs

→ Reply

-dub-otrezkov-

2 months ago, # ^ |

prefsums + binary search. you can check my sol https://codeforces.net/contest/2026/submission/288582700

→ Reply

123gjweq2

2 months ago, # ^ |

damn that's a lot of prefix sums

→ Reply

2 months ago, # ^ |

i gave up after trying too much prefix

→ Reply

2 months ago, # ^ |

I used $$$4$$$ different prefixes in total ._.

→ Reply

Alenygam

2 months ago, # ^ |

+10

Yea I just upsolved it and this problem was a pain. It took me quite a bit to implement it and iron out all the bugs...

Also not very "educational". It doesn't really teach you to think differently, just "implement harder".

→ Reply

neal27

2 months ago, # ^ |

← Rev. 2 →

(assuming 1-based indexing everywhere) consider the b array as divided into blocks as this: (n size block) (n — 1 size block) (n — 2 size block)..... now consider one block which has starting element of pair as i. what is the sum of this block? s(i, i) + s(i, i + 1) + s(i, i + 2) + ... s(i, n) where s(l, r) is sum of a from l to r. you will see that in this expression, a[i] is added n + 1 — i times. so calculate suffix array on a[i] by this rule (a[i] * (n + 1 — i))

now if i want sum of k blocks, i need sum of block 1, sum of block 2, ... sum of block k i.e. suff[1] + suff[2] + .... suff[k] so create a prefix array on the suffix array created before.

now consider this problem: we want to find sum 1 to x, in array b:

first find number of blocks that are completely covered say k — 1 (use binary search) add pref[k — 1] then we are at block k, now if this block has l as left point of the pairs. we want to find (l, l) + (l, l + 1) +.... (l, l1) (l1 depends on where x lies in this block. now for this we can add suff[l] — suff[l1 + 1] directly. but note : this followed rule (a[i] * (n + 1 — i), but now a[i] has not been added (n + 1 — i) times. you will see that now a[i] has been added (n + 1 — i) — (n — l1) times. so you need to subtract s(l, l1) * (n — l1). again have a prefix array on original a for this say this answer we calculated for sum of b from 1 to x, is given by f(x), then given query is answered by f(r) — f(l-1).

→ Reply

2 months ago, # ^ |

I saw lots of max flow solutions.

→ Reply

-dub-otrezkov-

2 months ago, # ^ |

me too, but why them work?

→ Reply

jackson.souza

2 months ago, # ^ |

The solution is a direct application of Project Selection. Here is blog about this: https://codeforces.net/blog/entry/101354

→ Reply

Rising-coder

2 months ago, # ^ |

← Rev. 2 →

+11

Why is div2E max flow :(
I hope there are simpler solutions

→ Reply

shouldorshouldnot

2 months ago, # ^ |

is flow hard?

→ Reply

qwertylkjhg

2 months ago, # ^ |

answer is n — max pair matching in the graph, where left side vertices are 1,2...n and right side 0,1,2...59 ,edges i <-> j where a[i]'s j-th bit is set.

→ Reply

2 months ago, # |

← Rev. 2 →

B?!!!! Why is n < 2000? Is it really n^2 for odd n? How to solve B?

→ Reply

MonoLith

2 months ago, # ^ |

Yepp just brute force for every index For every index I push a[I] +1 just after a[I] and then check the minimum among all maximum You can see my code

→ Reply

2 months ago, # ^ |

Thanks, can you give a case where the picking the either last or first doesn't work for odd n? I couldn't come up with such a case

→ Reply

MonoLith

2 months ago, # ^ |

← Rev. 3 →

For n= 7

1 2 3 1000 1001 1002 1003 It's optimal to add answer is 1 If I add 4 after 2nd index (0 based) And then pair (1 2) (3 4) (1000 1001) (1002 1003) But If you add in begining or end it will be 997

→ Reply

2 months ago, # ^ |

Thanks got it!

→ Reply

anishray042

2 months ago, # ^ |

← Rev. 2 →

1 2 20 25 26

→ Reply

2 months ago, # ^ |

yeah, for even N you just sort and pair up, and for odd you test all possible Ai that you could pair up with the extra cell

→ Reply

nivedkml

2 months ago, # ^ |

You can do in O(n + log2(max(ai)) using binary search. You can check this comment.

→ Reply

ab_malek

2 months ago, # ^ |

I did it with o(n^2). You can actually remove each element and cut the array at that position to make the array two even array and solve it.

I think this intuition is less complex to solve the problem. By also accepting o(n^2) authors try to make the problem simpler.

→ Reply

Alenygam

2 months ago, # ^ |

I did it in O(N). You can check out my solution: 288539510

→ Reply

7 weeks ago, # ^ |

Nice, using suffix and prefix max

→ Reply

lhlephuocdao

7 weeks ago, # ^ |

Could you explain your solution?

→ Reply

Subarna1

2 months ago, # |

What is the solution for B?

→ Reply

nivedkml

2 months ago, # ^ |

You can binary search for each k from low = 0 and high. = (arr[n-1] — arr[0])

Code

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
typedef long long ll;
typedef long double ld;

const int mod = 1e9 + 7;

bool check (ll k, vector<ll>& a) {
  int n = a.size();
  int cnt = 0;
  for(int i = 1; i < n; i++) {
    if (a[i] - a[i-1] <= k) {
      cnt++;
      i++;
    }
  }
  
  return cnt >= n/2;
}

void solve () {
  int n;
  cin>>n;
  
  vector<ll> a(n);
  for (int i = 0; i < n; i++)
    cin>>a[i];
    
  ll low = 1, high = a[n-1] - a[0];
  
  while (low < high) {
    ll mid = low + (high - low)/2;
    
    if (check(mid, a))
      high = mid;
    else
      low = mid + 1;
  }
  
  cout<<low<<"\n";
}

int main() 
{
    ios_base::sync_with_stdio(false);
	  cin.tie(NULL);
	  
	  int t;
    cin>>t;
    
    while (t--)
      solve();
}

→ Reply

sachin.13

2 months ago, # ^ |

why return cnt >= n/2;

how you got this idea?

→ Reply

nivedkml

2 months ago, # ^ |

I will try to explain it here, let me know if you get it or not.

cnt is the count of pairs, number of pairs should be n/2, as 2 elements make up a pair. Also imp thing is we only have to check diff between conseq elements as least diff of any j with current i will be when j = i + 1 as array is increasing. eg: if n = 6. there should be 3 pairs. if n = 7, there should be 3 pairs and the remaining 1 we can match by adding our available "atmost one addition case".

n is even : Lets say a = {1, 5, 8, 10, 13, 14} and k = 3 here 1 and 14 would not get a pair (as (5-1) = 4 > k & 14 doesn't have a pair to match with), whereas (5, 8) and (10, 13) can make up pair. So cnt = 2. As we can only add atmost 1 number, we can't make pair for both 1 and 14. So k = 3 is not feasible. if cnt was 3 (= n/2) then that means all the numbers have pairs. So its feasible.

n is odd : Lets say a = {1, 5, 8, 10, 13} and k = 3 here 1 would not get a pair (as 5-1 = 4 > k), whereas (5, 8) and (10, 13) can make up pair. So cnt = 2 (= n/2). As we can only add atmost 1 number, we can make a pair for 1 by adding 0. So k = 3 is feasible.

→ Reply

sachin.13

2 months ago, # ^ |

ok got ,good explanation man :)

→ Reply

2 months ago, # ^ |

observe if we have n==even , then we cant take the extra element as that can't be compensated by any other element while making pairs so just find the max difference b/w consecutive elements, if n==odd , we have the choice to leave one element and find an extra new one for it, we can do this for each element and store the max diff to the right of it and to the max diff b/w consecutive elements to the left of it and take the max of both the overall answer for this case would be minimum of all such cases

→ Reply

2 months ago, # ^ |

Solution can be seen here : https://pastebin.com/WyE4dwSL

→ Reply

Subarna1

2 months ago, # ^ |

My idea is also similarly. But I increment the iterator for even case with i++ instead of i+=2, and I spend whole 2 hours thinking some edge cases for odd case.

Now I get the mistake.

→ Reply

louisjohns32

2 months ago, # |

c's gonna make me cry when i see the case im failing on

→ Reply

Shoeib

2 months ago, # |

please don't write problems like B again

→ Reply

2 months ago, # ^ |

Actually, I think it's a very good and tricky problem. No one on my friends list got it on the first try.

→ Reply

Shoeib

2 months ago, # ^ |

after the first WA2, i waste about 50mins. at WA5 bcos i were minimizing the ans with 1e15 :(

→ Reply

m_nature

2 months ago, # ^ |

What? It's just a standard binary search problem.

→ Reply

2 months ago, # |

after the contest, i felt like it is somehow harder than the last div1+2

→ Reply

123gjweq2

2 months ago, # ^ |

→ Reply

2 months ago, # |

Many low-rated people solved D in the last 15 minutes, I don't know if it's my skill issue but I don't think it is an easy problem. So please skip those who cheated.

→ Reply

FrostBytee

2 months ago, # ^ |

Same with B ig

→ Reply

tickbird

2 months ago, # ^ |

← Rev. 2 →

no wonder, D is ChatGPT solvable. in fact, first AC was done by hardstuck gray account.

→ Reply

shviv1

2 months ago, # |

I attempted only the first two problems and found both of them weird, or maybe I am making some blunders; I don't know.

→ Reply

2 months ago, # |

couldn't solve any thing I'm mad but at least the problems are not guessing problem

→ Reply

retard.

2 months ago, # |

+33

I mean I like prefix sums, but prefix sums of prefix sums of prefix sums is too much man.

→ Reply

alpha1215

2 months ago, # |

AC D at 1:59 :)

→ Reply

chlalstjr

2 months ago, # ^ |

+25

AC D at 2:01 :(

→ Reply

christmas964

2 months ago, # |

Thank you very much for contest.

→ Reply

MonoLith

2 months ago, # |

-7

I spent close to 38 minutes for problem A and got one wrong on B just in hurry of choices Struggle is real kn geometry problems

→ Reply

2 months ago, # |

today D feels like a buffed version of 2009F - Firefly's Queries.

Which I regret haven't upsolve the problem yet...

But idk maybe I'd stuck on this anyway.

→ Reply

2 months ago, # ^ |

They are not similar at all.

→ Reply

YocyCraft

2 months ago, # |

← Rev. 3 →

+28

E: Build a bipartite graph with n vertexs on the left and 60 vertexs on the right. For each 1<=i<=n and 0<=j<60, we add an edge if a[i] has j-th bit set on. For any subset of left nodes, the score is (number of chosen left vertexs )-(number of right vertexs with edge connected to chosen left vertexs ) = (number of chosen left vertexs )+(number of right vertexs without connection to chosen left vertexs )-60, then the answer is (Size of maximum independent set)-60. By the Konig theorem: In any bipartite graph, the size of maximum matching is same as minimum vertex corver, and (size of minimum vertex corver)+(size of maximum independent set)=n+60, we can calculate answer by any maximum matching algorithm.

→ Reply

2 months ago, # ^ |

Can you explain to me what does "set bit" mean ?

→ Reply

YocyCraft

2 months ago, # ^ |

If the j-th bit of a[i] is 1. Or if ((a[i]>>j)&1)==1

→ Reply

mir

2 months ago, # ^ |

+22

Or just think of it as the classical Project selection problem.

The bits are the machines.

The numbers are the projects.

→ Reply

conoda

8 days ago, # ^ |

open the dm for a second Umi

→ Reply

Yugandhar_Master

2 months ago, # ^ |

+10

Awesome idea

→ Reply

Igor_Parfenov

2 months ago, # ^ |

+10

That is... beautiful...

→ Reply

Al_Imran16731

2 months ago, # |

If i've submitted twice of one problem which one will be counted? If first one is hacked then second one counted?

→ Reply

p1k4

2 months ago, # ^ |

the last submission that passes pretests will be counted

→ Reply

Al_Imran16731

2 months ago, # ^ |

Thnak you!! But in current standing showing first one counted!!will this updated?

→ Reply

ShardsOfNarsil

2 months ago, # |

There is nothing educational about B.

→ Reply

Shoeib

2 months ago, # |

B reminds me with this problem

→ Reply

Jerrasterix

2 months ago, # ^ |

It is quite similar to "socks 2" of ABC although a bit different

→ Reply

2 months ago, # |

im really confused why my binary search submission failed on B, and then my brute force one passed. obviously n is 2000, so i kinda knew it was brute force, but i didnt come up with any counter test case for my binary search one, can someone give a counter example?

→ Reply

2 months ago, # ^ |

← Rev. 2 →

try this

1 2 4 6 7

→ Reply

2 months ago, # ^ |

i get 1 on both of my solutions

→ Reply

darishkhan

2 months ago, # ^ |

Binary search would pass. I did it with binary search.

→ Reply

2 months ago, # |

In problem E, what does "set bit" mean ?

→ Reply

Noobish_Monk

2 months ago, # ^ |

bits that are 1 in the bitwise OR

→ Reply

2 months ago, # ^ |

Thank you, I thought that it the last bit which equal to 1, so I used Dp and got wrong ans

→ Reply

Yugandhar_Master

2 months ago, # ^ |

+19

But how you become CM without knowing what is set bit. I'm not insulting you just curious to know

→ Reply

https://codeforces.net/contest/2026/submission/288585044

2 months ago, # ^ |

This is the first time I have ever knew about " set bit " word. I call it is "bit 1" :D

→ Reply

mahendraakshansh

2 months ago, # |

can someone help why this is wrong?

Greedy solution. Logic is that I store all the i where s[i] == 1 in a greater int set. ans = (n*(n+1))/2

I iterate over them{ count = 0; I have 2 variables l and r, I iterate over l from n->0. if I find s[l] == 0, then count++; if I find s[l] == 1 then I check on count, if it is 0 then I move more left.

When my 0s are exhausted, I move to r and only check the 1s from 1->n, if there is a 1 corresponding the I make count++, if there isnt then I break,

if there is a count then I reduce the answer by the indes of the one in the starting loop}

→ Reply

chaihard

2 months ago, # ^ |

← Rev. 2 →

The algorithm I used:

Greedily scan from right to left
If s[i] = 1, pair it with rightmost '0' (pos<i)
Else pair it with the leftmost '1'

In 2,3 just store the i, in these cases only, you will be saving money.

→ Reply

mahendraakshansh

2 months ago, # ^ |

Yep I have done this only. Implementation is a bit different but yep

→ Reply

xsyncwave

2 months ago, # ^ |

If s[i] = 0, the value $$$i + 1$$$ would be added to the cost no-matter what.

Go from right to left. The idea is to greedily exhaust the rightmost $$$1's$$$ with the first encountered $$$0's$$$ from right to left. If we exhaust in pairs, we will be able to remove as many $$$1's$$$ as possible.

Use a std::deque to store the cost generated by $$$1's$$$. Larger values are stored in the front.

if s[i] == 0,
if !dq.empty() do pop.front(); if it is empty, we can pair it with the already exhausted $$$1's$$$.
do cost += i + 1

if s[i] == 1 do dq.push_back(i + 1). Finally when the dq contains $$$1's$$$, we can greedily exhaust the largest(front) and smallest(back) values.

https://codeforces.net/contest/2026/submission/288593783

→ Reply

alexshao

2 months ago, # ^ |

Consider 1100011111

→ Reply

marcobonato

2 months ago, # |

Does anyone know what's wrong with my solution for B at 288576824? It seems to me like it should work, but sadly it fails on test 2.

→ Reply

2 months ago, # ^ |

Check my braindead solution (that divide to 2 cases of N like you): 288562462
(Why braindead? It just bruteforce every possible choice of "removal" in case N is odd and find the "best" choice (variable "minn")).
(Case N is even, my solution is the same as yours)

→ Reply

louisfghbvc

2 months ago, # |

PD I know prefix sum. But just too heavy implemention... run out of time. :(

→ Reply

2 months ago, # ^ |

yea, i gave up on d too

→ Reply

papa-ka-para

2 months ago, # ^ |

same.

→ Reply

Noobish_Monk

2 months ago, # |

Do I understand right that problem F is just:

Code persistent queue on 6 stacks, in stacks we store knapsacks, so when answering the query we can just take left and right knapsacks and bruteforce the sum on each edge

→ Reply

informal007

2 months ago, # |

Is large number in cpp necessary to solve problem D?

Is there a great large number template in cpp? emmmmm

→ Reply

2 months ago, # ^ |

+17

nah, it is just 10 millions prefix sums

→ Reply

Saivishwas

2 months ago, # |

how to solve C?

→ Reply

Valenz

2 months ago, # ^ |

I transverse the array from back to front and use deque to be able to pop front efficiently. The greedy part is to match higher indexed '1' with any first '0' found and pop it. Then, if there are still '1's remaining, just pick the lowest half.

→ Reply

2 months ago, # ^ |

think of a number 0 can carry the most expensive 1 (right most one)
after eliminate all the 0, the array is left with all the 1, then again, a left most 1 can carry the right most one. (*)
the answer is sum of all 0 index and all 1 index left in (*)

main take away is just greedy and 2 pointers

→ Reply

2 months ago, # ^ |

I was knowing it was greedy and came up with this idea but couldn't implement again. Fck my implementation skills fk it

→ Reply

2 months ago, # ^ |

← Rev. 2 →

Chill mate, look at me hard stuck in pupils for 4 months already and still die trying. You peaked in specialist is a good stuff, keep going.

→ Reply

2 months ago, # ^ |

ahh mate I peaked there I am trying really hard right now solving 1300-1500 range alot hoping to improve soon

→ Reply

LJY--2002

2 months ago, # |

wrong A why cant long long ? https://codeforces.net/contest/2026/submission/288534007

0 0 68724335200 68724335200 0 68724335200 68724335200 0 0 0 68724335200 68724335200 0 68724335200 68724335200 0 0 0 68724335200 68724335200 0 68724335200 68724335200 0 0 0 68724335200 68724335200 0 68724335200 68724335200 0

wrong output format Expected int32, but "68724335200" found (test case 1)

→ Reply

Igor_Parfenov

2 months ago, # ^ |

Looks like weird behavior because of reading before and after sync_with_stdio. Place it at the beginning.

→ Reply

LJY--2002

7 weeks ago, # ^ |

thanks

→ Reply

bacxiuda

2 months ago, # |

+11

Can anyone try to hack this submission? I think greedy cannot pass this problem.

→ Reply

BayernForce

2 months ago, # |

In these contests, is wrong answer on Test 1, considered as a penalty ?

→ Reply

bhargav_roy

2 months ago, # ^ |

I don't think so. Someone has commented about it here: Link

→ Reply

BayernForce

2 months ago, # ^ |

Thanks a lot!

→ Reply

papa-ka-para

2 months ago, # |

Either I am getting dumb day after day, or A,B,C are actually getting difficult contest after contest.

Yesterday was Div (1 + 2) contest.

Today it is simply Div-2 contest.

I felt like today's ABC were more difficult, than Yesterday's ABC.

→ Reply

2 months ago, # ^ |

Nope

Today I solved ABC, but yesterday C was giving me an insomnia...

→ Reply

ciprianamza

2 months ago, # ^ |

I also found yesterday's B much easier than today's A or B. Both today's and yesterday's A were a bit more complicated written than usual. Today's C was much easier (at least for me) than yesterday's C, sadly I ran out of time. :D

→ Reply

2 months ago, # |

A had a really nice hint for the idea that AB, CD are diagonals of a square with side min(x,y) i.e. K<=1414 , hinting the appearance of root of 2

→ Reply

LMeyling

2 months ago, # |

+19

Problem E seems familiar

→ Reply

2 months ago, # |

Could anyone please explain how to do B? I used binary search, but it didn't work.

→ Reply

2 months ago, # ^ |

just brute force the point which will be paired with a point outside the given set.

→ Reply

2 months ago, # ^ |

you could use binary search or brute force (idk the binary search way)

but in the bruteforce way, if n is even, you just pair up all cells, and if its odd, you test removing every cell and pairing up the others to see which way is cheaper

→ Reply

2 months ago, # ^ |

Thank you. Got AC.

But I'm still wondering why my BS solution didn't work.

Anyways, thanks.

→ Reply

2 months ago, # ^ |

np!

→ Reply

Alosqka

2 months ago, # ^ |

Cause you have added random things in your code which is greedy when you saw the sample test cases

if(n%2!=0 && !x && (((num[i]-num[i-1]+1)/2<=mid) || i==1))

i) why i==1 is getting a free choice

ii) why n%2!=0? it makes no sense. If you approach is because you are already going to use one point to get even points then you are correct but making such mess in the same line? Cause later you are doing i==1 which means you are skipping a element at position = 0. Which again makes no sense cause you can pair any of the i so why position i=0 is getting a priority?

iii) (num[i]-num[i-1]+1)/2 <= mid makes no sense because the new point you will be placing will be not at the middle it will be anywhere ITS FREE WILL. By placing it at the middle of num[i] and num[i-1] gives no contribution cause you are meant to stick the power up for the first element that violates the <=mid thing with its next right neighbor (according to greedy approach).

I hope you understand that you have just written many wrong things and messy in a single line.

Dont be sad or angry about it. Understand it calmly and keep grinding.

If you need my bs approach (a clean code) https://codeforces.net/contest/2026/submission/288520406

Thank You!

→ Reply

2 months ago, # ^ |

No I got it. I should have read the question carefully to fully understand it. Couldn’t give my best performance today.

→ Reply

Alosqka

2 months ago, # ^ |

Its okay buddy. Sometimes we perform good and sometimes we perform bad.

Cheers that you are consistent with giving contests! Keep grinding 😇

→ Reply

2 months ago, # ^ |

It's optimal to paint neighbors.

→ Reply

2 months ago, # ^ |

why this case 2 and not 1 please answer


2
1 3

we can paint cell number 2 what is wrong with that ?

→ Reply

2 months ago, # ^ |

You have to choose two cells at a time. In this test case the no. of cells is even. So you can't choose any cell outside this given set.

→ Reply

2 months ago, # |

← Rev. 2 →

Miss chance to become master AGAIN by declaring $$$a_i$$$ of Problem E as int, not long long.

Note: shifting more than bit width is an undefined behavior, so I get WA1, not WA2 or WA3, which is confusing to me.

→ Reply

dino_merlin

2 months ago, # |

+15

D is very reminiscent of Mosaic from this year's IOI.

→ Reply

dg351

2 months ago, # |

Can anyone please explain why my solution fails:

Method: For even n, directly calculate the max distance between all pairs (a[0],a[1]), (a[2], a[3]).....

For odd n, calculate min(max(((a[0],a[1]), (a[2], a[3]).....), ((a[1],a[2]),(a[3],a[4]).....))).

Submission

→ Reply

2 months ago, # ^ |

Consider 1 2 10 20 21

→ Reply

dg351

2 months ago, # ^ |

Got it, thanks a lot.

→ Reply

Aritro_Sarkar

2 months ago, # |

-41

The worst contest in codeforces history

→ Reply

towrist

2 months ago, # |

Spent a lot of time thinking about E after coming up with the obvious Maximum Matching algorithm, not able to believe its actually the intended solution.

While not having a template for it cost me today's E, I am really surprised Maximum Matching was allowed to appear in E, especially when the idea that each bit should have atleast one unique entry is quite simple.

→ Reply

PaciukZvichainyi

2 months ago, # ^ |

I agree that it is too much for E. But it seems to me that we have no right to complain, since this is Educ and in fact it is intended for this: you know an algorithm — 3 minutes will be enough for you, if you don't know — you are cooked for the next two hours.

→ Reply

pagol

2 months ago, # |

"Euclidean or Manhattan" missing from "A"s statement.

→ Reply

marcobonato

2 months ago, # ^ |

If it's not specified I think you can just assume Euclidan

→ Reply

4uck_d3v

2 months ago, # |

-11

Are there any ways to solve problem E with dp? I tried to solve it with dp but get WA.

Let dp[i][j] represent the value of mask such that the number of 1-bits in mask is minimized when constructing a subsequence of length j with i as the last element of the sequence.

I think we can combine with some greedy tactics, such as save more than one mask for each dp[i][j] at a time.

Sorry for my bad English.

→ Reply

Abito

2 months ago, # ^ |

-8

No it's not possible because even a mask where the bits might not be minimized might be better for bigger j and many other stuff

→ Reply

2 months ago, # |

-29

The worst contest in codeforces history

→ Reply

cwz2024

2 months ago, # |

-13

Using random to solve E: (This is gonna WA on test 2) (OMG, it's running on test 10!) (OMG, it's running on test 20!) (OMG! It ACCEPTED!!!) (I'm going to submit a lot of them to ensure I can pass main test) (passed 6/27) (ALL 6 AC submissions are hacked, rank 103->511 QAQ)

So is there a way to hack these submissions at a high possibility? Or it was just because I was to silly when randomizing? Can these submissions be hacked? 288611596 288611196

→ Reply

cwz2024

2 months ago, # ^ |

Okay, I've come up with a hack and hacked myself:(

Spoiler

1
7
3 3 3 125 125 125 125

→ Reply

2 months ago, # ^ |

thank you counterexample lmao, this one also breaks my code for some reason

→ Reply

2 months ago, # |

← Rev. 3 →

for problem B this case

2
1 3

why the answer is 2 and not 1

if k=1 then we paint 1 and 2 and then we can easily paint 2 and 3 ??????????? why I'm reading the statement wrong every time ????

→ Reply

marcobonato

2 months ago, # ^ |

You can only paint WHITE cells. So, after you paint 1 and 2, cell 2 will be black, so you can't use to paint 2 and 3 since you can only paint white cells.

→ Reply

PaarthJuneja

2 months ago, # ^ |

i spent a few seconds thinking the same thing during the contest lol

notice that the problem statement mentions in bold letters that you can only paint white boxes. once you've done the operation on 1 and 2, 2 becomes black so you can't operate on the second box anymore.

→ Reply

RDDCCD

2 months ago, # |

+19

Seems that problem F only have operation 3 in the sample. See here

code copied from jiangly's code and add one assertion on operation 3. Only have 96 tests during the contest while the verdict is RE on 97.

→ Reply

awoo

2 months ago, # ^ |

← Rev. 2 →

+31

My bad :( We only discovered that during the contest. Somehow all incorrect solutions we had were incorrect even on that set of data and all correct were still correct after the generators got fixed. Luckily, not a lot of people got affected by the incomplete tests.

→ Reply

jeroenodb

2 months ago, # ^ |

I now got affected due to some runtime error that only fires if there's actually operations of this type in the input.

→ Reply

2 months ago, # |

← Rev. 2 →

→ Reply

2 months ago, # |

could someone provide counter example for this submission , im getting WA on test 5, and the solution seems kinda silly but it runs in O(60*n^2) in worst case scenario, and it seems correct to me. basically what i do is for every element i, lets call it valid, if for every bit that is set in in a[i], it has atleast 1 valid neighbour. first we assume all indices are valid, and then we check if there is an element that isn't and if there is such an element we delete it, and also since it may have made some other indices valid, but now doesnt anymore, we have to repeat this until no changes occur. this runs in O(60*n^2) in the worst case where we delete 1 element per iteration, and every element will be deleted, so its fast enough. but its getting WA on test 5 and i cant seem to find a simple counterexample.

→ Reply

2 months ago, # ^ |

nvm, got it

→ Reply

PaarthJuneja

2 months ago, # |

i went from getting a +65 in yesterday's contest to literally not being able to solve a single problem today. cf contests are SUCH a rollercoaster i swear :\

→ Reply

pranavoak7698

2 months ago, # |

Sorry Demon_Master

→ Reply

SilverCipher

2 months ago, # |

← Rev. 2 →

+10

Educational contest educated me that I know nothing. Nothing: No, you don't know me. Me: He knows me. He: Who, are you? Who: No, I am not "?". Not: No, your not Not. No: I know.

→ Reply

invincible_rj

2 months ago, # |

C was easier than B, also A was weird. not a balanced contest tbh,

→ Reply

satwika_55

2 months ago, # |

What the hell was that B question ?? After several incorrect submissions, I came to a conclusion that its a BS + DP problem.

→ Reply

Hazer_BJU

2 months ago, # ^ |

For even numbers, it is only possible to paint them pairwise from left to right. For odd numbers, you can delete one element and solve it as even numbers.

→ Reply

2 months ago, # ^ |

← Rev. 2 →

you can bruteforce it: for n even, just pair up all values, for n odd, fix every value and pair the others and see which way you get the minimum cost

→ Reply

Hazer_BJU

2 months ago, # |

-8

I can't figure out why this code got WA on D. How mysterious.

#include <bits/stdc++.h>
#define MAXN 300005
using namespace std;
typedef long long llong;
llong n,q,L,R;
llong a[MAXN],presum[MAXN],sumsum[MAXN],press[MAXN],ppsum[MAXN];
llong find_pos(llong p) {
	llong l=1,r=n+1;
	while(r!=l+1) {
		llong mid=(l+r)/2;
		if (n*(n+1)/2-(mid-1)*mid/2>=p) l=mid;
		else r=mid;
	}
	return l;
}
llong query(llong p) {
	if (p==0) return 0;
	llong len=find_pos(p),order=n-len+1;
	llong starting=n*(n+1)/2-len*(len+1)/2+1;
	llong minus=presum[order-1];
	llong ans=ppsum[p-starting+order]-ppsum[order-1]-minus*(p-starting+1)+press[order-1];
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for (llong i=1;i<=n;i++) {
		cin>>a[i];
		presum[i]=presum[i-1]+a[i];
		ppsum[i]=ppsum[i-1]+presum[i];
		sumsum[1]+=presum[i];
	}
	press[1]=sumsum[1];
	for (llong i=2;i<=n;i++) {
		sumsum[i]=sumsum[i-1]-(i-1)*(n-i+2);
		press[i]=press[i-1]+sumsum[i];
	}
	cin>>q;
	for (llong i=1;i<=q;i++) {
		cin>>L>>R;
		cout<<query(R)-query(L-1)<<'\n';
	}
	return 0;
}

→ Reply

vuysztrcKJBHVIUVbkjbkhj

2 months ago, # |

← Rev. 2 →

-8

please help me to find why this code is not working for c https://codeforces.net/contest/2026/problem/C

//this is code
#include <iostream>
#include <string>
using namespace std;
 
int main() {
    int tc;
    cin >> tc;
    while (tc-- > 0) {
        int n;
        cin >> n;
        string str;
        cin >> str;
        int s = 0, e = str.length() &mdash; 1;
        long long ans = 0;
        
        while (s <= e) {
            if (e - 1 >= s && str[e - 1] == '0') {
                int idx = e - 1;
                while (idx >= s && str[idx] == '0') {
                    ans += (idx + 1);
                    idx--;
                }
                e = idx;
            } else {
                ans += (s + 1);
                s++;
                e--;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

→ Reply

chenhongrui

2 months ago, # |

Awesome contest!I am rank 3 and will become IM!

→ Reply

2 months ago, # ^ |

orz

→ Reply

Hardy_Lee

2 months ago, # |

Why unrated?

→ Reply

Tannyyyyy12

2 months ago, # ^ |

Ratings will change in sometime i guess..

→ Reply

Hardy_Lee

2 months ago, # ^ |

But unrated allowed maybe.

→ Reply

TokaiZaopen

2 months ago, # |

+36

problem D makes me feel like I'm not participating in CP …… All of the difficulty is to write the code. Too little about algorithm and too much about coding. Well, maybe it can help us improve our coding ability ……

→ Reply

Lirnited

2 months ago, # ^ |

problem E is also not good. If you know Maximum Weight Closed Subgraph you can solve it quickly, but if you don't know that you are hardly solve it.

I think Div .2 D and E should have good ideas without too hard code or too hard algorithm.

→ Reply

vgoofficial

2 months ago, # ^ |

+28

Isnt the point of Educational Rounds to teach these topics to a wider range of participants?

→ Reply