Codeforces Round #627 (Div. 3)

5 years ago, # ^ |

Good luck and high rating <3

→ Reply

ShortestPath

5 years ago, # ^ |

Thank you so much <3

→ Reply

rishabh727

5 years ago, # |

-42

How was your Holi celebration ? Was anyone not able to play due to coronavirus threat?

→ Reply

rishabh727

5 years ago, # ^ |

So many downvotes :( . I haven't asked anything wrong :( .

→ Reply

mipmap42

5 years ago, # ^ |

+14

your question was right but on the wrong platform.

→ Reply

5 years ago, # |

2 hours in Div 3 and 4 hours in Reply Code Challenge, it's going to be an exhaustive day.

→ Reply

immortal_mark

5 years ago, # ^ |

I think you are highely inspired by TVF Pitchers.

→ Reply

5 years ago, # ^ |

True

→ Reply

5 years ago, # |

Hope that I can solve A-B-C.

Good luck guys <3

→ Reply

Thenextsuper-sun

5 years ago, # |

well，is there anyone know what's the name of the other contest（1.5hours later） after this contest？

→ Reply

S2speed

5 years ago, # ^ |

Reply code challenge : https://codeforces.net/blog/entry/74502

→ Reply

Thenextsuper-sun

5 years ago, # ^ |

Thank you so~much

→ Reply

S2speed

5 years ago, # ^ |

You're welcome

→ Reply

PolarFlea

5 years ago, # |

-6

Hope to become expert after this round

→ Reply

tzc_wk

5 years ago, # ^ |

+13

No, you won't

→ Reply

PolarFlea

5 years ago, # ^ |

← Rev. 2 →

Yes, I will.

→ Reply

5 years ago, # ^ |

I think ... He will :)

→ Reply

5 years ago, # ^ |

Would you like to share your secrets... with us :)

→ Reply

yui_chan

5 years ago, # |

I hope to get blue in this contest

→ Reply

KLNG7

5 years ago, # |

I don't think i can solve over two problems...

→ Reply

ya_hossein

5 years ago, # ^ |

if you think you can't, so you can't.

Believing in yourself is the first step to success.

→ Reply

5 years ago, # |

Hope problems will not be indirect like this

→ Reply

prakhar_111

5 years ago, # ^ |

Well, you can jump through the centre.

→ Reply

5 years ago, # ^ |

Ya I can for that I require wings of Advanced mathematics and data structures. Anyways Good Luck to everyone for the contest.

→ Reply

rony160136rr

5 years ago, # |

Bad luck for me becoz i can't attend this contest.

→ Reply

johnwick2b67

5 years ago, # |

← Rev. 3 →

→ Reply

Aesir

5 years ago, # |

Hope i will be green after this round :))

→ Reply

Sibin_Thomas

5 years ago, # ^ |

same

→ Reply

techfreakology

5 years ago, # |

I use this site during contest :)

→ Reply

xodeChemist

5 years ago, # ^ |

really that's i waited for

→ Reply

donutbyte

5 years ago, # |

+64

I got logged out 2-3 times during contest. Did it happen to anybody else or problem at my end?

→ Reply

shubhammitt

5 years ago, # ^ |

