Educational Codeforces Round 93 [Rated for Div. 2]

4 years ago, # ^ |

→ Reply

Peaceful_warrior_

4 years ago, # ^ |

← Rev. 4 →

14th Aug — educational codeforces round 93

15th Aug — atcoder beginner contest 175, Facebook hacker cup round 1,Codevita

16th Aug — codeforces Global round 10,Google Internship Test

BUSY DAY's

May I couldn't Perform well in these 3 days but i will learn many new things..

I am also excited!

All the Best

→ Reply

Snake_Eyes1999

4 years ago, # ^ |

bro, did you get the mail regarding google internship test.Since, I also register for internship but haven't got any mail regarding this.

→ Reply

Peaceful_warrior_

4 years ago, # ^ |

Not yet but my friends got. I registered at last date so, i guess they are sending email according to registration date

→ Reply

manpreet.singh

4 years ago, # ^ |

I also registered at last date and didn't get mail.

→ Reply

BigOf1

4 years ago, # ^ |

Yes ,I got the mail..

→ Reply

hackersarkar12

4 years ago, # |

-24

can anyone tell me the soultion approach of codeforces div 2 664 c problem. http://codeforces.me/contest/1395/problem/C

→ Reply

AlexLorintz

4 years ago, # ^ |

You can just brute force the answer, i was pretty annoyed that i did not manage to solve it during the contest https://codeforces.me/contest/1395/submission/89732090 ...

→ Reply

hackersarkar12

4 years ago, # ^ |

-6

but i dont understand the brute force logic

→ Reply

AlexLorintz

4 years ago, # ^ |

← Rev. 2 →

+11

Every element of the array a (i will use the definitions from my code) can be combined with any element from the array b. So for every element with index i from a (i = 0 , N — 1) you create an array arr of M elements where arr[j] (j = 0 , M — 1) = a[i] & b[j]. If i == 0 (we are at the first element of the array) we mark in the bitset as true every element from arr and if i > 0 we will iterate over the bitset and we will mark as true in a new bitset the values val | arr[j] where val is a value from the first bitset which was already marked as true. By doing this at every step i (i = 0 , N — 1) you will have marked in the bitset every possible result for the expression c[0] | c[1] | ... c[i] (c having the meaning from the statement). After that you copy the second bitset in the first one. The bitset from the end will have marked as true every value which is a possible answer for the problem.

PS. 512 is the size of the bitset because the maximum possible answer is 511(2^9-1). I hope that my explanation is decent.

→ Reply

hackersarkar12

4 years ago, # ^ |

+20

thanks bro

→ Reply

YPK

4 years ago, # ^ |

you will find it in Competitive Programmer’s Handbook(by Antti Laaksonen), page no.102.

I learned a lot from this book

→ Reply

4 years ago, # ^ |

+14

you should ask this in the editorial part of that round, this is not related to this round.

→ Reply

AnsariMohsin

4 years ago, # |

-8

Standard Div2 round vs Educational round , which do you think is tougher ?

→ Reply

dv.jakhar

4 years ago, # ^ |

+20

div 2 I guess

→ Reply

fff

4 years ago, # ^ |

for me educational rounds are easier than div2

→ Reply

City_Hunter

4 years ago, # ^ |

← Rev. 2 →

+17

Don't know which one is tougher. But for me, problems from educational rounds seem to be more interesting.

→ Reply

Hikarii

4 years ago, # ^ |

It's different for me, I enjoy solving standard Div 2 more, I usually get pretty upset while solving Educational rounds.

→ Reply

roshan_mehta

4 years ago, # |

-18

where is the comment-As a Tester give me a contribution..LOL

→ Reply

blaze999

4 years ago, # |

-23

what is the scoring distribution?

→ Reply

Just_a_programmer

4 years ago, # ^ |

In educational rounds, all the problems have same weight-age, therefore there is no scoring distribution.

→ Reply

jayantjha1109

4 years ago, # ^ |

-13

Do all the problems have same difficulty too?

→ Reply

Just_a_programmer

4 years ago, # ^ |

No, generally they are sorted in the order of non-decreasing difficulty.

→ Reply

Hamim99

4 years ago, # |

-13

Lucky month for competitive programmer

→ Reply

Ali_Adelkhah

4 years ago, # |

← Rev. 2 →

-22

good contest

→ Reply

PedroPerale

4 years ago, # |

+148

I got covid 19, I am on my fourth day of isolation. I'm not feeling very well, but codeforces has helped me a lot to distract myself, wish me luck in this contest

→ Reply

PedroPerale

4 years ago, # ^ |

Thanks Codeforces for all the contests in this month

→ Reply

A-m-z

4 years ago, # ^ |

That's sick af.

→ Reply

Trying

4 years ago, # ^ |

-21

Literally

→ Reply

AriaH

4 years ago, # ^ |

+12

Just chill!

→ Reply

manik.jain

4 years ago, # ^ |

+18

Sorry to hear that man. Good luck today!

→ Reply

conan1024hao

4 years ago, # ^ |

Hope you get well soon

→ Reply

4 years ago, # ^ |

Best wishes to you. I hope you will recover soon.

→ Reply

NeighboursFish

4 years ago, # |

+33

I don't really understand why they say "6 or 7 problems". Aren't they sure about the number of problems till the last minutes?

→ Reply

4 years ago, # |

-62

Let us see what are we going to have today, long queue, weak pretest, complicated problem statement, or all of these together.

→ Reply

math_is_love

4 years ago, # ^ |

Educational rounds don't have pretests.

→ Reply

mihirarora

4 years ago, # |

+31

→ Reply

codemastercpp

4 years ago, # ^ |

← Rev. 2 →

Can relate, I had WA on test 6 but then got stuck at WA on test 7.

→ Reply

swag3301

4 years ago, # ^ |

WA on test case 6 LMFAO

→ Reply

4 years ago, # ^ |

Test 6 failed then try this:
1 3 1
10
8 5 3
12
Expected: 146

→ Reply

Rudro25

4 years ago, # ^ |

my code gives output:146..... but i got WA on 6

→ Reply

4 years ago, # ^ |

Ohh yes now I remeber there is some more issue. I changed my entire approach instead of doing greedy I went to DP.

→ Reply

coding_lover

4 years ago, # ^ |

can you please explain why the greedy logic does not work in problem D

→ Reply

4 years ago, # ^ |

I dont know fully. The test case I mentioned clearly show we have to do some case work when 2 colors with 1 pair and one with more than one remains. So may be some more such case work would be required to make it work. Has anyone solved this using Greedy, if yes please comment your submission id.

→ Reply

nagaraj41

4 years ago, # ^ |

← Rev. 2 →

Try 2 2 2
2 2
2 2
2 2
ans: 12

→ Reply

TheScrasse

4 years ago, # ^ |

← Rev. 2 →

+16

For those wondering: test 7 could be something similar to

Some greedy approaches print 32, but the answer is 48.

→ Reply

Kabir_125

4 years ago, # ^ |

now i got this . thanks bro

→ Reply

snorkel

4 years ago, # |

Am I only one who couldn't access codeforces for almost an hour during the contest? (I posted this and got downvoted, idk why).

→ Reply

hetp111

4 years ago, # ^ |

+13

