Codeforces Round #780 (Div. 3)

2 years ago, # |

← Rev. 2 →

+44

A: nice and easy, thanks for including 0 2 into samples.
B: a bit tricky for its position, but okay.
C: nice greedy, even tho not all people proved it.
D: the worst problem I've solved in March.
E: a bit too easy for its position, definitely easier than D.
F: nice observation-based problem.

Nice contest, but D should've been removed or at least switched with E.

→ Reply

Trippie

2 years ago, # ^ |

nice greedy, even tho not all people proved it

what exactly is there to prove?

→ Reply

2 years ago, # ^ |

That you can take the first recurring character into the answer. See 151525744. Also it just came to my knowledge that some people did dp, then yes, there is nothing to prove.

→ Reply

Chef__Forces

2 years ago, # ^ |

what can be the approach for E

→ Reply

2 years ago, # ^ |

There are only $$$n$$$ possible diagonals, one can explicitly check them all.

→ Reply

2 years ago, # ^ |

Note that any shift, up/down/left/right, preserves the diagonals as they are (if you consider the diagonals as 'wrapping round' when they reach an edge). Find the diagonal with the most 1s on it, say it has X 1s out of a total of Y 1s on the whole grid. Then the answer is (Y — X) + (N — X): the number of 1s off main diagonal is Y — X, and the number of 0s on the main diagonal is N — X.

→ Reply

Arun_bro1

2 years ago, # ^ |

I observe that after any operation finally what you have to do is choose some row and move downward and check the cost. there are n rows and n operation to check each row.

→ Reply

Mohd_Arbaz

2 years ago, # ^ |

my solution to f1 is taking 982ms runtime, i think it is hackable, can you please try to hack it Your text to link here...

→ Reply

2 years ago, # ^ |

I don't think that it is hackable unless 982ms comes from re-running your solution several times (CF does that to close-to-tle solutions). From my experiments, the worst case for your solution is simply 3000 minuses. Here is a generator that I used in experiments.

This is also visible in code, as it takes the longest to run if p<m all the time and condition y-(a*2)<m never breaks early. This is exactly the case of 3000 minuses.

Some reasoning for why this works fast may be that:

you process each substring in $$$1/3$$$ of its length;
there are roughly $$$n^2/2$$$ substrings;
the average length of a substring is roughly $$$n/3$$$.

It follows that your solution performs roughly $$$n^3/18$$$ operations, or 1.5 billion, which is not that far off what is usually considered to be acceptable.

→ Reply

2 years ago, # ^ |

how to solve C with greedy?I can only come up with a DP solution

→ Reply

2 years ago, # ^ |

← Rev. 2 →

You can take the first recurring character into the answer. See 151525744.

→ Reply

2 years ago, # ^ |

you can solve it without dp like this:

imagine we want to maximize the # of characters preserved, instead of minimizing the # of deletions. Supposed we want to preserve a pair of some character c, which occurs at indices [i1, i2, i3 ... ] (in sorted order). We would never want to preserve the c's at i1 and i3, because (i1, i2) will give us the same result for fewer deletions.

So let's consider the adjacent intervals for each occurrence of every character. (i1, i2) (i2, i3) (i3, i4) ...

Note that if we choose to take some interval (i,j) it means we are preserving the 2 characters at i and j. This also implies, that everything between them is deleted. If that's the case, then the optimal answer which maximizes the # of preserved characters is clearly reduced to: the maximum number of disjoint intervals we can take.

If we stick all of these adjacent intervals, for each unique character, into a big array, we can run a greedy algorithm to compute the max disjoint intervals taken.

Here is code: https://codeforces.com/contest/1660/submission/152393885

→ Reply

winterfire

2 years ago, # ^ |

← Rev. 2 →

I agree. Problem D took an hour out of me, and I ended up with an RTE on test 2. 151575805

EDIT: Thanks for pointing out the greedy approach for C. Like several others, I used DP. 151539005

→ Reply

cheese_case

2 years ago, # ^ |

I think D is a Directly Calculating..

→ Reply

cheese_case

2 years ago, # ^ |