Same here :(

→ Reply

SugA

5 years ago, # ^ |

Glad to see I wasn't the only one who faced the same issue.
Made me wonder if my account got hacked or something :/

→ Reply

rish01

5 years ago, # ^ |

Yes,this happened with me also. Maybe a coincidence, but it happened mostly when I clicked submit button.

→ Reply

5 years ago, # ^ |

Me too. I thought it was my browser problem or something like that and erased cache and it happend again... :(

→ Reply

xodeChemist

5 years ago, # ^ |

Same to me ((

→ Reply

wasa855

5 years ago, # |

+17

I feel it difficult to understand some of the problem statements,does anyone feel the same?

→ Reply

PolarFlea

5 years ago, # ^ |

me!!!

→ Reply

shubhammitt

5 years ago, # ^ |

+11

Yes :/

→ Reply

3liAckerman

5 years ago, # ^ |

+11

me，especially problem a

→ Reply

Jamom

5 years ago, # ^ |

F too

→ Reply

5 years ago, # ^ |

statement of A was simple for those who played tetris before.

→ Reply

.anis.

5 years ago, # ^ |

+22

yeap, understanding Problem A was harder than solving it

→ Reply

5 years ago, # ^ |

Couldn't agree more

→ Reply

5 years ago, # ^ |

← Rev. 2 →

I took maximum time on A

→ Reply

123pow

5 years ago, # ^ |

problem E is difficult to understand

→ Reply

swapnil159

5 years ago, # ^ |

E was the most difficult to understand. I understood A maybe because I had played that game before.

→ Reply

madlogic

5 years ago, # ^ |

Exactly!

E was really confusing, in the examples they didn't even specify the mod h part

→ Reply

Vanilla_

5 years ago, # |

← Rev. 2 →

+23

A Done
B Done
C Done
Me Done
Nice Contest

→ Reply

aman__gupta__

5 years ago, # |

Good to see that vovuh is the writer.

→ Reply

Aesir

5 years ago, # |

← Rev. 2 →

The problems are too easy so that more than 500 participants solved all the problems

→ Reply

mycontest

5 years ago, # |

← Rev. 2 →

Guys,I have a problem! do not have a point of 1900 or higher in the rating Is that means standings in contest is different from your rank which is the final standings?

→ Reply

5 years ago, # ^ |

The contest will be rated for those participants who have a rating below 1600. However, participants with rating greater than or equal to 1600 can participate unofficially. Separate standings are available for official and unofficial+official participants.

→ Reply

mycontest

5 years ago, # ^ |

-8

I get it.Thanks!

→ Reply

5 years ago, # ^ |

You're welcome

→ Reply

nishant403

5 years ago, # |

+44

During the contest, I automatically got logged out from codeforces. I had two tabs of codeforces open in firefox. When I tried to submit I got to know I am not logged in. This has happened thrice. Is it normal/minor bug or there is some other problem ?

→ Reply

Brute_Forced

5 years ago, # ^ |

Even I faced this issue around 4-5 times.

→ Reply

5 years ago, # ^ |

I didn't count but it was infuriating.

→ Reply

5 years ago, # |

For those who cannot understand what is subgraph and subtree. Click :(

→ Reply

tmwilliamlin168

5 years ago, # |

+19

Screencast Explanations

→ Reply

SarthakBansal

5 years ago, # ^ |

Faster than Lightening! Thanks!

→ Reply

_kkhd

5 years ago, # ^ |

Thank you

→ Reply

ezdp

5 years ago, # ^ |

+39

→ Reply

5 years ago, # |

Thank you very much for the rating friendly contest

→ Reply

5 years ago, # |

← Rev. 9 →

How to solve D ;-;

My approach

Split array into negative-diff (A), positive-diff (B), zero-diff (C)

We have ai + aj > bi + bj 
<=> ai - bi > -(aj - bj)
<=> ci > -cj (where ck = diff(ak, bk) = ak - bk for all k E [1, n])
=> Count number of sum ci + cj > 0

Let res = |A| * (|A| - 1) / 2 + |A| * |C|
// sum of them is always >= 0
for i = 0 -> |A| - 1
-- while (j + 1 < |B| && B[j + 1] < A[i]) ++j
// move the pointer until the next element >= current
-- res = res + j
output << res

My source code

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
 
int main()
{
    int n;
    cin >> n;
 
    /// Count ai - bi > bj - aj // ci > -cj
    /// 0 3 -2 5 -1
    /// -2 -1
    /// 0 3 5
 
    vi a(n);
    for (int i = 0; i < n; ++i) { int x; cin >> x; a[i]  = x; }
    for (int i = 0; i < n; ++i) { int x; cin >> x; a[i] -= x; }
    
    int zero = 0;
    vi nega, posi;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] < 0)
            nega.push_back(a[i]);
        if (a[i] > 0)
            posi.push_back(a[i]);
        if (a[i] == 0)
            zero++;
    }
    nega.insert(nega.begin(), 0);
    int p = nega.size();
    int q = posi.size();
 
    sort(nega.begin(), nega.end(), greater<int>());
    sort(posi.begin(), posi.end(), less<int>());
 
    /*
    for (int i = 0; i < p; ++i) cout << nega[i] << ' '; cout << endl;
    for (int i = 0; i < q; ++i) cout << posi[i] << ' '; cout << endl;
    cout << endl;
    */
 
    if (posi.empty())
    {
        cout << 0;
        return 0;
    }
 
    if (posi.size() == n)
    {
        cout << 1LL * n * (n + 1) / 2;
        return 0;
    }
    
    ll res = q * (q - 1) / 2 + q * zero;
    for (int t = 0, i = 0, j = 0; i < q; ++i)
    {   
        while (j + 1 < p && -nega[j + 1] < posi[i]) ++j;
        res += j;
    }
    cout << res;
    return 0;
}

Found Mistake: (wrong formula) cout << 1LL * n * (n + 1) / 2; -> cout << 1LL * n * (n - 1) / 2; Found Mistake: (integer overflow) ll res = q * (q - 1) / 2 + q * zero; -> ll res = 1LL * q * (q - 1) / 2 + 1LL * q * zero;

AC Code (Spoiler warning)

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
 
int main()
{
    int n;
    cin >> n;
 
    /// Count ai - bi > bj - aj // ci > -cj
    /// 0 3 -2 5 -1
    /// -2 -1
    /// 0 3 5
 
    vi a(n);
    for (int i = 0; i < n; ++i) { int x; cin >> x; a[i]  = x; }
    for (int i = 0; i < n; ++i) { int x; cin >> x; a[i] -= x; }
    
    int zero = 0;
    vi nega, posi;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] < 0)
            nega.push_back(a[i]);
        if (a[i] > 0)
            posi.push_back(a[i]);
        if (a[i] == 0)
            zero++;
    }
    nega.insert(nega.begin(), 0);
    int p = nega.size();
    int q = posi.size();
 
    sort(nega.begin(), nega.end(), greater<int>());
    sort(posi.begin(), posi.end(), less<int>());
 
    /*
    for (int i = 0; i < p; ++i) cout << nega[i] << ' '; cout << endl;
    for (int i = 0; i < q; ++i) cout << posi[i] << ' '; cout << endl;
    cout << endl;
    */
 
    if (posi.empty())
    {
        cout << 0;
        return 0;
    }
 
    if (posi.size() == n)
    {
        cout << 1LL * n * (n - 1) / 2;
        return 0;
    }
    
    ll res = 1LL * q * (q - 1) / 2 + 1LL * q * zero;
    for (int t = 0, i = 0, j = 0; i < q; ++i)
    {   
        while (j + 1 < p && -nega[j + 1] < posi[i]) ++j;
        res += j;
    }
    cout << res;
    return 0;
}

→ Reply

5 years ago, # ^ |

You can use binary search. create a diff array such that diff[i] = teacher[i]-student[i]. sort this array. at a particular point i calculate how much you'll need to compensate for when you choose j. e.g if teacher[i]-student[i] = -2. then we know we need diff[j] >= 3, so as to make teacher[i]+teacher[j] > student[i] + student[j].

you can easily binary search this value in diff array.

→ Reply

tanuj_jain

5 years ago, # ^ |

I had the same logic, but failed somewhere in implementation i guess. Did you get AC with this logic?

→ Reply

5 years ago, # ^ |

Yup ... I had the same logic... ACed

→ Reply

garg_vibhor

5 years ago, # ^ |

I have implemented same logic in java but getting TLE in 24 testcase. but it is taking nlog(n) time. Your text to link here...

→ Reply

5 years ago, # ^ |

Change your int c[] to Integer c[] My submission of your code: 73104414

→ Reply

5 years ago, # ^ |

Let $$$c_i = a_i - b_i$$$. Now you have to count the number of pairs of $$$c_i$$$ with the positive sum. It can be done in $$$O(n log n)$$$ with binary search.

→ Reply

5 years ago, # ^ |

Can I ask why my approach failed ? T_T