Yes.

→ Reply

Tolydi_Kniper

4 years ago, # |

It seems nowadays codeforces has better problems than atcoder... — aid

just look at problem G today and you'll find you were wrong.

→ Reply

mango_lassi

4 years ago, # ^ |

Why don't you like problem G? For an educational round, it is fine. I dislike E and F much more.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

Could you explain your solution? I look at your code but cannot get it. Thanks in advance.

UPD: Nevermind, I understood it now. I think your sieve-like code for handling the largest divisor is so smart.

→ Reply

4 years ago, # ^ |

Will u plz tell , were E and F too boring or among the standard ones ??

→ Reply

mango_lassi

4 years ago, # ^ |

They were definitely not standard problems, and for an educational round that wouldn't even be an issue. I didn't really like how E was pretty much an implementation exercise. Looking back, F wasn't actually that bad.

→ Reply

4 years ago, # ^ |

Yup .. Personally i also think that F was good , and also E was heavy implementation (especially for me who did coordinate compression and segment tree) .

→ Reply

abhishek2408

4 years ago, # |

It was really an educational round reminded me to study ..

→ Reply

VeryGoodVeryGood

4 years ago, # |

I got problem A wrong, than was stuck on it to realise my initial idea was correct. Skipped B and went to solve C, cause I couldn't improve ranking at that point. Never solved C, I'm starting to believe I am dumb at this point...

→ Reply

4 years ago, # ^ |

Don't be shy bro. Most of us started like that if you don't want to believe, just check my rating graph

→ Reply

arsalan9911

4 years ago, # ^ |

I can relate to this & it even become worse when no one is there for help. Just keep practicing & don't hesitate to look for editorial & video solution. In case you need any help in A & B you can refer this

→ Reply

4 years ago, # |

+17

What a nice contest but I think D is a little easy with typical DP

→ Reply

anish_sk

4 years ago, # ^ |

Could you please explain the states of your dp?

→ Reply

4 years ago, # ^ |

F[i][j][k]=maximum sum from first i largest R, j largest G, k largest B.

→ Reply

4 years ago, # ^ |

I'm not good at explaining things so sorry in advance if people feel my explaination harsh

→ Reply

4 years ago, # ^ |

You need to do some greedy before this typical dp. This costed me 2 WA.

→ Reply

4 years ago, # ^ |

as I said before, you must DP with i largest, j largest, k largest so you must sort three arrays before dp

→ Reply

4 years ago, # ^ |

+11

Yeah, that's why it's not a classical dp. You need to be clever enough to get the idea.

→ Reply

Overmout

4 years ago, # ^ |

Oh. I tryed to use dp but missed some status trans

→ Reply

helth

4 years ago, # ^ |

I don't think this was an easy problem. Maybe it's not hard to guess that the solution is dp but if you want to be sure that this solution is correct you need to prove that in the maximum total area obtained by using i red sticks, j green sticks and k blue sticks there exists a rectangle with sides (ri, gj) or (ri, bk) or (gj, bk). Maybe I'm missing something but it wasn't trivial and took me a while to prove.

→ Reply

Atish508

4 years ago, # |

how to solve C please help

→ Reply

4 years ago, # ^ |

+47

You subtract 1 from every element and it becomes a standard problem. https://www.geeksforgeeks.org/number-subarrays-sum-exactly-equal-k/

→ Reply

swag3301

4 years ago, # ^ |

Elaborate , coz i still dont get it.

→ Reply

4 years ago, # ^ |

+10

When you subtract 1 from each element, the problem becomes counting the number of subarrays whose sum is 0.

→ Reply

swag3301

4 years ago, # ^ |

OMFG. There is no way u came up with this during the contest. You had to have solved this type of problem earlier. Anyway,Thanks man!

→ Reply

mpily

4 years ago, # ^ |

+38

how i realized it during the contest instead of writing it as

$$$\sum_{l}^{r} ( a_i ) = r-l+1$$$

write it instead as

$$$\sum_{l}^{r} ( a_i ) = \sum_{l}^{r}(1)$$$

which is equivalent to

$$$\sum_{l}^{r} ( a_i ) - \sum_{l}^{r}(1) = 0$$$

→ Reply

_ansh_

4 years ago, # ^ |

This is so beautiful <3

→ Reply

keep_it_aniii

4 years ago, # ^ |

mpily really liked your thought process man... appreciable!!!

→ Reply

Prometheus32

4 years ago, # ^ |

I saw the solution and was unable to digest why subtract by 1. Now it's clear. Thanks man.

→ Reply

Hamim99

4 years ago, # ^ |

your explanation is superb

→ Reply

decoder__

4 years ago, # ^ |

Could you elaborate more?

→ Reply

4 years ago, # ^ |

+29

The problem asks you to count the number of subarrays whose sum equals to its length right. So imagine if we subtract 1 from every element of that subarray, we end up subtracting the length of the subarray from the sum of its elements! If that subarray satisfy the condition of the problem statement then this new sum must be 0. That is why after subtracting 1 from all elements we count the number of subarrays whose sum is 0. Hope it helps.

→ Reply

dhritishman22

4 years ago, # ^ |

That was so cool! Thanks.

→ Reply

waltz47

4 years ago, # ^ |

Why are you adding map[cursum] everytime to the answer?

→ Reply

4 years ago, # ^ |

It is actually Map[cursum-0] which counts the number of prefixes ending before the current position. This number is equal to the number of subarray ending at the current position whose sum is 0. You could read the following article: https://www.geeksforgeeks.org/number-subarrays-sum-exactly-equal-k/

→ Reply

Harshil_

4 years ago, # ^ |

← Rev. 3 →

+12

first create prefix array then

then this should be true for subarray of (l,r) to be good.

prefix[r] - prefix[l - 1] = (r -l) + 1

l - prefix[l - 1] = r - prefix[r] + 1;

try to understand this part on your own

map<int,int> mp;
int ans = 0;
for(int i = 1; i <= n; i++){
    mp[i - prefix[i - 1]]++;
    int val = i - prefix[i] + 1 ;
    ans += mp[val];
}

→ Reply

nykterstein

4 years ago, # ^ |

wow! awesome approach!

→ Reply

floch

4 years ago, # ^ |

My solution was a bit more complicated than cote's solution, but I think it is worth sharing. Let $$$p_i$$$ be the sum of the interval $$$a_{1, \ldots i}$$$ for all $$$i$$$ (prefix sums). Now let $$$c_i = p_i - i$$$. Notice that the number of good intervals starting in $$$1$$$ is the number of ocurrences of $$$0$$$ in $$$c_i$$$. For that we will keep a map $$$cnt$$$, where $$$cnt[x]$$$ is the number of ocurrences of $$$x$$$ in $$$c_i$$$. Now, we will "remove" the first element and update the prefix sums and $$$c_i$$$. Notice that all values of $$$c_i$$$ will change by a same value

$$$d + c_i = c_i - a_0 - (i - 1) \Rightarrow d = -a_0 + 1.$$$

Then we have that the

$$$cnt[x] = cnt[x - d]$$$

. So it is sufficient to keep a variable d and update it in each iteraction (and thre is no need to update $c_i$ or $$$p_i$$$). Submission: 89922879

→ Reply