thank for your ideas

→ Reply

2 years ago, # ^ |

← Rev. 2 →

I think F2 and D are both a lot easier to come up with than E

Maybe a severe intuition gap on my part

→ Reply

2 years ago, # |

How to solve F2? I'm too weak :(

→ Reply

who_asked

2 years ago, # ^ |

You can use divide an conquer in $$$O(Nlog^2N)$$$

→ Reply

2 years ago, # ^ |

+14

Claim: $$$(l, r)$$$ is good if $$$\text{balance}[r] \le \text{balance}[l]$$$ and $$$\text{balance}[l] \equiv \text{balance}[r] \pmod{3}$$$, where $$$\text{balance}[i]$$$ is balance of prefix $$$s[0..i]$$$. We will count $$$(l, r)$$$ grouped by $$$r$$$. This means counting numbers greater than or equal to something with a given remainder modulo $$$3$$$. I used 3 ordered_sets for this purpose, with balance numbers grouped by remainder, but there is also a linear dp that uses discrete continuity.

→ Reply

2 years ago, # ^ |

Thank you so much! Now I get it :) I thouht too much and didn't solve it even though I came up with the idea of $$$3$$$ QAQ

→ Reply

yuziriha

2 years ago, # ^ |

Why cant u a purple refer to Fenwick Tree??i dont think f2 a hard one since youve done f1

→ Reply

2 years ago, # ^ |

My solution to F1 was too complex so that I constrainted myself in that way :<

→ Reply

rgnerdplayer

2 years ago, # ^ |

3 BITs solves in $$$O(nlgn)$$$.

→ Reply

pooty

2 years ago, # ^ |

+11

I think the key observation is that if minus count > plus count + 1, you can always combine some minuses together to makes plus (since they would definitely be minuses adjacent to each other), which simplifies the question greatly because now you don't really need to keep track of the position of minuses and whether they can merge or not. When that idea struck me after trying for a while, the question became rather classic.

→ Reply

YoisakiKanade

2 years ago, # ^ |

+36

Same.

When I was solving F1, I forgot the limit of adjacent minus signs, but I got an accepted verdict. An interesting thing is that I have even not noticed that the limit is not necessary after that. Then I resubmitted the "corrected" code on F1.

This minor mistake took me more time to get the right idea of F2.

→ Reply

2 years ago, # ^ |

I made it $$$O(NlogN)$$$ with a segment tree(of course Fenwick tree can also solve it)

→ Reply

Just__a__Visitor

2 years ago, # |

-17

My approach for F1. Promising String (easy version).

Part 1: A necessary and sufficient condition for a string to be promising.
Part 2: $$$O(n)$$$ algorithm to check the previous condition.
Part 3: $$$O(n^3)$$$ solution to the problem using 2D DP.
Part 4: Optimizing the previous solution to $$$O(n^2)$$$ .

Part 1

Part 2

Part 3

Part 4

Code

→ Reply

Sakura_mw

2 years ago, # ^ |

I suppose presenting the process of problem solving is often useful for adequate programmers..? Can not understand so many downvotes though some little mistakes in Part 3.

→ Reply

2 years ago, # ^ |

i think downvotes are just because there's an easier way under f1 constraints. Can just brute force it directly without any dp

→ Reply

Sakura_mw

2 years ago, # ^ |

alright, got it :)

→ Reply

sayemsub15

2 years ago, # |

How to do 'C'? I couldn't come up with any solution in two hours

→ Reply

afix

2 years ago, # ^ |

← Rev. 2 →

My solution

→ Reply

cheese_case

2 years ago, # ^ |

thank you & you are so strong

→ Reply

Maksadbek

2 years ago, # ^ |

How do we now if the previous position of i was already coupled with other previous k: k < j < i ?

For example: "aaa". Here we couple 1 with 0. After that we can't couple 2 with 1 because 1 is already coupled.

→ Reply

afix

2 years ago, # ^ |

← Rev. 2 →

You don't need to know that. When you try to couple the current position i with the previous position j, you then look at the answer for the substring that ends at j-1. So for your example the solution will look like this:

Current substring is "a". The answer is 1.
Current substring is "aa". We either delete 1 and add the answer for 0 (1+1=2 total deletions), or couple 1 with 0 (0 total deletions)
Current substring is "aaa". We either delete 2 and add the answer for 1 (1+0=1 total deletion), or couple 2 with 1 and add the answer for 0 (0+1=1 total deletions).

→ Reply

Maksadbek

2 years ago, # ^ |

Thank you! Now I got it.

→ Reply

whiteshadow98

2 years ago, # ^ |

← Rev. 4 →

For any character at a position i , you can only do 2 things.
a) Remove the ith character b)Pair up ith character with the next index j , such that j>i AND s[j]==s[i].

Now , you can write a recursive function to do the same and memorize it for the constraints.

→ Reply

AAK

2 years ago, # ^ |

Greedily selecting pairs of same characters traversing from left to right to not be deleted, and removing the rest was what worked for me. My intuition was that it would never be better to remove the "closest" pairs of same characters, because in doing so we'd be removing 2 characters just to merge 2 other characters. I don't have a proof for this though.

Code

void solve()
{
    string s; cin>>s;
    int n = s.length(), ans = 0;
    vector<bool> c(26, 0);
    rep(i, n) {
        if(c[s[i]-'a']) {
            c.clear(); c.resize(26, 0);
            ans -= 2;
        } else {
            c[s[i]-'a'] = 1;
        }
    }
    cout<<n+ans<<'\n';
}

→ Reply

2 years ago, # ^ |

if you're interested, you can solve it without dp like this:

So let's consider the adjacent intervals for each occurrence of every character. (i1, i2) (i2, i3) (i3, i4) ...

If we stick all of these adjacent intervals, for each unique character, into a big array, we can run a greedy algorithm to compute the max disjoint intervals taken.

Here is code: https://codeforces.com/contest/1660/submission/152393885

→ Reply

Zealotrahl

2 years ago, # |

what was the website showing smallest countertest to submission?

→ Reply

2 years ago, # ^ |

You called? :)

Will be adding the problems from this contest in an hour or two. Stay tuned!

→ Reply

Bn_Gaber

2 years ago, # |

any hint to solve C?

→ Reply

eyfmharb

2 years ago, # ^ |

Let $$$dp[i]$$$ denote the minimum number of deletions to make string $$$s[0..i]$$$ even. Then you can either delete $$$s[i]$$$ (corresponding to $$$dp[i-1]$$$), or you can match $$$s[i]$$$ with another $$$s[j]$$$ where $$$j<i$$$ and $$$s[j]=s[i]$$$. Now how can find that $$$j$$$ by doing preprocessing?

→ Reply

2 years ago, # ^ |

← Rev. 2 →

Work greedily on segments When s[i] == s[i+1] increment i by 2 when i == n-1 increment res by 1 When s[i]!=s[i+1] Now try to search for two chars in a segment that are the same like here mbacb two b are there So we will remove mac here

Simply to search whether there are two same chars we can use set If we found one then res will be inc by window_size — 2 otherwise, res will take that entire window.

This was my approach. I hope it doesn't get hacked 151529755

→ Reply

Osama_Gharib

2 years ago, # ^ |

greedy approach: if s[i]==s[i+1] you move to s[i+2]. else you choose to either remove the whole remaining string, or match two characters. To match two characters iterate through every character c from 'a' to 'z', then find the next occurrence of c and the next next occurrence of c and in order to match the two characters you will remove every character before the first occurrence of c and every character in between the first occurrence and second occurrence of c.

→ Reply

2 years ago, # ^ |

if you're interested, you can solve it without dp like this:

So let's consider the adjacent intervals for each occurrence of every character. (i1, i2) (i2, i3) (i3, i4) ...

If we stick all of these adjacent intervals, for each unique character, into a big array, we can run a greedy algorithm to compute the max disjoint intervals taken.

Here is code: https://codeforces.com/contest/1660/submission/152393885

→ Reply

mon0pole

2 years ago, # |

Were the problems too easy?
First time AK'ed any div3. contest.(Hoping I won't FST)
Thanks for the problemset.