→ Reply

_paryatak_

5 years ago, # ^ |

Create an array of differences of a[i]-b[i] then use lower bound to find good pairs for negative numbers and zero numbers and for positive use binomial coefficient (ncr).

→ Reply

5 years ago, # ^ |

What formula should I use ?

→ Reply

5 years ago, # ^ |

+10

I used PBDS.

→ Reply

5 years ago, # ^ |

how?

→ Reply

5 years ago, # ^ |

Let's just iterate over the array from the start, and since we need to find unordered pairs, so for a particular i, we need all elements before it such that: ai — bi > bj — aj or Let's denote bj — aj as val, then we need all such elements where : val < ai — bi So PBDS on pair of elements acts like a multiset with additional feature ,giving count of elements less than x too.So use that function for each i and get count of elements less than {ai-bi-1,inf}, and add it to answer and insert pair {bi-ai,i} to the pbds.

→ Reply

5 years ago, # ^ |

Use PBDS as a multiset (comparator less_equal). Traverse from the end of the array and for each index, increment answer by order_of_key of $$$a[i]-b[i]$$$ (basically index of upper bound). Then insert $$$b[i]-a[i]$$$ in the PBDS.

→ Reply

A_Le_K

5 years ago, # ^ |

Yes, yes, yes, shooting pigeons with a cannon — that's my style! 73043201

→ Reply

ezdp

5 years ago, # ^ |

Can you share your code? I tried using pbds, but it gave wa on test 6.

→ Reply

5 years ago, # ^ |

You can look it up in my submissions and if are not permitted, then add me as a friend and then look it up in standings submission. Sharing code here will scribble the comment section.

→ Reply

5 years ago, # ^ |

It can also be done with sorting; if you have a sorted array $$$c$$$ and you want to know for particular $$$i$$$, how many $$$j$$$ satisfy $$$c[i]+c[j]>0$$$, then you can decrement $$$j$$$ from $$$n$$$ down to the first index where $$$c[i]-c[j]<=0$$$, and count $$$n-j$$$. Then if you iterate over increasing $$$i$$$, this $$$j$$$ can only decrease.

→ Reply

5 years ago, # ^ |

What is wrong with my approach ? ;-;

→ Reply

rupav

5 years ago, # ^ |

problem is similar to inversion count, so used BIT tree to solve it, after compression.

→ Reply

Brodicico

5 years ago, # ^ |

← Rev. 2 →

I'm glad i'm not the only one who used BIT :)))))

→ Reply

5 years ago, # ^ |

← Rev. 4 →

Let c[i] = a[i] — b[i]. Now we have to count the number of pairs with positive sum. Sort array c.

Set two pointers, one at index 0 (pointer j) and the other at index n-1 (pointer k). In each iteration decrease k by 1 and find the corresponding index j, by running a separate loop within the previous loop. Exit when j >= k.

Initialize ans = 0, and keep adding (k — j) in each iteration, i.e. ans += k — j

Note that j keeps on increasing in each iteration. We do not restart j from 0 each time.

Time Complexity: O(n)

→ Reply

tissue_eater64

5 years ago, # ^ |

thanks for taking your time to write an explanation.

→ Reply

5 years ago, # ^ |

Thanks for saying that <3

→ Reply

5 years ago, # |

Can any one give a hack on the following approach for D?

Sort them by $$$a_i-b_i$$$, then use binary search to find last okay one.

→ Reply

nonstopfor

5 years ago, # ^ |

Gradually sort?

→ Reply

5 years ago, # ^ |

Can you explain it further please?

→ Reply

nonstopfor

5 years ago, # ^ |

I think simply sort will TLE. What's your method?

→ Reply

5 years ago, # ^ |

Pasting my code here: (ignore the stable sort part, using sort fails also) Link

→ Reply

nonstopfor

5 years ago, # ^ |

We need ai-bi+aj-bj>0 instead of ai-bi>aj-bj

→ Reply

It_Wasnt_Me

5 years ago, # ^ |

sorting them will change the order of the indices

and in the problem you need $$$j$$$ to be $$$>$$$ $$$i$$$

→ Reply

5 years ago, # ^ |

← Rev. 2 →

That doesn't matter, if you are counting all distinct pairs $$$(i,j)$$$ which satisfy some property, then this will equal the number of distinct pairs $$$(\sigma(i),\sigma(j))$$$ which satisfy the same property, for any permutation $$$\sigma$$$

→ Reply

uux

5 years ago, # ^ |

Make an array of Ai — Bi, sort it and binary search the right one for each. That's the solution I think.

→ Reply

5 years ago, # ^ |

Maybe you can use the Binary Indexed Tree in value.

First discrete all $$$a_i - b_i$$$ and $$$b_i - a_i$$$.

Then for every $$$i \in [2, n]$$$, calculate all for $$$j \in [1, i)$$$ which $$$b_j - a_j < a_i - b_i$$$

The time complexity will be $$$O(n \log n)$$$.

→ Reply

T-REXX

5 years ago, # |

-7

Lightning-fast system testing

→ Reply

5 years ago, # ^ |

There is a 12 hr hacking phase, after which system testing will begin.

→ Reply

forget_it

5 years ago, # |

+11

Why, i kept logging out after few intervals ,throughout the contest??

→ Reply

Icewill

5 years ago, # ^ |

Me too!

→ Reply

lone-_-wolf

5 years ago, # ^ |

Same here

→ Reply

5 years ago, # ^ |

Same here !

→ Reply

5 years ago, # |

How to solve E? Also, what is the name of the concept used in E?

→ Reply

5 years ago, # ^ |

+13

I believe it's called dynamic programming.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Dynamic programming. $$$dp_{i, j}$$$ is the number of good times when we consider the first $$$i$$$ times ($$$0$$$-indexed) and did this $$$-1$$$ "operation" $$$j$$$ times. The answer is $$$\max\limits_{j=0}^{n} dp_n$$$.

→ Reply

Fishdeer

5 years ago, # ^ |

what's the meaning of the first $$$i$$$ times，I can't get it

→ Reply

5 years ago, # ^ |