MyLastHour

4 years ago, # |

Problem D.... why????

→ Reply

mohitfps10

4 years ago, # |

Solutiom of C in less than O(n^2)..??

→ Reply

4 years ago, # ^ |

i think it should be O(n) using hash map or something

→ Reply

madlogic

4 years ago, # ^ |

← Rev. 3 →

After getting the prefix sums
Basically what you need to find is $$$pref[r] - pref[l - 1] = r - l + 1$$$
Equating that it becomes $$$pref[r] - r = pref[l - 1] - l + 1$$$
So at index i you need to count the indices $$$j <= i$$$ with $$$pref[i] - i == pref[j - 1] - j + 1$$$

Code

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> prefix(n);
    prefix[0] = s[0] - '0';
    for (int i = 1; i < n; i++)
      prefix[i] += prefix[i - 1] + (s[i] - '0');
    map<int, int> dp;
    long long ans = 0;
    dp[1] = 1;
    for (int i = 0; i < n; i++) {
      if (i)
        dp[prefix[i - 1] - i + 1]++;
      int cur = prefix[i] - i;
      if (dp.count(cur))
        ans += dp[cur];
    }
    cout << ans << '\n';
  }
  return 0;
}

→ Reply

Ghost0fSparta

4 years ago, # ^ |

You can convert it to pref[r]-pref[l] = r-l

→ Reply

aceofspade1

4 years ago, # ^ |

Why dp[1]=1 ?Thanks

→ Reply

madlogic

4 years ago, # ^ |

Notice for all $$$i$$$ I increase $$$pref[i - 1] - i + 1$$$
So for $$$i = 0$$$ $$$pref[i - 1] = 0$$$ and $$$pref[i - 1] - 0 + 1 = 0 - 0 + 1 = 1$$$
So basically I increase for $$$i = 0$$$ at the beginning

→ Reply

RalseiJevil

4 years ago, # |

What was testcase 7 of problem D?

→ Reply

RedDreams

4 years ago, # ^ |

← Rev. 2 →

test:

4 2 2

3 3 3 3

4 4

your ans = 4 * 4 + 4 * 4 = 32

correct ans = 3 * 4 + 3 * 4 + 3 * 4 + 3 * 4 = 48

→ Reply

jayantjha1109

4 years ago, # ^ |

I got WA on test 7 too and couldnt figure out where I went wrong. But then I realized this test case gave me a WA-

3 3 3 3 3 3 3 3 3 3 3 3

The answer to this should be 36 but it gives me 27. I hope this might help.

→ Reply

zass

4 years ago, # |

← Rev. 3 →

Getting AC in D in like 10 mins but not getting any logic whatsoever for C hurts a lot.

→ Reply

hetp111

4 years ago, # ^ |

sum(l,r)=r-l+1

sum(l,r)-(r-l+1)=0

v[l]-1 + ... + v[r]-1 = 0

so just subtract 1 from every element, and find all sub arrays with sum==0

→ Reply

1a2a3a

4 years ago, # |

I think C is more difficult than D...T^T.. How to solve C?

→ Reply

MyLastHour

4 years ago, # ^ |

Calculate the prefix sums p[i]. If p[i]-p[j] = i-j, then j+1..i is a good subarray. However, this equation can be rearranged to p[i]-i = p[j]-j. It suffices to find all values of p[i]-i and use some math to calculate the number of pairs.

→ Reply

1a2a3a

4 years ago, # ^ |

oh...Thanks for your kind comment.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

+47

Here's a nice transformation:

$$$ \begin{align} & \sum\limits_{i=l}^r a_i = r - l + 1 \\ \implies & \left( \sum\limits_{i=l}^r a_i \right) - (r - l + 1) = 0 \\ \implies & \left( \sum\limits_{i=l}^r a_i \right) - \left( \sum\limits_{i=l}^r 1 \right) = 0 \\ \implies & \sum\limits_{i=l}^r (a_i - 1) = 0 \end{align} $$$

Becomes much easier to code because the goal sum doesn't change.

→ Reply

1a2a3a

4 years ago, # ^ |

wow.......

→ Reply

Satwik_Tiwari

4 years ago, # ^ |

That's a very good solution tbh.

→ Reply

4 years ago, # ^ |

I exactly did this .. But took a quite more time

→ Reply

2147483648

4 years ago, # |

+38

It was really good round, my nickname is lying :)

→ Reply

4 years ago, # |

How to solve E? Can it be solved using set and priority_queue.

→ Reply

4 years ago, # ^ |

Implemented segment tree and got WA on test 4.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

Coordinate Compression + Segment Tree I saw other peoples' code also and they implemented it using set only but i don't know about it .

→ Reply

https://codeforces.me/contest/1398/submission/89953351

4 years ago, # ^ |

Can you tell your approach please.

→ Reply

bc_mc_bsdk_mkc

4 years ago, # |

please anyone tell what's wrong in my solution in D (it's giving WA on test#7)

→ Reply

RedDreams

4 years ago, # ^ |

test:

4 2 2

3 3 3 3

4 4

your ans = 4 * 4 + 4 * 4 = 32

correct ans = 3 * 4 + 3 * 4 + 3 * 4 + 3 * 4 = 48

→ Reply

Noobmaster666

4 years ago, # |

can anyone help me out? I can't figure out why i failed test case 2 for problem c. I have created a consecutive sum array(i dont remember the actual name) and then checked for windows of all sizes.89943421

→ Reply

MijPeter

4 years ago, # ^ |

There are about 10^5 * 10^5 = 10^10 windows of all sizes. 10^10 things to do is too much for this time limit.

→ Reply

vineetjai

4 years ago, # |

← Rev. 3 →

C is a standard problem often asked at AtCoder beginner rounds.[the idea is just to use prefix sums]

Edit: finally question reduces to find (i,j) pair such that j>i && pre[j]-pre[i]=j-i which can be easily solved using map.

→ Reply

retr0coderxyz

4 years ago, # ^ |

Can you explain a bit elaborate please :)

→ Reply

DiabolicPrism

4 years ago, # ^ |

← Rev. 4 →

+17

Let $$$sum_{i}$$$ be the sum of elements till position $$$i$$$.

If you have two positions $$$i$$$ and $$$j$$$, $$$i \lt j$$$, if $$$sum_{i} - i = sum_{j} - j$$$, re-arranging the terms we see that $$$sum_{j} - sum_{i} = j - i$$$, i.e, the sum between their positions is clearly equal to the distance between them. So we just need to keep track of the count of elements with equal $$$sum_{i} - i$$$.

Now we note that since between all pairs with the same $$$sum_{i} - i$$$ the sum of elements must be equal to the distance between them, if the cnt of $$$sum_{i} - i$$$ occurs $$$k$$$ times, we have $$$k - 1$$$ subarrays which are adjacent to each other from which we want to form a subarray. So there are $$$k - 1$$$ ways of choosing $$$1$$$ continous subarrays, $$$k - 2$$$ of $$$2$$$ continous subarrays and so on, which is just the sum of the first $$$k -1$$$ natural numbers, or $$$\frac{(k - 1) \times k}{2}$$$ possible subarrays.

My submission: 89890437

→ Reply

ghost1733

4 years ago, # ^ |