→ Reply

lbm364dl

2 years ago, # ^ |

Actually I only solved A and B

→ Reply

2 years ago, # ^ |

Far from it, I'd say. C and D were quite difficult by Div 3C and Div 3D standards. I solved C with dynamic programming and D with a relatively fiddly implementation. There may have been easier ways to do it, but I found them far from trivial. Then E and F1 were much easier. That was strange! A fun contest.

→ Reply

Zealotrahl

2 years ago, # ^ |

I don't get why most of the people solved C using DP, such solution looks so elegant, hope it does not fail https://codeforces.com/contest/1660/submission/151587350

→ Reply

2 years ago, # ^ |

The simple answer will be that it was the first (and safest) idea that came to people's minds. DP is often a safer approach than greedy.

You are right — that solution is elegant.

→ Reply

vrintle

2 years ago, # ^ |

It feels so, because its the first time I also AK'ed a Div3 without a single wrong attempt!

Maybe E should've more harder.

→ Reply

2 years ago, # ^ |

← Rev. 2 →

Also my first AK.I think the difficulty of the questions is more average.ABC is not that easy and EF is not that difficult.

→ Reply

yu_zkkk

2 years ago, # |

Why is the time limit for question d, can someone help me take a look, I think it is O(n)Your text to link here...

→ Reply

paulzrm

2 years ago, # ^ |

i'm sorry that your solution works in $$$O(n^2)$$$ because of the first line in f()

    while(l<=n&&a[l]==0)l++;while(r>=1&&a[r]==0)r--;

when a[] are all zero, l will run to n+1 and r will run to 0.

That costs O(n) each time, and it will process n times.

→ Reply

S_Neal

2 years ago, # |

can you give me test case for problem D . https://codeforces.com/contest/1660/submission/151583999 I can't find why it gets wrong answer.

→ Reply

2 years ago, # ^ |

Failing testcase: Ticket 3077

→ Reply

2 years ago, # |

← Rev. 2 →

What was test case 14 in D

Can someone provide me a corner case for this solution?

My approach was to calculate the maximum product subarray ending index then, remove n-that_index-1 elements from the array after that pop element and check their product when product == max product print size of the remaining array.

151575450

→ Reply

Chef__Forces

2 years ago, # ^ |

bro u cant just multiply the numbers as if we have 100 numbers 2 in our array so ur code will calculate 2 power 100 which is a very huge value and cant be stored so u should have calculate the frequency of 2 or -2 in spite of product because only frequency of abs(2) matters in the products

→ Reply

kh0i

2 years ago, # ^ |

$$$2^{200000} = $$$ overflow.

→ Reply

2 years ago, # ^ |

I want to bang my head against wall :)

→ Reply

Chef__Forces

2 years ago, # ^ |

i also did the same mistake and got 3 wa in the starting

→ Reply

wakaranai

2 years ago, # ^ |

You can probably still do it this way using this property: log(a*b) = log(a) + log(b) to avoid overflow errors.

→ Reply

2 years ago, # |

My solution to problem D:

It's easy to find that the final product must be positive,so we can divide the sequence by every $$$0$$$.

For each subsequence:

If the product is negative,find the far left negative number and the far right negative number,compare their results and shorten the subsequence. It is easy to see the product must be postive after this operation. When we compared the subsequences,we only need to pay attention to the $$$2$$$ and $$$-2$$$,so we can use prefix sum to solve it.

Finally we check all the subsequnces and find the best answer.

The solution is $$$O(n)$$$.