More correctly, $$$dp_{i, j}$$$ is the number of "good times" when we consider first $$$i$$$ values $$$a_i$$$ and used $$$-1$$$ $$$j$$$ times. Transitions are also pretty easy: if the sum of the first $$$i$$$ values $$$a_i$$$ is $$$s$$$ then $$$dp_{i + 1, j} = max(dp_{i + 1, j}, dp_{i, j} + [(s - j) \% h \in [l; r]])$$$ and $$$dp_{i + 1, j + 1} = max(dp_{i + 1, j + 1}, dp_{i, j} + [(s - j - 1) \% h \in [l; r]])$$$. $$$\%$$$ is modulo operation ofc.

→ Reply

5 years ago, # ^ |

state are index and modulo

→ Reply

5 years ago, # ^ |

Submission:73073024

→ Reply

lone-_-wolf

5 years ago, # |

-7

in problem D , solution of 10^10 was giving TLE for test case 12,althought time limit was 2 seconds, http://codeforces.net/contest/1324/submission/73076815 i thought 10^10 solutions can run in 2 sec

→ Reply

5 years ago, # ^ |

I think a bound of 10^(7-8) is good for 2 secs, 10^10 is taking it too far.

→ Reply

akiradeveloper

5 years ago, # |

+19

Downvoted because the sentence in problem E is completely unreadable.

The sentence "The i-th time he will sleep exactly after ai hours from the time he woke up" and "Vova can control himself and before the i-th time can choose between two options: go to sleep after ai hours or after ai−1 hours." sounds inconsistent.

→ Reply

5 years ago, # |

← Rev. 2 →

for problem D, i Stored two arrays one array has (ai-bi) values and the other has (bi-ai) values and i ran a nested loop from i to n-1 & j=i+1 to n-1 and counted the number of elements that are greater than current element. what could i have done better?

→ Reply

5 years ago, # ^ |

In fact, you can first discrete all $$$a_i - b_i$$$ and $$$b_i - a_i$$$.

Then use a Binary Indexed Tree to count all the values.

The time complexity will be $$$O(n \log n)$$$.

→ Reply

OrientalHorizon

5 years ago, # ^ |

Use a binary indexed tree.

Insert $$$a_i - b_i$$$ into it after checking how many elements there are before $$$i$$$ which satisfies $$$a_j - b_j > b_i - a_i$$$. Discrete all $$$a_i - b_i$$$ and $$$b_i - a_i$$$ first thing first.

→ Reply

5 years ago, # |

← Rev. 2 →

-31

UPD: Sorry for the comment. I didn't think much, it's my bad.

Appologize for the round, sorry.

→ Reply

5 years ago, # ^ |

+18

Do you write is serious? The "subSTRING" problem, as you say, is not "more interesting" and can be solved in $$$O(n)$$$ considering $$$3$$$ or $$$4$$$ consecutive characters.

D — data structure problem? The problem "sort the array and do (lower bound or binary search)" is data structure problem?

→ Reply

5 years ago, # ^ |

+13

Sorry for that. I didn't think too much.

I am terribly sorry for the words.

→ Reply

OrientalHorizon

5 years ago, # ^ |

How to "sort the array and do (lower bound or binary search)"?

It seems very interesting.

I used binary indexed tree after discretion.

→ Reply

5 years ago, # ^ |

See this

→ Reply

uux

5 years ago, # ^ |

Can't the substring problem be solved in O(N)?, I did that only after I misread the problem! :( Just check all "3 consecutive characters substring" and "4 consecutive characters substring".

→ Reply

5 years ago, # |

Interesting fact for myself: Everytime people celebrate a rating-friendly contest, I lose ratings; Everytime people complain about toxic problems, I gain ratings.

→ Reply

5 years ago, # |

You did not think that the tasks are too simple even for div 3 ?)

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Speed is really need. lol

→ Reply

Bhj2001

5 years ago, # ^ |

-26

vovuh made them easy to please div3 ppl

here

→ Reply

5 years ago, # ^ |

+64

Haha, that's funny. I don't know how to prepare "good" round. I prepare slightly hard round, people say "omg that's div.1, not div.3!". I prepare slightly easy round, people say "loool 2ez4me that was not even a round". I don't know what to do.

→ Reply

5 years ago, # ^ |

+62

Lol. You should ignore comments made by candidate masters on div3 rounds. A candidate master saying div3 is easy is like a pupil / grey guy saying div1 is hard.

→ Reply

5 years ago, # ^ |

+20

actually, vovuh, you did well, i really appreciate as most of div.3 contests are made of you

→ Reply

5 years ago, # ^ |

-62

Don't coordinate anymore divs 3 rounds )

→ Reply

5 years ago, # ^ |

← Rev. 2 →

+45

Yea, yea, I remembered you. You wrote the same about awoo. That's all I need to know.

→ Reply

5 years ago, # ^ |

-13

axaxaxxa

→ Reply

5 years ago, # ^ |

+19

→ Reply

5 years ago, # ^ |

You look like Radewoosh

→ Reply

5 years ago, # ^ |

I'm his brother

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Blue blood in ICPC?

→ Reply

eugalt

5 years ago, # ^ |

Twin brother.

→ Reply

5 years ago, # ^ |

who knows who knows

→ Reply

5 years ago, # ^ |

+24

Actually, vovuh, you are the best. You prepare quality Div 3 contests, and I enjoy participating in your contests. Also, I participating out of the contest; I get to learn new concepts and techniques from your contests. I hope you keep up this great work and keep contributing to more such awesome contests.

→ Reply

ezdp

5 years ago, # ^ |

I really liked D problem of this contest. I've been focusing on pbds/fenwick last 2 weeks and this problem really put my knowledge to test. I like how I saw 3 different approaches on this problem(bin search, pbds, fenwick and treap). The problem really managed to capture the creativity of the community. Well done, our Div.3 King

→ Reply

sh_maestro

5 years ago, # ^ |

← Rev. 2 →

Great job vovuh, don't give in to the hate. As it is, it's hard and time consuming to create problems and test cases, let alone deal with criticism such as this.