elegant explanation.

→ Reply

sevlll777

4 years ago, # ^ |

+18

In educational rounds problem can be standard it is OK

→ Reply

Matuagkeetarp

4 years ago, # ^ |

I thought of using prefix sums to get sum of range in O(1) but still for every subarray to consider it will be O(N*N), Can you help me in understanding this a bit?

→ Reply

RalseiJevil

4 years ago, # ^ |

What you need is pre[r] — pre[l-1] = r — l + 1. You can rewrite this equation as pre[r] — r = pre[l-1] — (l-1), so for every good subarray, pre[i] — i is constant at the ends of it. Now you just have to make pairs

→ Reply

an09mous

4 years ago, # ^ |

Can you tell me what is the need for a[i] to be between 0 and 9? It confused me a lot and consumed a lot of my time.

→ Reply

vineetjai

4 years ago, # ^ |

← Rev. 2 →

for higher values of a[i] algo still works.

→ Reply

an09mous

4 years ago, # ^ |

Yes, that 0 to 9 constraint created a lot of confusion for me.

→ Reply

vrooooom

4 years ago, # ^ |

There is no need. I think it was just to throw you off... All that mattered was subtracting 1 from every element and then doing prefix sums, and checking for 0.

→ Reply

an09mous

4 years ago, # ^ |

Yes, that really threw me off. Wasted an hour on C ;_;

→ Reply

DiabolicPrism

4 years ago, # |

← Rev. 3 →

Any idea what is test case 2 of E or what is wrong with my idea?

My idea was as follows:

If after any operation we have $$$k$$$ lightning spells, then we need to keep track of the sum of the $$$k$$$ most powerful spells, while ensuring at max $$$k - 1$$$ of those are lightning spells (use a fire spell of power 0 as a dummy spell if needed). We can maintain the non-doubled spells using multisets in descending order and the doubled ones using multisets in ascending order for both types of spells. Change in sum can be tracked at the time of transistion of elements between these sets. Is the idea wrong or did I go wrong somewhere in implementation?

→ Reply

ALXHXO

4 years ago, # |

Hello, what was the idea in problem D? I assumed that it's always optimal to choose the first two biggest sides of different collor and add the area to the answer. I am really curious to know the problem since I got wrong answer on test 6!

→ Reply

MyLastHour

4 years ago, # ^ |

There is the case where some of the sides are equal.

→ Reply

ALXHXO

4 years ago, # ^ |

That is not a problem since a square is also considered rectangle as we can understand from the test samples!

→ Reply

4 years ago, # ^ |

I used 3d dp to solve it. Sort all the r, g, b arrays.

Now for state solve(i, j, k) => we can have 3 possibilities

solve(i-1, j-1, k) + r[i]*g[j]
solve(i, j-1, k-1) + g[j]*b[k]
solve(i-1, j, k-1) + r[i]*b[k]

Take max of all the three. You will have your answer.

Here is the link to code using above approach https://codeforces.me/contest/1398/submission/89925922

→ Reply

ALXHXO

4 years ago, # ^ |

This is a great idea, thank you. Probably my mistake was that I haven't found any counterexample during contest so I assumed that there is no need for backtraching stuff. (Or 3d dp)

→ Reply

Anshumann

4 years ago, # ^ |

using greedy is wrong because by doing so you might end up with a lesser number of rectangles ,which in turn might reduce the final output. For example lets say we have red array of size 20, green of size 20 and blue of size 190, using greedy u might use all the elements of red and green arrays first (resulting in just 20 rectangles) but there is a possibility of having 40 rectangles if u also choose elements from the blue array.

→ Reply

Nikhil_Kr

4 years ago, # ^ |

do we need to sort the array if i apply this logic, 1. solve(i-1, j-1, k) + r[i]*g[j] 2. solve(i, j-1, k-1) + g[j]*b[k] 3. solve(i-1, j, k-1) + r[i]*b[k] 4. solve(i-1,j,k) 5. solve(i,j-1,k) 6. solve(i,j,k-1)

89945848 mine logic without sorting, can u point out where am i going wrong

→ Reply

hopesanddreams

4 years ago, # ^ |

← Rev. 3 →

3 2 1 3 4 5 5 6 7

→ Reply

sunio

4 years ago, # ^ |

← Rev. 2 →

Check for this testcase

2 2 2

5 1

4 4

Correct Output (DP) : 41

→ Reply

tarptaeya

4 years ago, # |

Why greedy does't works for D??

→ Reply

el_heffeh

4 years ago, # ^ |

← Rev. 2 →

Check out this test case:
1 2 2
7
5 3
6 2

Greedy gives 52 as an answer, but the correct one is 53.

→ Reply

vongkh

4 years ago, # ^ |

cool. How did you come up with this counterexample?

→ Reply

el_heffeh

4 years ago, # ^ |

during the contest, when I kept on getting WA on test 6 (and eventually never got it)

→ Reply

vongkh

4 years ago, # ^ |

I kept getting WA on test 6 too but I couldn't think of any counter example. So I believed that greedy algorithm should work. I spent 40 min staring at my code trying to find stupid implementation mistake xD.

→ Reply

Mksiyak

4 years ago, # ^ |

← Rev. 3 →

A simpler one :

1 1 2

3 2

if we take 5 and 4 we can't include (3 and 2).

so optimal answer is 5*3+4*2

→ Reply

4 years ago, # ^ |

I tried greedy too but failed miserably.

→ Reply

Fuad

4 years ago, # ^ |

← Rev. 2 →

My Greedy solution for D was taking all the combination of 3 types of triangle. Since there can be 3 types of triangle, there are 200*200*200 combinations to choose from. Each combination tells how many triangles I will make of each type. I only worked with the valid combinations so that I don't get TLE. Then I am greedily taking the maximum product and not taking any more triangles of a type than what my combination says. Can anyone tell me why it does not work?

→ Reply

adityaRaj28

4 years ago, # ^ |

tryed the same dude, now i know its wrong on 4 2 2 3 3 3 3 4 4 4 4

Correct output : 48 We got : 32

→ Reply

Fuad

4 years ago, # ^ |

← Rev. 2 →

My solution is giving the correct output 48. Still don't why it won't work. Here's my last submission 89977686

→ Reply

4 years ago, # |

What's the test 4 for problem E? I was using two sum segment tree one for lightning spells with twice the value of d and another for fire spell for value d. Also tracked minimum of lightning spells and maximum of fire spells by set and then computed the answer. Resulting WA on test 4.
89951160
In my submission, vectors are defined as sum -> lightning, sum2 -> fireball, v -> lightning, v2 -> fireball, st1 -> lightning, st2 -> fireball

→ Reply

arutsudar

4 years ago, # |

+11

Really nice Problemset :-)

→ Reply

4 years ago, # |

In E I had to query the sum of the k largest elements. Is there a data structure that supports this?

I used a messy combination of segment and fenwick trees and the fact that we know all elements before.

→ Reply

Marisa

4 years ago, # ^ |

← Rev. 2 →

You can do it with just two sets. First set will contain k largest elements, and second set all other elements.

→ Reply

4 years ago, # ^ |

Can you please explain the approach.

→ Reply

Marisa

4 years ago, # ^ |