Pardon me for my bad English :(. You can try to connect the code to understand it.

code

#include<bits/stdc++.h>
//#define int ll
#define pb push_back
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define piii pair<int,pair<int,int> >
using namespace std;
typedef long long ll;
const int N=300005;
const int inf=(1<<30)-1;
const ll inff=1ll<<60;
const int mod=1e9+7;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
int n,a[N],f[N];
int ansl,ansr;
void solve(int l,int r){
	if(l == r && a[l] < 0) return;
	int minus=0;
	for(int i=l;i<=r;i++){
		if(a[i] < 0) minus++;
	}
	if(minus%2){
		int tmp1=0,tmp2=0;
		for(int i=l;i<=r;i++)
		    if(a[i] < 0){
		    	tmp1 = i;
		    	break;
		    }
		for(int i=r;i>=l;i--)
			if(a[i] < 0){
				tmp2 = i;
				break;
			}
		if(f[r] - f[tmp1] > f[tmp2-1] - f[l-1]) l=tmp1+1;
		else r=tmp2-1;
	}
	if(f[r]-f[l-1] > f[ansr]-f[ansl-1])
	    ansr=r,ansl=l;
}
int main(){int tests=1;tests=read();
while(tests--){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++){
		f[i] = f[i-1] + (abs(a[i])==2);
	}
	if(n == 1){
		if(a[1] > 0) puts("0 0");
		else puts("1 0"); 
		continue;
	}
	int lst=0;
	a[n+1]=0;
	ansl=0,ansr=0;
	for(int i=1;i<=n+1;i++)
	    if(a[i] == 0){
	    	solve(lst+1,i-1);
	    	lst=i;
	    }
	if(ansl == 0 && ansr == 0) printf("%d 0\n",n);
	else printf("%d %d\n",ansl-1,n-ansr);
}	return 0;
}

→ Reply

Osama_Gharib

2 years ago, # ^ |

tfw solved it but used a prefix product array and thus overflowed. Feelsbad

→ Reply

Dan4Life

2 years ago, # ^ |

I tried that, but couldnt figure out the reason for tle

→ Reply

AmiteshMagar

2 years ago, # |

Definitely, one of the best contest i have given so far. Expecting to become specialist once again!!

Great questions by the setter and good strong test cases. Thank you!!

→ Reply

VOBEYAN

2 years ago, # |

Love Aris

→ Reply

YesIAmANoob

2 years ago, # |

+10

Is it possible to hack the slow solutions of problem F1?

→ Reply

zhude

2 years ago, # |

I think problem C is the hardest problem. I use 22min on it.

→ Reply

singh04

2 years ago, # |

I think this div 3 round should be declared div 2.

→ Reply

2 years ago, # ^ |

I think it is of medium difficulty in div3s.

→ Reply

singh04

2 years ago, # ^ |

Just the way the first 2 questions of div 2 are doable at least the first three questions of div 3 should be doable. But, the number of submissions is telling a different story.

→ Reply

2 years ago, # ^ |

C is hard for this position,this I agree.

→ Reply

2 years ago, # |

← Rev. 3 →

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

I've also added a new feature to view progress of your judgement in near real-time. (For example, the current state of your ticket, how many inputs were evaluated, etc).

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

→ Reply

mnkqc

2 years ago, # |

← Rev. 2 →

Learning From Mistake (Mistake 4)

Initially, After getting the usual wa on test 2, I tried another approach 151583179, which gave a runtime error on test 15. I went around stress testing as to why is giving Runtime error, and spent way too much time on it.
After the contest, I tried to print the error 151598207 and it was this
In python, int does not have an upper bound on size (It depends on the system), but float does. Float has an upper bound, which can be checked using sys.float_info.max. I did not know it. It cost me an AC. After replacing the / with //, It 151598360 gave an AC. How foolish of me!

→ Reply

Individual

2 years ago, # |

Bruh... Managed to only solve B and A, failed at C. Now tried E and solved it within a couple of minutes. I think I am just a total disgrace at DP. Could anyone recommend me a way to master on problems of this tag?

→ Reply

2 years ago, # ^ |

if you're interested, you can solve it without dp like this:

So let's consider the adjacent intervals for each occurrence of every character. (i1, i2) (i2, i3) (i3, i4) ...

If we stick all of these adjacent intervals, for each unique character, into a big array, we can run a greedy algorithm to compute the max disjoint intervals taken.

Here is code: https://codeforces.com/contest/1660/submission/152393885

→ Reply

Individual

2 years ago, # ^ |

Thanks a lot! Will have a deep look

→ Reply

beethoven97

2 years ago, # |