Personally, I think this is a good level of difficulty, otherwise how do we differentiate between Div 2 and Div 3 problems. Once in a while, problems in Div 3 are easier compared to other Div 3 contests — but I think many people in Div 2/Div 3 enjoy the opportunity to solve a few problems (that are in reach and where we can apply what we've learnt recently) and then learn from the other unsolved problems.

→ Reply

5 years ago, # ^ |

I think that this is the perfect difficulty level for Div 3. Myself being an Expert (Rating: 1734), I was only able to solve A, B, C, D. So, I believe that it justifies my claim.

→ Reply

5 years ago, # |

+13

Speedforces

→ Reply

MubtasimShahriar

5 years ago, # |

Tried E for the first time in my life. Got wrong answer test 40! I think I made a silly mistake but couldn't figure out yet. My submission: 73079617

→ Reply

rupav

5 years ago, # ^ |

It failed for me as well, test case is involving l = 0 I guesss, and I had counted t = 0 case, which is wrong. Removing that gave me AC.

→ Reply

5 years ago, # |

← Rev. 2 →

Why these two submissions using PBDS for problem D got different verdicts vovuh please look into the matter.

Correct SOlution:-73082017 Rejected Submission:-73079109

→ Reply

TselmegKh

5 years ago, # ^ |

It's because, in your case, it couldn't contain same elements.

→ Reply

5 years ago, # ^ |

thank you for reply oh I got that it is property of sets

→ Reply

5 years ago, # |

During contest I was logged out several times. Does someone know why?

→ Reply

5 years ago, # |

It's quite easy. Even my i got more rating, but i think i wouldn't satisfy with those.

→ Reply

axe98

5 years ago, # |

Why I am getting ILLEGAL CONTEST error while pushing "hack it"? Please fix

→ Reply

5 years ago, # ^ |

you must go to submission link and then press hack it there instead of hack from status

→ Reply

axe98

5 years ago, # ^ |

TY. It works

→ Reply

5 years ago, # |

← Rev. 3 →

Hello? I'm a bit curious about how to solve F, can someone help me? Thanks

→ Reply

johnwick690

5 years ago, # |

can someone please explain the reason for TLE in my submission of E my code -link

→ Reply

gamer37

5 years ago, # ^ |

Because at last where you have done dp[id][sum][f]=ans, your value of sum is changed, but your dp[id][sum][f] should use original value of sum not the updated one.

→ Reply

5 years ago, # |

1 5 2 2 2 2 4 why this will give yes in A?

→ Reply

rupav

5 years ago, # ^ |

NO, since all elements must have same parity (either odd or even), then only answer can be "YES"

→ Reply

5 years ago, # ^ |

can you show the steps?

→ Reply

ashkANOn

5 years ago, # ^ |

Add 2 with each 2 then reduce 1 by 1 in 4 steps

→ Reply

dapingguo8

5 years ago, # ^ |

Is it a full test or a single case? If it is a full test(i.e. 1 represents number of cases,5 represents number of columns) then simply put blocks in column 1-4 If it is a case(i.e. there are 7 columns),the answer is NO.

→ Reply

5 years ago, # |

+104 -> +8, thx for B pretests, goodbye expert:(

→ Reply

5 years ago, # ^ |

exactly same problem.... :/ why would they create such weak tests?

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Actually, it means we should be more careful, and find out all special cases.

→ Reply

5 years ago, # ^ |

the thing is , the hacks arent even special cases, the hack could have easily been in the example test.

→ Reply

5 years ago, # ^ |

If you didn't consider something, for you it was a special case I suppose.

→ Reply

5 years ago, # ^ |

how did you figure out your rating change?

→ Reply

5 years ago, # ^ |

Chrome extension "CF-predictor"

→ Reply

5 years ago, # ^ |

Oh thanks. I can't see the prediction, I guess I was supposed to have it before the contest too?

→ Reply

5 years ago, # ^ |

Sorry, I don't know.

→ Reply

A_man909

5 years ago, # |

Hack for B?

→ Reply

5 years ago, # ^ |

← Rev. 2 →

1
3
1 1 1

→ Reply

MhD88

5 years ago, # |

← Rev. 3 →

!!NEED HELP!!

My solution for problem-D : 73076688

According to me,it's complexity nlogn, but i m getting time limit. Can anyone explain why it is happening or where m i wrong??

TIA

→ Reply

5 years ago, # ^ |

sum+=(ll)distance(it,ms.end()); has linear complexity -> O(n^2logn)

→ Reply

CodAR

5 years ago, # ^ |

If I hack my own solution, then will that be an advantage?? like my scores would not reduce

→ Reply

5 years ago, # ^ |

No, you'll just hack your own solution instead of someone else.

→ Reply

5 years ago, # ^ |

Seppuku, the honourable way.

→ Reply

5 years ago, # ^ |

So, I made that:)

→ Reply

5 years ago, # |

quite sad that my solution for B got accepted in the first place , was it intentional to make the test cases all weak for only an odd length palindrome / 2 different numbers only? would've solved 5 problems in one contest for the first time.

→ Reply

k_8

5 years ago, # |

Hi, can anyone explain why this solution 73084554 is giving WA. While this solution works 73037149 by tmwilliamlin168. Thanks in Advance!

→ Reply

PouyaNavid

5 years ago, # |

← Rev. 5 →

Problem B $$$O(N)$$$

73087070

→ Reply

5 years ago, # |

I liked this contest vovuh. Good job. I'm interested to know your thoughts on the difficulty levels of $$$D$$$ and $$$E$$$ if this was a Div $$$2$$$ contest. Do you think $$$D$$$ is harder than $$$E$$$ ?

How to solve $$$F$$$ ?

→ Reply

5 years ago, # ^ |

I think D is between the div2B and the div2C, while E is between the div2C and the div2D.

However, you may just wait until when these problems are recorded in PROBLEMSET and the difficulty of them will be visble for you.

→ Reply

5 years ago, # ^ |

I think segment trees are too difficult to be asked for $$$B$$$. It might be a $$$C$$$.

Can you please tell me how to solve $$$F$$$ ?

→ Reply

5 years ago, # ^ |

In fact, you don't need segment tree for D since the binary search is enough for it.

For problem F, I apply DFS twice on the trees.

In the first DFS, I regarded no.1 node as root and regarded the trees as a rooted trees. In this DFS, I get the correct answer for no.1 node.

In the second DFS, I started my DFS from no.1 node and calculated the answer of other nodes in my traversal.

For more details ( since I'm poor in English but good at C++ ), you can look up my code.

→ Reply

5 years ago, # ^ |

Nice ! I never thought of binary search for counting inversions ! :)

My main doubt was in the second DFS. Thanks !

→ Reply

NerfThis

5 years ago, # ^ |

I implemented the same algorithm in Java, but failed test case 3. I couldn't figure out why it fails. Can you help me? My submission is: 73110580

→ Reply

5 years ago, # ^ |

It seems like ts3 is just a random tree whose node is all black. So you can just make a small test to see what happens in your program.

→ Reply

NerfThis

5 years ago, # ^ |

My tree building logic was wrong, I need to build a 0-rooted tree recursively, thanks anyway!

→ Reply

limabeans

5 years ago, # ^ |

← Rev. 2 →

Root the tree arbitrarily and let $$$dp_x$$$ be the answer for $$$x$$$'s subtree. We can do this with a single dfs.

But then $$$dp_x$$$ won't necessarily have its full answer (because we didn't consider the path through $$$x$$$'s parent). So do a second dfs and for each parent node $$$y$$$ update each of $$$y$$$'s child's $$$dp$$$, (child may benefit from path via their parent $$$y$$$), but be careful to not to over count that child's contribution from $$$dp_y$$$.

for clarity you can see my submission: 73067648

→ Reply

https://codeforces.net/contest/1324/submission/73078402

5 years ago, # ^ |

Ah ! The overcounting is tricky ! We should subtract only if $$$f(c) > 0$$$. The reason is that if $$$f(c) > 0$$$, then we never added $$$f(c)$$$ to $$$f(v)$$$

Thanks !

→ Reply

Hisham_hates_graphs

5 years ago, # |

← Rev. 2 →

it is the first time i tried in E

but i got WA on 40

any one can help me why it is wrong

→ Reply

Kavit_Kheni

5 years ago, # ^ |

Corner Case:

1 3 0 0 1

You miss this case.

→ Reply

Vaidik_Patel_27

5 years ago, # ^ |

yo boy!

→ Reply

5 years ago, # |

→ Reply

Jass_Manak

5 years ago, # |

Can someone please explain to me the DP state for problem E?

→ Reply

5 years ago, # ^ |

Before considering sleeps #$$$i,i+1,\ldots,n$$$, suppose you last slept at time t. Then under these conditions, dp[i][t] is the maximum number of good sleeps among $$$i,i+1,\ldots,n$$$. The question asks to find dp[1][0].

→ Reply

elements

5 years ago, # |

Can B be solved in O($$$n^2$$$) will it pass?

→ Reply

5 years ago, # ^ |

i think. YES, as n=5000

→ Reply

limabeans

5 years ago, # ^ |

Yes, but if you have a constant factor $$$a$$$ you will have runtime $$$O(a * n^2)$$$, which may TLE because worst case scenario you will do something like $$$a * 5000 * 5000$$$ operations which may not be executed in time (I hacked a couple ppl with this idea)

→ Reply

rahulpkvij

5 years ago, # |

Can someone explain why the order (i<j) won't matter in problem D ??

→ Reply

5 years ago, # ^ |

i<j simply means that pair (i,j) and (j,i) are same. so you can ignore this statement and divide it by 2 at last to consider it only once.

→ Reply

elements

5 years ago, # ^ |

It is another way of telling that pairs (i,j) and (j,i) are the same. And they have to be counted as 1.

→ Reply

2022OVO

5 years ago, # |

← Rev. 2 →

Is problem F a classic problem? Because i notice that many people write similar code in their dfs. If it is, please tell me. Thanks is advance :)