Since k can change by at most one, you will need to remove\add only 1 element. Also after inserting element you need to swap elements if minimum of first set is smaller than maximum of second set.

→ Reply

taran_1407

4 years ago, # ^ |

+11

Treap can easily handle that.

→ Reply

4 years ago, # ^ |

Thanks. I never used a Treap before

→ Reply

4 years ago, # ^ |

Why k largest elements? Isn't it 2 * (sum of lightning) + sum of fire + maxfire — minlightning and if there is no lightning then simply sum of fire

→ Reply

4 years ago, # ^ |

My approach definitely wasn't the simplest

→ Reply

4 years ago, # ^ |

I see, I asked why my one is wrong? I am getting WA on test 4 implementing segment tree using this idea

→ Reply

4 years ago, # ^ |

Sometimes it is optimal to cast lightning, fire, lightning, fire, etc.

→ Reply

4 years ago, # ^ |

Got it now. Thanks.

→ Reply

realnimish

4 years ago, # ^ |

Is it so? Consider the case where you have 3 lightning spell with damage 1,2,3 and 3 fire spell with damage 10,20,30. I believe the maximum damage should be 126 but your formula evaluates to 101.

→ Reply

4 years ago, # ^ |

Got it man. I was foolish enough to get it.

→ Reply

_pastor_

4 years ago, # ^ |

https://codeforces.me/contest/1398/submission/89908543 tm william's solution is very neat.

→ Reply

phibrain

4 years ago, # ^ |

you can do that offline compressing all values and using segment tree.

→ Reply

geekpradd

4 years ago, # ^ |

Policy based data structures can also work (but I ended up getting WA for some reason)

→ Reply

fauji

4 years ago, # |

+22

→ Reply

isocyanide7

4 years ago, # ^ |

Agreed.

→ Reply

SarthakBansal

4 years ago, # |

← Rev. 2 →

-6

Ciao Rating !

→ Reply

wish2lucky

4 years ago, # |

This game really pisses me off

→ Reply

Nikhil_Kr

4 years ago, # |

In question D, why do we have to sort the arrays before applying DP, i code it without sorting but it was giving wrong ans but after sorting with same logic it was giving right ans?

→ Reply

Nikhil_Kr

4 years ago, # ^ |

code without sorting 89945848 give wrong ans. code with sorting 89955750 gives right ans.

→ Reply

Aesir

4 years ago, # |

Too sad, I can't implement E in time (in 30 mins) :((. How can I improve my coding speed

→ Reply

LimitBreaker

4 years ago, # |

About problem C: Let's consider s[l], s[l+1], .., s[r] so if s[l]+s[l+1]+..+s[r] = r- l + 1 then s[l..r] is good s[l]+s[l+1]+..+s[r] = 1 + 1 + 1 + .. + 1 (r — l + 1) s[l] — 1 + s[l+1] — 1 + ... = 0 so the problem switches to finding the number of subarr (after decreasing by 1 each element) which has sum = 0 (can be easily done by map)

→ Reply

dcordb

4 years ago, # |

It seems testcases are weak on problem E, this slow solution passes. Go ahead and hack it! 89956850

→ Reply

AlwaysACoder

4 years ago, # |

+27

Here's a simple alternate for C: Decrease all the values in the array by 1, and now you need to find the number of subarrays which has sum equal to 0.

Btw, how to solve F?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

+15

Let's try to find the answer for each len $$$l$$$.

Let $$$f(pos, len)$$$ = maximum possible number of sets that could have already finished considering $$$s[pos::]$$$ and number of contiguous rounds required is $$$len$$$.
Now, If $$$s[pos], s[pos+1] ...s[pos+len-1]$$$ doesn't contains both $$$1$$$ and $$$0$$$ then $$$f(pos,len) = 1 + f(pos+len, len)$$$.
Otherwise, find the minimum index $$$idx$$$ in $$$(pos, pos+len-1)$$$ such that $$$s[idx], s[idx+1]..s[pos+len]$$$ doesn't contains both 1 and $$$0$$$ and then $$$f(pos, len) = f(idx, len)$$$.

The time complexity of the solution will be $$$O(N+N/2+N/3...) = O(Nlog(N)).$$$