when i try to hack a solution i received an Unexpected verdict, what it means?

→ Reply

till-t

2 years ago, # |

First contest, big thanks to the writers and testers! For problems that I struggled with, what is the best way to get guidance? Thanks!

→ Reply

acorn11

2 years ago, # ^ |

You can wait for the editorial thread or just ask here.

→ Reply

SecondThread

2 years ago, # ^ |

Or go here.

→ Reply

till-t

2 years ago, # ^ |

When do editorial threads post?

→ Reply

acorn11

2 years ago, # ^ |

← Rev. 4 →

Within 24 hours typically.

Sometimes the threads are posted immediately after the contest but for Div3/Educational I think they wait at least after the hacking phase (12 Hours).

Also the ratings are updated at more or less the same time.

→ Reply

till-t

2 years ago, # ^ |

Great, appreciate you

→ Reply

Tenac-ious-

2 years ago, # |

I am getting TLE on problem D please help!! submission : link

→ Reply

SecondThread

2 years ago, # |

+43

My speedrun and video solutions to all problems is available here on my youtube channel for anyone interested.

→ Reply

2 years ago, # |

Commemorating my first time to solve all tasks in a contest.

→ Reply

h00p3r2

2 years ago, # |

← Rev. 3 →

Please if someone can help me with Problem D, my code computes the first and last index of the subarray. I can't find anything wrong with it (Overflow shouldn't be a problem because Python supports arbitrarily large integers). Submission: 151614920

Nevermind: ...empty product has value 1. But still got TLE despite O(N). Guess large products are costly.

→ Reply

2 years ago, # ^ |

← Rev. 2 →