→ Reply

5 years ago, # ^ |

i think you are talking about F

→ Reply

2022OVO

5 years ago, # ^ |

Thanks! fixed now.

→ Reply

5 years ago, # ^ |

i think because its straight forward.

→ Reply

5 years ago, # ^ |

Yes it's a classic problem based on dp on trees. You can refer to rachitiitr youtube videos regarding in-out dp.

→ Reply

iprakhar22

5 years ago, # ^ |

Can you provide the link please :)

→ Reply

_PickleRick_

5 years ago, # ^ |

Can you suggest links for rerooting technique and in-out dp?

→ Reply

5 years ago, # |

Could someone help me figure out my mistake in Problem E 73091842. Thanks in advance.

→ Reply

beginner1010

5 years ago, # ^ |

It's because you don't take maximum of dp[i][j]s any where in your for loops.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

→ Reply

5 years ago, # |

vovuh you are great author your problems are amazing

→ Reply

5 years ago, # |

Hack case of B . 1 3 2 2 2

→ Reply

5 years ago, # |

← Rev. 3 →

how is this O(n^2) solution timing out on B for 2 secs??.Link

→ Reply

5 years ago, # ^ |

It seems like you are using map<int, int> which takes $$$O(\log n)$$$ time for adding and looking for element. Also, std::map is especially slow (big constant factor) so your solution has time complexity $$$O(n^2 \log n)$$$ with big constant factor.

→ Reply

5 years ago, # ^ |

Ah, wow. i always thought map was constant access and insertion. thanks btw

→ Reply

5 years ago, # ^ |

I think what you want is unordered map which uses hash. It has constant access time on average (but can be up to $$$O(n)$$$ worst case). It also is quite slow since internal structure is somewhat complicated. I mean, don't expect something like a array-access speed.

Also, since it uses random, it can be hacked if some experienced coder tries to craft specific testcase to kill unordered map.

I think there was a good blog on CF about this (and also how not to get hacked from that) but I can't find it now.

→ Reply

5 years ago, # ^ |

Neat info thanks. i guess using a boolean array in this case would have been better. my loss

→ Reply