The solution was simple but I was not able to prove that time complexity is $$$O(N(log(N))$$$ but the the basic proof is that lets in one iteration you are going from $$$pos$$$ to $$$idx1$$$ where $$$idx1$$$ can be $$$pos+1$$$ but in the next iteration you will definitely jump from $$$idx1$$$ to $$$idx2$$$ such that $$$idx2 >= pos + len$$$ thus at max total $$$2 * (N/len)$$$ iterations will be there for a single $$$len$$$.

→ Reply

tuananh238

4 years ago, # ^ |

How do you perform step 3?

I use Segment Tree, so the total complexity is O(n*log(n)^2), and my submission runs in ~1.9s, nearly TLE.

→ Reply

4 years ago, # ^ |

For every index, Calculate the previous index such that it has one and also the previous index such that it has zero.

$$$if(s[pos+len]== ?)idx = min(prev_zero[pos+len], prev_one[pos+len]) +1$$$
$$$if(s[pos+len]==1)idx = prev_zero[pos+len] + 1$$$
$$$if(s[pos+len]==0)idx = prev_one[pos+len] + 1$$$

→ Reply

decoder__

4 years ago, # ^ |

Can you elaborate more on this?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

Short proof:

→ Reply

TryAgain2

4 years ago, # ^ |

I understood this proof but why we use frequency to calculate the total answer ?

→ Reply

4 years ago, # ^ |

The goal is to find all possible $$$l$$$ s for our current $$$r$$$.

Let $$$prefix(i) = A[1] + A[2] + ... + A[i]$$$. Suppose our current prefix sum $$$prefix(r) = x$$$. Since $$$prefix(r) - prefix(l-1) = A[l] + A[l+1] + ... + A[r-1] + A[r]$$$, then for all $$$j < r$$$ such that $$$prefix(j) = x$$$, we know $$$prefix(r) - prefix(j) = 0$$$. We keep the frequency of every $$$prefix(j)$$$ to search for how many of them are equal to $$$x$$$.

→ Reply

TryAgain2

4 years ago, # ^ |

Thanks very much . i understood this approach very will.. but in general how can i know like these proofs by myself in the contest !? any suggestions to improve my skills ?

→ Reply

4 years ago, # ^ |

The trick with using prefix sums to calculate subarray sums is very common because it has so many uses. This particular problem is one that comes up every so often. You just need to keep practicing so that you'll learn these new techniques and remember them for future contests :)

→ Reply

Noureldin

4 years ago, # ^ |

think of the brute force solution then optimize it, you can find the answer for any x in O(n) like this

pseudocode

def f(x):
  i = 0
  ret = 0
  while i+x <= n:
       any_ones = #is there any ones between [i, i + x - 1]
       any_zeros= #is there any zeros between [i, i + x - 1]
       if any_ones and any_zeros:
            #can't win the round between i and i + x -1
            i += 1
       else:
            #can win the round
            ret += 1
            i += x
  return ret

this obviously takes $$$\mathcal{O}(N^2)$$$ but we can make it $$$\mathcal{O}(N * log(N))$$$, first for each i compute X[i] = biggest x such that $$$[i, i + x - 1]$$$ doesn't contain both 1s and 0, this can be done in O(n log n) using binary search and prefix sums, now in the loop above replace i += 1 by i = find(i, x) where find(i, x) returns the first j > i and X[j] >= x, this can be done using disjoint-set (initialize the parent[i] as first j > i with X[j] > X[i]) and modify the find function slightly

→ Reply

_chandler_

4 years ago, # |

+59

could E BE more boring ?

→ Reply

https://stackoverflow.com/questions/26532723/counting-all-contiguous-sub-arrays-given-sum-zero

4 years ago, # ^ |

Well，I think problem E is fine because I consolidated the segment tree from it._(:з」∠)_

→ Reply

omar208

4 years ago, # |

i see the answer for "C. Good Subarrays" in this content but i still can't understand it can any one help me?

→ Reply

sirearsh

4 years ago, # ^ |

← Rev. 3 →

if you just subtract 1 from all the elements, you will have little different array.

but now, you need to find all the subarrays with count 0.

Why?

ideal array with all subarrays with their sum = size of that subarray is 
1 1 1 1 ... 1 (up till n)
if you subtract 1 from all
now you have 
0 0 0 0 ... 0 (you can see the change it made right?)
now you need to find all the subarray with sum = 0.

here is how to deal with this problem from this perspective

→ Reply

Thallium54

4 years ago, # ^ |

$$$sum_r-sum_l=r-l \implies sum_r-r=sum_l-l$$$

→ Reply

Z0rr0_2

4 years ago, # |

← Rev. 2 →

→ Reply

axe98

4 years ago, # ^ |

Done

→ Reply

mkitkat

4 years ago, # |

In problem D why is it important to sort. . . . My thinking, If I'm using exhaustive search using dp, it should give the optimal answer, int this case max area, without even sorting. Please clarify this for me. Thanks

→ Reply

aniervs

4 years ago, # ^ |

← Rev. 3 →

Let's say we have two pairs of one type with lengths $$$a_1, a_2 (a_1 \le a_2)$$$, and two pairs of another type with lengths $$$b_1, b_2 (b_1 \le b_2)$$$, then it's optimal to create a rectangle of sides $$$a_2, b_2$$$ and a rectangle $$$a_1,b_1$$$. This is easy to prove.

So, after sorting once we pair $$$i$$$ on first array with $$$j$$$ on second array, we'll never pair $$$k < i$$$ on first array with $$$z > j$$$ on second array. So we keep a classic DP.

$$$dp[i][j][j]: $$$max total area using pairs till $$$i$$$ on first array, till $$$j$$$ on second array and till $$$k$$$ on third array.

→ Reply

bully....maguire

4 years ago, # ^ |

← Rev. 2 →

If I'm using exhaustive search using dp

No we are not doing exhaustive search , if we are pairing one from red and one from green , they must be of highest length in there category .

Did you asked yourself how transition will take place (i.e how we will find $$$dp[i][j][k]$$$ with the help of some lower $$$i,j,k$$$) ?

$$$dp[i][j][k] = max(dp[i-1][j-1][k]+A_i*A_j,dp[i][j-1][k-1]+A_j*A_k,dp[i-1][j][k-1]+A_i+A_k)$$$

while taking $$$A_i*A_j$$$ , we will take the maximum ones and thus we need to sort.

→ Reply

chowdhuryan1999

4 years ago, # |

Please provide a test case where Greedy approach in problem D fails

→ Reply

4 years ago, # ^ |

← Rev. 2 →

4 2 2
10 10 10 10
11 11
11 11

→ Reply

sourabh_jangid

4 years ago, # ^ |

← Rev. 2 →

Consider this test case: 2 2 2
5 5
4 4
3 3

→ Reply

wery0

4 years ago, # |

How to solve $$$G$$$ without bitsets? Faster than $$$O(X^2/32)$$$

→ Reply

tfg

4 years ago, # ^ |

+13

fft

→ Reply

wery0

4 years ago, # ^ |

Nice! Karatsuba also works.

→ Reply

V1S1T0R

4 years ago, # ^ |

Can you please explain your complete approach ?...

I know that if we have (a[i] — a[j] == t) for some i,j(i > j) and t then we can use an approach similar to sieve and solve... but not getting the fact what is the exact purpose of using fft ?

→ Reply

wery0

4 years ago, # ^ |

FFT can be used to get these values $$$t$$$. For this we should calculate $$$(x^{a_0} + x^{a_1} + ... + x^{a_N})*(x^{-a_0} + x^{-a_1} + ... + x^{-a_N})$$$. If coefficient at $$$x^{t}$$$ $$$!=0$$$, then there are exist $$$i$$$ and $$$j$$$ such that $$$a[i]-a[j]==t$$$.

→ Reply

nimom

4 years ago, # ^ |

How to solve G with bitset?

→ Reply

4 years ago, # |

Problem C becomes so beautiful after realizing its logic.

→ Reply

4 years ago, # ^ |

+36

One more solution to solve such types of problems.

Let $$$pref[i] = s[1] + s[2] ... + s[i]$$$

Thus required subarrays $$$(s[L...R])$$$ will follow this property,

$$$pref[R] - pref[L-1] = R-L+1$$$
$$$pref[R] - R = pref[L-1] - (L-1)$$$

Or, Basically you can choose any two index such that their $$$pref[i]-i$$$ is samefor both of them. Now, it's basic $$$O(N)$$$ task, using $$$C(freq, 2)$$$ for every frequency of $$$pref[i]-i$$$.

→ Reply

Rudro25

4 years ago, # ^ |

← Rev. 2 →

-10

[deleted]

→ Reply

MavrosOplarxigos

4 years ago, # |

I have submitted 2 identical solutions for problem C. Solution A: 89960181 Solution B: 89960214 The only difference between the two is on line 22: In one approach I use an integer to represent the index while in the other I use a long long. I also use in both cases a long long to represent an index in line 53.

Why does one solution pass while the other doesn't? I've already read many forums regarding the indexing on arrays in C++. Nowhere did I found that it says that a long long will cause problems when indexing with it.

→ Reply

iMurat

4 years ago, # ^ |

You didn't initialize variable out 89961488

→ Reply

MavrosOplarxigos

4 years ago, # ^ |

Thnx dude I mean I broke my head to figure it out. It is weird thought the fact that 89960214 gets AC. I mean I do not initialize out and because I used an integer for indexing it works for some reason XD

→ Reply

MubtasimShahriar

4 years ago, # |

-18

O(n) solution of C with HashMap 89943214

→ Reply

Trgt_2021_explosion

4 years ago, # |

why the greedy solution of D — "pick two largest pair every time" fails?

→ Reply

hopesanddreams

4 years ago, # ^ |

Counterexample:

R: 3 4 5

G: 5 6

B: 7

If you take 2 biggest elements of different colours you'll end up with: 7 * 6 + 5 * 5 = 67

Though the optimal split is: 7 * 5 + 6 * 4 + 5 * 3 = 35 + 24 + 15 = 74

→ Reply

spookywooky

4 years ago, # ^ |

9 9
10
10

-> That greedy pairs the both 10 instead of 9,10 + 9,10.

→ Reply

bully....maguire

4 years ago, # ^ |

spooky mah boi , why you oscillate between colors so much ?

→ Reply

spookywooky

4 years ago, # ^ |

The crazy problem setters create weird problems ;)