Python's large integer operation is slow when the integers are extremely large.Don't use that.You can express it as $$$\pm 2^x$$$ instead.(sorry for my poor English

→ Reply

SigninQQ

2 years ago, # ^ |

Maybe the value of cur overflows.

→ Reply

shreyas_171

2 years ago, # |

Can anyone explain me the intuition of MAP solution in C prblm ?

→ Reply

ahmedfouadnew

2 years ago, # ^ |

I believe it comes from thinking of those elements left in the map as being unavailable for the upcoming letters in the string or that they shouldn't be matched with any of the upcoming letters as this will break the order of the string.

→ Reply

Tenac-ious-

2 years ago, # |

I am getting TLE on problem D please help!! submission : link

→ Reply

onlyerror

2 years ago, # |

← Rev. 2 →

F1 and C should be interchanged

→ Reply

ahirjasmin5

2 years ago, # |

Is it unrated really, can anyone please reply ?

→ Reply

yukai

2 years ago, # ^ |

I would also like to know

→ Reply

ash.ketchup

2 years ago, # |

Hello. I have a rating under 1600, and I believe I am a trusted account. But last night, when I participated in this contest, my ratings didn't change. Can anyone help me understand what happened?

→ Reply

AFLeartLey0103

2 years ago, # ^ |

I satisfy the conditions too but my rating didn't change too idk what happened

→ Reply

ash.ketchup

2 years ago, # ^ |

What should we do? How do we attract the attention of CF authorities?

→ Reply

AFLeartLey0103

2 years ago, # ^ |

It seems that no participant got a change in their rating, idk if it is true If any samples which conflicts my opinion just reply me

→ Reply

2 years ago, # ^ |

← Rev. 2 →

Just wait. The ratings will be updated within few hours since there was a hacking phase after the contest that's why it's taking time.

→ Reply

yunhh

2 years ago, # |

Where is the solution?

→ Reply

Akiyama-Mizuki

2 years ago, # ^ |

You can read other people's code(in status) and try to understand the correct solution until the official solutions.

→ Reply

OLIN_ONE

2 years ago, # |

Can someone help me why am I getting wa on testcase 2? Here is my submission : 152264434

Approach : get all segment without zeros , and try to find the best answer from those segments .

any counter example would be so much helpful

→ Reply

2 years ago, # ^ |

Failing testcase: Ticket 3199

→ Reply

lazy_loop

2 years ago, # ^ |

Pls help https://codeforces.com/contest/1660/submission/152302981 Thankyou

→ Reply

2 years ago, # ^ |

Failing testcase: Ticket 3289

P.S: You don't need to ping me. You can learn how to use the website using this blog and comment

→ Reply

lazy_loop

2 years ago, # ^ |

Thanks a lot!

→ Reply

2 years ago, # |

← Rev. 2 →

Someone has spammed the problem tags for F2 — if anyone has tag edit access and can undo it that would be good.

UPD: resolved, thanks

→ Reply

sunstar2022

2 years ago, # |

Why this submission TLE? I think it is right and I have submitted after the contest, however, it was Accepted. Could anyone give me a hand?

→ Reply

2 years ago, # |

← Rev. 3 →

I have a problem with the problem D. In contest time I got "Accepted". But now I got "wrong Answer" in the same test case (Test case 2). So, why I didn't get "WA" in contest time. I still had 10-15 minutes. Please help me with this situation.

→ Reply

sanyacoder

2 years ago, # ^ |

Maybe it's because in the hacking phase somebody else's solution was hacked and then that hacking test was added to the rest of the other D tests, and your solution fails the test

→ Reply

2 years ago, # ^ |

← Rev. 4 →

NO. It's not like that. The test case existed before. The test case was -

1 0

For this I printed "0 0", it got accepted in contest time. But now I am getting WA.

→ Reply

johnLate

2 years ago, # ^ |

Maybe the original checker was wrong and got fixed.

From the problem statement:

The product of elements of an empty array (array of length $$$0$$$) should be assumed to be $$$1$$$.

So for this testcase:

1
0

0 0 would mean to keep the only element, so the product for this array would be 0
1 0 or 0 1 would mean to delete the only element -> result is 1

Another testcase:

2
1 0

0 0 -> 0
1 0 -> 0
0 1 -> 1 (empty array is also correct: 2 0, 1 1, 0 2)

→ Reply

2 years ago, # ^ |

I know. But my point was if I got a correct verdict in contest time maybe I could solve the problem. But I didn't. I got the correct verdict in system testing. Why ? I am the one who suffered.

→ Reply

johnLate

2 years ago, # ^ |

The world is not perfect. Sometimes mistakes happen.

Do not take it too seriously. Maybe you could have gained a bit more rating, but others would have been better too, so maybe not. Anyway, do a few more contests in the future and your "suffering" will be forgotten.

→ Reply

2 years ago, # ^ |

The test case was 2. It was already in the pretest. From my previous submission I can see that my answer for that case wasn't considered wrong.

→ Reply

MR_HAROT_9655

2 years ago, # ^ |

← Rev. 2 →

exactly same happened with me, my code gave 0 0 on test case 1 0, which is indeed wrong ans due to a typo but during the contest it showed accepted, so i didn't checked it again, but now its wrong ans on test case 2, i had 10 -15 min remaining when i submitted D, i could have corrected my solution

→ Reply

Prahmodh_Raj

2 years ago, # |

Why haven't the rating changes been applied yet?

→ Reply

Reborn

2 years ago, # ^ |

Me too.

→ Reply

Reborn

2 years ago, # ^ |

I've waited for a long time! Is it a trick on April Fool's Day?

→ Reply

Alexey

2 years ago, # ^ |

It's usual for div3 and educational rounds

→ Reply

Jadebo1

2 years ago, # |

when will I get my score

→ Reply

mukeshsingh__123

2 years ago, # |

can anyone tell me the solution of C problem without dp

→ Reply

2 years ago, # ^ |

Simply to search whether there are two same chars we can use set If we found one then res will be inc by window_size — 2 otherwise, res will take that entire window.151529755

→ Reply

https://codeforces.com/contest/1660/submission/151537948

2 years ago, # ^ |

Greedy.

Make same letters into pairs $$$(l,r)$$$

For each time,choose the pair that the $$$r$$$ is minimal.

Pardon for my bad English,you can see the code to understand it better :p

→ Reply

mukeshsingh__123

2 years ago, # ^ |

can you please explain in more detail..i will be grateful

→ Reply