coderanant

5 years ago, # ^ |

You might be talking about this.

→ Reply

Jamom

5 years ago, # ^ |

coderanant orz

→ Reply

towrist

5 years ago, # ^ |

So this should time out too? 73028508

→ Reply

5 years ago, # ^ |

I don't think so. Your code is performing $$$n$$$ map access operations which make the whole complexity like $$$n \log n$$$. The code originally asked was using about $$$n^2$$$ map access.

→ Reply

towrist

5 years ago, # ^ |

← Rev. 2 →

Thanks. I was misinformed about the access time of maps, now its clear.

→ Reply

5 years ago, # ^ |

I think map takes O(log n) time for searching thus complexity goes to O(n^2logn)

→ Reply

AhmadEbtihal

5 years ago, # |

+15

When it's my first time to solve 4 problems and I've a new high rank:

HACKS:

→ Reply

nagabhushan

5 years ago, # |

Nice Contest! My solutions: A. Check the parity of all elements. If the parity is same, then the answer is YES, else NO B. Its always enough to check for palindrome sequences of length 3. So considering each element as center, check if the right and left parts contain atleast 1 element in common. C. its always beneficial to use R and not L. (why? bcoz with L you can only reach back to reach some R, which anyway you would have reached before reach the cell with L). so find the largest gap in reaching a R. D. Compute ci = bi-ai and sort this array. Then for each ai and bi count the number of elements in array c less than ai-bi. Also make sure to consider the edge cases where you have counted the same element again. E. Use dp. The state is (i, time), where i is the day (or the ith sleep) and time is the current time. Write transitions to each of ai and ai-1. F. Assuming you run bfs from some initial root node, Compute max(wi-bi) for each node i in its subtree rooted at i. Now we need to compute the value in parent part. This can be done using tree rerooting technique.

→ Reply

5 years ago, # |

Could someone help me with my problem E submission. I am not able to figure out the mistake.Thanks in advance[submission:73096035]

→ Reply

De_sl

5 years ago, # ^ |

Corrected code 73127806

Explanation

→ Reply

5 years ago, # ^ |

Thanks

→ Reply

Aditya_13

5 years ago, # |

Can anyone tell me why this 73097950 passes and this 73098017 does not ?

→ Reply

5 years ago, # ^ |

← Rev. 3 →

they will give different output when v contain same value more than once.Check this 3 6 6 6 2 2 2

→ Reply

kk_ban

5 years ago, # |

+20

![ ]()

→ Reply

anupamshah_

5 years ago, # ^ |

← Rev. 2 →

Edit: now i know that these are the number of hacks.

→ Reply

5 years ago, # |

← Rev. 2 →

I got TLE error during contest instead of WA! even after the contest when I was submitting correct answer I was getting TLE. I got frustrated and then copy pasted solution of another user then also I got TLE. Also, I was logged out multiple times automatically during the contest!! solution link: https://codeforces.net/contest/1324/submission/73104474

→ Reply

ManavJ07

5 years ago, # ^ |

use pypy 3 instead of python 3 as your language on codeforces.

→ Reply

5 years ago, # ^ |

It worked, thanks for the help! do you know reason/line where its failing in python3.7?

→ Reply

EnMinGW32

5 years ago, # ^ |

There are answers in stackoverflow.com

→ Reply

5 years ago, # ^ |

I am getting error in 6th problem too, for 36th test case!

can you help me in that too? https://codeforces.net/contest/1324/submission/74307112

→ Reply

CodAR

5 years ago, # |

Will there be any system testing after the hacking round is finished??

→ Reply

dapingguo8

5 years ago, # ^ |

← Rev. 2 →

Yes

All of the AC solutions will be rejudged with original tests and successful hacks once the hacking phase is over.

→ Reply

syh0313

5 years ago, # |

Why I want to hack a solution and it shows Illegal contest ID ？

→ Reply

dapingguo8

5 years ago, # ^ |

Try to hack solutions via the Status page instead of the Standing Page

→ Reply

syh0313

5 years ago, # ^ |

Ok I get it. Appreciating your help !

→ Reply

Eclipse_Hunter

5 years ago, # |

Can Somebody please explain why this solution is not giving compile time error on pretest cases and arbitrary cases on offline compiler Solution for Problem 2

→ Reply

126378

5 years ago, # |

+14

When system test will start?

→ Reply

persistent

5 years ago, # |

What's wrong with my solution for E problem? 73075794

→ Reply

Aehnuwx

5 years ago, # |

I am wonder that when the system test will begin.

→ Reply

supriya14

5 years ago, # |

Anyone who solved problem D using two pointers? Please explain your approach

→ Reply

masaow

5 years ago, # |