No seriously, one limitation for me is the ability to concentrate, I am sometimes not able to implement simple tasks, like todays C, even if I know how it works.

→ Reply

4 years ago, # ^ |

When you fell from CM to specialist, I just thought that you are trying to get a record of biggest rating change.
Yeah, problem setters set such problems that if you get some WA, debugging would take a lot of time. This affects me too.

→ Reply

Sportsman

4 years ago, # |

Why is my approach for C failing? My approach: Every good subarray should start with some index, so i'll brute force for every index checking it for lengths (1,2,...9) . Time complexity O(9*n). It failed for many, example => s = "11140000000090000000002111" , correct ans = 37 , my ans = 29

→ Reply

hopesanddreams

4 years ago, # ^ |

Consider an array full of 1's. In your solution you ignore good subarrays of length more than 9, which is not correct

→ Reply

gurharpartapdhaliwal

4 years ago, # |

in c i storedd arr[i]-1 for each array and counted the no of subarrays with sum 0 balancing excess with shortage!

→ Reply

sur.i.rus

4 years ago, # |

← Rev. 3 →

why my code for D is giving TLE. It is using same approach as DP solution.

code

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

#define rng(x) x.begin(), x.end()
#define pb push_back
#define f first
#define s second

typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<bool> vb;

/*-----------------------------Code begins----------------------------------*/


ll rgb(vl r, vl g, vl b){
    int z1=r.size(),z2=g.size(),z3=b.size();
    int cnt=0;
    if(z1==0){cnt++;}
    if(z2==0){cnt++;}
    if(z3==0){cnt++;}
    if(cnt>=2){return 0ll;}
    if(cnt==1){
        if(z1==0){
            ll y=g[z2-1],z=b[z3-1];
            g.pop_back(); b.pop_back();
            ll gb=y*z; return gb+rgb(r,g,b);
        }
        if(z2==0){
            ll x=r[z1-1],z=b[z3-1];
            r.pop_back(); b.pop_back();
            ll rb=x*z; return rb+rgb(r,g,b);
        }
        if(z3==0){
            ll x=r[z1-1],y=g[z2-1];
            r.pop_back(); g.pop_back();
            ll rg=x*y; return rg+rgb(r,g,b);
        }
    }
    ll x=r[z1-1],y=g[z2-1],z=b[z3-1];
    ll rg=x*y,gb=y*z,rb=x*z;
    ll lr=r[z1-1],lg=g[z2-1],lb=b[z3-1];
    r.pop_back(); g.pop_back();
    ll ans1=rg+rgb(r,g,b);
    r.push_back(lr); b.pop_back();
    ll ans2=gb+rgb(r,g,b);
    r.pop_back(); g.push_back(lg);
    ll ans3=rb+rgb(r,g,b);
    return max(ans1,max(ans2,ans3));
}

void solve(){
   int nr,ng,nb; cin>>nr>>ng>>nb;
   vl r(nr),g(ng),b(nb);
   for(int i=0; i<nr; i++){cin>>r[i];}
   for(int i=0; i<ng; i++){cin>>g[i];}
   for(int i=0; i<nb; i++){cin>>b[i];}
   sort(rng(r)); sort(rng(b)); sort(rng(g));
   ll ans=rgb(r,g,b);
   cout<<ans<<"\n";
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);  cout.tie(0);
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

→ Reply

hetp111

4 years ago, # ^ |

Close enough, but learn dp, you'll see why it fails.

→ Reply

sur.i.rus

4 years ago, # ^ |

← Rev. 2 →

i have tried to do DP problems but most of the times i fail to think of a DP solution

→ Reply

sare

4 years ago, # ^ |

I think rgb() is called for same vectors several times. It's same as when you find the nth element of Fibonacci sequence by iterative method or recursive method.

The other thing is that whenever you call rgb() it will copy all data from current vector to the next function but in DP no.

(Sorry for my bad English)

→ Reply

sur.i.rus

4 years ago, # ^ |

ok i will try to implement DP solution then. my bad i couldn't think of it during contest(sad emoji)

Spoiler

→ Reply

galen_colin

4 years ago, # |

+31

My screencast, if you want to enjoy my fingers suffering from typing so much (video solutions for A-E included)

→ Reply

divyamsingal01

4 years ago, # |

← Rev. 2 →

Why are the hacks shown on the hacking page in reverse order, like the most recent hack is at the end?

→ Reply

Barney_Stinson

4 years ago, # |

If anyone has used memoization for D pls do share your code.It would be a great help for a beginner like me as i am learning dp . Thanks in advance

→ Reply

Link to visual editorial here

4 years ago, # ^ |

Hope this helps https://codeforces.me/contest/1398/submission/89925922

→ Reply

we_are_267

4 years ago, # |

Got WA on Test 6 in Question D. The 6th test case given is not intuitive.Can anyone help me out with a intuitive test case similar to the test which is used in testing.My solution is a greedy approach, but not a general one.So test cases such as the below test case will result in correct answer.This is my solution 89953296.

4 2 2

3 3 3 3

4 4

This test case results in correct answer for my solution.

→ Reply

kakarotto_sama

4 years ago, # ^ |

← Rev. 3 →

3 3 3

2 8 5

1 10 5

9 9 3

Correct answer : 10*9 + 8*9 + 5*5 + 2*3 = 193

Your answer : 182

→ Reply

vagi

4 years ago, # |

I guess people are making fake ids just to hack those submissions afterwards. Deliberately a stupid if case is added to be hacked afterwards XD.

89940459

The hacked guy likes 78788 a lot I guess. One more of his solutions from another contest using his fake id Noob_is_back got hacked. See this 87193319 and you'll find 78788 again in the code. The hackers are still grey :)

→ Reply

hjcafaroUC

4 years ago, # |

My hack has been on "waiting" since this morning. It's not just when I'm logged in, it shows up like that on an incognito tab as well.

→ Reply

the_algorithmic_eye

4 years ago, # |

+16

In the meantime before editorial is published and for those interested, here is the 3Blue1Brown styled visual editorial for Problem C, visualizing tmwilliamlin168's code (89883985). I have also given a somewhat formal proof before visualizing 1st input of Test Case #5

→ Reply

4 years ago, # |

how to check the time it takes for the submission when hacking?

→ Reply

4 years ago, # |

← Rev. 2 →

-8

I love problem D very much!!

→ Reply

4 years ago, # ^ |

How to solve E?

→ Reply

4 years ago, # ^ |

I use the line segment tree (weighted segment tree). In fact, it is easy to find that the answer to problem E each line:ans = the sum of the largest number in the first K + the sum of all the numbers (here K refers to how many numbers can be doubled)

Then we read all the values first, sort them (discretize them), and then read the input of the problem again (which has been changed by array storage in advance)

We maintain the weighted line segment tree every time, that is, we ask the sum of the top k numbers in the 1-n interval every time. For example, to find the sum of the top 4 numbers, I will first ask whether the number of the right subtree (because the number stored on the right is larger than the number on the left) is less than 4. If so, enter it directly and return the sum of the top 4 numbers under the right subtree. If not, directly Select the sum of the prior numbers of the right subtree and add the sum of the first k = 4-num [RS] numbers under the left subtree (Num [RS] represents the first number of the right subtree),and then return it.

In short, the answer is to ask the sum of the top k numbers on the line segment tree and add the values of all the current numbers

(PS: but note that if the minimum value of all the numbers that can be doubled is greater than the maximum value of the number that can't be doubled, we can't simply choose the top k, but we should choose the top K + 1 and subtract the minimum value of the double number, because one can't double itself.)

→ Reply

4 years ago, # ^ |

Well, I am having tough time to understand this.

→ Reply

4 years ago, # ^ |

Maybe my expression is not clear, but you can find ideas from it. It must be feasible because I passed after the contest.

→ Reply

N_eB

4 years ago, # |

any news about the tutorial?

→ Reply

xyq0220

4 years ago, # |

why this code 89922404 for problem C won't get TLE

→ Reply

TheNR

4 years ago, # ^ |

The first three lines makes the code really fast.

→ Reply

ankushkhanna

4 years ago, # |

Why are Educational Rounds always so late with editorials?

→ Reply

TheNR

4 years ago, # ^ |

Because of the 12 hour open hacking phase, I guess.

→ Reply

udayan14

4 years ago, # |

Can someone help me in D. I used a 3d dp approach, which finds the maximum value using 6 cases. However, it failed on test 5. Here is the failed submission, while here is the one that passes. What does sorting do?

→ Reply

BumbleBee

4 years ago, # ^ |

← Rev. 2 →

It's always optimal to chose pairs with the maximum product. So we sort those three lists in decreasing order and take pairs from top of them. But when we have multiple options for pairs with the maximum product we don't know which one we should take without looking at the next values and that's why we do dp.

$$$dp_{i,j,k} = max(dp_{i,j+1,k+1},dp_{i+1,j+1,k},dp_{i+1,j,k+1})$$$ = maximum area we can achieve when we have already taken first $$$i$$$, $$$j$$$ and $$$k$$$ values of the first, second and third array (according to $$$0$$$ based indexing).

→ Reply

arpan_100

4 years ago, # ^ |

← Rev. 3 →

I found your explanation easy to understand, can you tell what does dp[i] [j] [k] stands for i.e what is the meaning of each cell of dp, can you please elaborate it more.

→ Reply

BumbleBee

4 years ago, # ^ |

$$$dp_{i,j,k}$$$ stands for the state where we have already used first $$$i$$$ values of first array, first $$$j$$$ values of second array and first $$$k$$$ values of third array.
The value of $$$dp_{i,j,k}$$$ is the maximum area we can obtain using remaining values of these three arrays in this situation.

→ Reply

walleeva

4 years ago, # |

← Rev. 2 →

If anyone need Explanation & implementation(not a video tutorial) for C Here

→ Reply

ScotchOnTheRocks

4 years ago, # |

Has the system testing finished? Its been more than 12 hrs right? Also editorial please...

→ Reply

ybw051114

4 years ago, # |

I think a coincidence has occurred. I write every problem's code by myself. Before Each code I wrote my name and time.

→ Reply

cuebits

4 years ago, # |

← Rev. 2 →

This wasn't a part of the problem, but I was wondering what is the maximum number of rectangles that can be formed for problem D?

My approach

Without loss of generality, assume $$$R$$$ is the biggest number, $$$G$$$ is the second biggest number and $$$B$$$ is the smallest number.

ans = min(G, ciel(R/2)) + min(B, floor(R/2))
G -= min(G, ciel(R/2))
B -= min(B, floor(R/2))
ans += min(G, B)

$$$ans$$$ is the required number.

Please correct me if I am wrong.

→ Reply

__FAILURE__

4 years ago, # |

← Rev. 2 →

Is there a bug in the rating change of this round? Everyone seems to be one step down to their original rank

Edit : it is correct now

→ Reply

dmdivyansh_113

4 years ago, # |

in D ,why do we have to sort the values,even though we are using dp?

→ Reply

navneet.h

4 years ago, # ^ |

Because it is not subset dp like knapsack, we are just using dp on the number of elements chosen for each color,and we will chose that greedily, its always to better to chose highest two elements, but the choice of elements could restrict choice of other elements, hence we are using dp.

→ Reply

naeem4265

4 years ago, # |

waiting for editorial..

→ Reply

yhf_2015

4 years ago, # |

← Rev. 2 →

Dear Codeforces administrators and contest organizers:

Just now, I received the following message:

Your solution 89920639 for the problem 1398D significantly coincides with solutions yhf_2015/89920639, zstuyyyycccbbb/89946825, Gghost/89949025.

First of all, I promise that the game was completed by myself alone. I did not listen to anyone else's thoughts during the game, nor did I reveal my thoughts to anyone. I have no intersection with the two who gave similar codes.

Secondly, my thinking about problem D is straightforward and simple. I think many people may have the same thinking. With a huge base, this may really be an accident.

I was very surprised when this happened, and I don't know what kind of evidence I need to provide to prove what I said above. (If you need me to provide any evidence, I will fully cooperate.) After completing the problem, I immediately carried out the research of problem E and wrote the code. Unfortunately, due to some errors, it was not possible within the game time Used.

Regarding my IP address, the network provided by my broadband network operator cannot access your site smoothly. I used a VPN system to compete through the lines of other operators. I don't know whether this will affect your judgment.

The above English uses machine translation.

→ Reply

lucifer1004

4 years ago, # |

← Rev. 2 →

+26

Chinese editorial

→ Reply

Karthee

4 years ago, # |

← Rev. 2 →

Nice contest with great set of questions worthy attending it

→ Reply

V1S1T0R

4 years ago, # |

Can anyone please explain why do we use FFT to get whether a value (a[i] — a[j] == t) for some i,j and t is possible or not ?

Asking this because if we can get all possible values of t from the array a.. then we can simply use sieve and solve but i am not getting the fact why do we use fft ?

→ Reply

lucifer1004

4 years ago, # ^ |

Brute force is $$$O(n^2)$$$, which is too slow.

→ Reply

thanhdatPT

4 years ago, # ^ |

Nice trick Haha, I love FFT (but I don't know how to implement :))

→ Reply

Hamelin

4 years ago, # |

Can Anyone please explain solution of 1398E - Two Types of Spells .There is no editorial and i cant think of any solution. or atleast give hint about data structure to use.

→ Reply

YJU

4 years ago, # ^ |

← Rev. 3 →

Segment tree and multiset are sufficient. assume there are L lightning spells, you just need to know the first L largest power of magic spells ... and some annoying implementation.

since all the powers are positive integers, you will always put the smallest lightning spell in the first position. then if there exists at least one fire spell, you can get L spells doubled. else you can only get L-1 spells doubled(since the last spell will be lightning spell).

sorry for poor English, I'm trying to improve it by answering questions.

→ Reply

vedang122

4 years ago, # |

← Rev. 2 →

I get it in Problem D we have to first sort before applying dp, but I sorted all three array in descending order ( just applying the logic that since we need bigger ones first) but I got WA.
Can someone please explain the difference ?
AC. WA. Only difference between two is the way of sorting.

→ Reply