Why did it keep on logging out during the entire contest? It was so irritating whenever I was to submit my solution It logged out :(

→ Reply

towrist

5 years ago, # |

Each time Vova sleeps exactly one day (in other words, h hours).

What a lousy problem statement for E.

→ Reply

5 years ago, # |

When will the ratings change?

→ Reply

kartel

5 years ago, # |

+11

I have a solution on F that seems to be different from everyone: Let's hang the tree at vertex 1 and calculate dp[v] — the maximum answer for the subtree of v. This DP solves the problem for the vertex v if the root is the vertex v. How do we fix this? Let us remember when recalculating the DP for root 1 which vertices we included in the answer. Then we’ll introduce a push push that will push dp[v] into dp[u] depending on the benefits. That is, if our vertex u was included in the answer, then we push dp[u] = max(dp[u], dp[v]) into it, otherwise dp[u] = max(dp[u], dp[u] + dp[v]) The answer for vertex v is dp[v]

→ Reply

5 years ago, # ^ |

I did this too (submission towards the bottom) but I think it is more or less the same as everyone else. It just condensed the if/else that others used into a smaller form.

→ Reply

kartel

5 years ago, # ^ |

+11

I do not completely agree, because the majority (70-90%) passed the "resuspension" technique for O (1)

→ Reply

5 years ago, # |

When will the rating be changed?

→ Reply

EnMinGW32

5 years ago, # ^ |

You need to wait for system test first.

→ Reply

5 years ago, # ^ |

But Hasn't the system test finished?

→ Reply

5 years ago, # ^ |

I think so as it says final standings.

→ Reply

5 years ago, # ^ |

But all the finished matches said final standings.

→ Reply

EnMinGW32

5 years ago, # ^ |

You can check the submissions' judge time in standings page to see whether the system test have done or not.

→ Reply

maximus_maximus_maximus

5 years ago, # |

I kept getting logged out of my account. Did this happen to anyone else ? Why did it occur ?

→ Reply

TheRedLegend

5 years ago, # ^ |

Yes, it happens to me regularly, even during the contest I had to log in 3 or 4 times.

→ Reply

kishan2101999

5 years ago, # ^ |

I had same problem during contest...

→ Reply

1a2a3a

5 years ago, # |

Is it rated?

→ Reply

5 years ago, # ^ |

I think it's rated. If it isn't rated, they will declare it.

→ Reply

5 years ago, # |

Is the system testing done??

→ Reply

danielcm586

5 years ago, # |

when will our rating change?

→ Reply

yash_daga

5 years ago, # ^ |

← Rev. 2 →

I hope it changes soon, I have refreshed my profile page atleast 50 times to see if I reach expert after the rating change.

→ Reply

5 years ago, # ^ |

I have lost count of the number of times I refreshed my profile. xD xD

→ Reply

yash_daga

5 years ago, # ^ |

Yeah me too XD. I was so excited after solving 5 questions for the first time that I couldn't sleep last night.

→ Reply

5 years ago, # ^ |

Same xD

→ Reply

126378

5 years ago, # |

Hacking phase finished more than 6 hours ago but no system testing till now!

→ Reply

kishan2101999

5 years ago, # |

How long does it take to give rating????

→ Reply

sharath101

5 years ago, # ^ |

System testing just started, I think it'll take an hour more

→ Reply

5 years ago, # |

When will the ratings change?

→ Reply

5 years ago, # |

Maybe they are thinking to do system testing together with round 628. It happened once afaik.

→ Reply

purple_rAin

5 years ago, # |

waiting for the rating change...

→ Reply

hwy2004

5 years ago, # |

← Rev. 2 →

Why another system testing?

→ Reply

hwy2004

5 years ago, # ^ |

And now it is stuck at 78%:D

→ Reply

5 years ago, # |

Testing is stuck at 78%

→ Reply

aberent

5 years ago, # |

Is system testing stuck? The status has been "System Testing 78%" for at least the last half hour.

→ Reply

kishan2101999

5 years ago, # |

Is there something happen with the site...? Because system testing stuck at 78%.

→ Reply

5 years ago, # |

+16

Even corona virus is faster than system testing

→ Reply

5 years ago, # |

great now stuck at 79!!

→ Reply

koshle

5 years ago, # |

+15

Cooper after returning to earth: Did system testing crossed 79%....??

→ Reply

Lelouch.Lamperouge

5 years ago, # |

The rate of system testing is prolly 1% per hour XD

→ Reply

5 years ago, # |

Python runs faster than this system testing :(

→ Reply

TheRedLegend

5 years ago, # |

Codeforces definitely needs a better hardware. :/

→ Reply

ashkANOn

5 years ago, # |

I think codeforces is going through their ever slowest system test.

→ Reply

5 years ago, # |

their slowest system testing in the history

→ Reply

TheRedLegend

5 years ago, # |

Hopefully this system testing will end in 2020. :D

→ Reply

farabi_Shafkat

5 years ago, # |

reached 100%, then went back to 91% :3 .

→ Reply

ChaosAngel

5 years ago, # |

Contrary to your speculations, I assure you everything is alright. The system testing is progressing very rapidly. It only took 2 minutes to go from 98% to 91%.

→ Reply

Alan_Mgine

5 years ago, # |

Recursive testing. :D

→ Reply

JJaewon

5 years ago, # |

wtf systest rolled back 100% -> 91%

→ Reply

Peregrine_Falcon

5 years ago, # |

What's wrong with the system testing? Does anyone knows?

→ Reply

di4s

5 years ago, # ^ |

← Rev. 3 →

deleted

→ Reply

Peregrine_Falcon

5 years ago, # ^ |

Seriously man!O_o

→ Reply

Lelouch.Lamperouge

5 years ago, # |

Did I just travelled back in time or what? system testing was 100 just a few mins ago and it's 92 now!!

→ Reply

abhijeetbiswas

5 years ago, # |

Why are D and E being tested again??

→ Reply

koshle

5 years ago, # ^ |

Because they were suspected to COVID19..

→ Reply

Lelouch.Lamperouge

5 years ago, # |

looks like they are testing problems D and E again as the count for rest of the problems is not changing

→ Reply

sashiming

5 years ago, # |

Finally system test has finished !!

→ Reply

5 years ago, # |

when will the ratings come?

→ Reply

ashkANOn

5 years ago, # |

Almost e qual time distribution for open hacking and system testing phase.

→ Reply

5 years ago, # |

Why is final standings fluctuating , some kind of superposition???

→ Reply

5 years ago, # ^ |

If you are talking about the show unofficial standings then that is because some people entered the round virtually.

→ Reply

5 years ago, # ^ |

The official one , I get it now , the rankings keeps on fluctuating because of untrusted participants.

→ Reply

5 years ago, # ^ |

True, I keep changing from 177 to 251 back and forth.

→ Reply

https://www.youtube.com/playlist?list=PLl4Y2XuUavmtjmxnbqOAb_UNyRK1soQZw

5 years ago, # ^ |

One ranking with unrated participants and other calculated only with rated ones.

→ Reply

0ideas

5 years ago, # |

Where is our rating?

→ Reply

oruegg19

5 years ago, # |

It has been a day since the contest ended. And 12 hours since the hacking phase ended. There has been no change in ratings. Is this a usual occurrence?

→ Reply

coder_pulkit_c

5 years ago, # |

+16

Will be uploading solution videos of all questions on this link.

→ Reply

ankit-SM

5 years ago, # |

← Rev. 2 →

→ Reply