Educational Codeforces Round 150 [рейтинговый для Div. 2]

11 месяцев назад, # ^ |

← Rev. 2 →

Thanks a lot! and I believe $$$k$$$ should be the rightmost interval that does not intersect $$$i$$$ and $$$j$$$ instead of the leftmost one. Am I right? UPD. I got what you means by "leftmost". Thanks!

→ Ответить

pkpawan

11 месяцев назад, # |

← Rev. 2 →

Test case 9 or problem C ruined my contest.

→ Ответить

Sakuya_maid

11 месяцев назад, # |

I like to see a magic trick where I lose 100 points at a time

→ Ответить

_Shinigami

11 месяцев назад, # |

can anyone tell me what's wrong in this solution of problem B

→ Ответить

Jeevansingh.126

11 месяцев назад, # ^ |

First, you need to compare a[i] with v.back() not a[i-1].
Change isSorted only when we insert an element in v, not otherwise because it will remain sorted if we are not inserting any element. updated solution — https://codeforces.com/contest/1841/my

→ Ответить

_Shinigami

11 месяцев назад, # ^ |

thanks a lot, got it now

→ Ответить

abc864197532

11 месяцев назад, # |

Problem F almost = This Problem

→ Ответить

thedykosas

11 месяцев назад, # |

Please tell if someone is kind to stream problemset discussion. Thx

→ Ответить

abc864197532

11 месяцев назад, # |

+35

Problem F almost = This Problem

→ Ответить

Hmys

11 месяцев назад, # |

My solution for C was to count the number of "positive" numbers before a letter, ie numbers that weren't guaranteed to be negative by an earlier number. Then calculate the "gain" you get by changing letter s[i] to k, by looking at whether s[i] was guaranteed to be negative by looking at the biggest letter strictly above it, and summing over the number of letters before it that would become negative by changing it to that value. Is this correct? I got wrong answer on testcase 10.

→ Ответить

robostac

11 месяцев назад, # ^ |

Best answer can be negative (you only allow changes if best > 0)

→ Ответить

Hmys

11 месяцев назад, # ^ |

Hmmm. I did include that. I only set best initialized to -10^15. Maybe that was the issue.

→ Ответить

Shivu

11 месяцев назад, # |

PROCEDURE FOR C WAS VERY CLEAR BUT COULDN'T IMPLEMENT IT

→ Ответить

pedrosorio

11 месяцев назад, # |

← Rev. 6 →

Final EDIT: The solution can be negative. Never assume initializing best = 0 will work...

Problem C WA on test 10. Does anyone know what this test is?

Even implemented a brute force solution during the contest and tested on all strings up to length 10 and gives the same result as my solution. What am I missing?

Brute force solution:

def value(s):
    s = [ord(c)-ord('A') for c in s]
    res = 0
    md = 0
    for i in range(len(s)-1, -1, -1):
        if s[i] < md:
            res -= (10 ** s[i])
        else:
            res += (10 ** s[i])
        md = max(md, s[i])
    return res

def generate_replacements(s):
    yield s
    for i in range(len(s)):
        for d in range(5):
            if d == ord(s[i]) - ord('A'):
                continue
            yield s[:i] + chr(ord('A') + d) + s[i+1:]

def brute_force(s):
    return max(value(r) for r in generate_replacements(s))

EDIT: Up to length 10 may not be the best test since 10*D = E, etc. but my code doesn't seem to have issues with things like 100 * 'D' + 'E'.

EDIT2: It does have issues with 100 * 'D' + 'EE' of course...

→ Ответить

swayingdream

11 месяцев назад, # ^ |

← Rev. 3 →

Input: 2 DDDDDDDDDDDDDDDDDDDE EEEEE

Expected: 20000 50000

Found: 28000 40000

→ Ответить

llc5pg

11 месяцев назад, # ^ |

OK, So, we should consider decreasing the last E to D.

→ Ответить

pedrosorio

11 месяцев назад, # ^ |

I don't understand this comment. What does it have to do with mine?

→ Ответить

smilinginpain

11 месяцев назад, # ^ |

Yes, you can change at max 1, it implies either 0 or 1, so for TC 2, you change 0 times to get 50K

For input 1, you can change E to D, so answer will be 20*1000

→ Ответить

page_fault

11 месяцев назад, # ^ |

The answer can be negative as well; I missed that at first and got WA on test 10. Maybe that's what you're missing as well.

→ Ответить

https://codeforces.com/contest/1841/submission/209467430

11 месяцев назад, # ^ |

Oo f*ck

→ Ответить

Rakesh_898

11 месяцев назад, # |

← Rev. 4 →

-67

I use prefix sum concept in problem c and change one by one charcter in string and every time i take maximum of all but got wr0ng answer on test case 9. Lmao what is the test case that missed my code anyone?

→ Ответить

Number_72

11 месяцев назад, # ^ |

same but you should also consider decreasing. Check my submissions.

→ Ответить

Sokol080808

11 месяцев назад, # |

+10

Кажется, что задача С — упрощенная версия задачи "Московские числа" (вроде такое название) с какого-то прошлого всероса

→ Ответить

b16a

11 месяцев назад, # ^ |

задача классная! жаль только WA9... :(

→ Ответить

dxbt

11 месяцев назад, # |

SO problem D can be solved by Monotonic stack？

→ Ответить

ARMINIUS

11 месяцев назад, # |

have no testers in educational rounds makes trouble again this time in problem F?

→ Ответить

MojoLake

11 месяцев назад, # |

I tried doing a greedy graphy solution to D but didn't work :D.

→ Ответить

onlyerror

11 месяцев назад, # ^ |

← Rev. 2 →

Sort then dp.

→ Ответить

shubhu1

11 месяцев назад, # |

What test case for problem B was this solution failing?

→ Ответить

taarkik

11 месяцев назад, # ^ |

← Rev. 3 →

yeah tricky edge cases

→ Ответить

BigBadBully

11 месяцев назад, # ^ |

I used 2 variables, a prev and current pointer, but my solution failed like 50 times cuz i forgot to check if i added the element prev is at, also try checking if the current number is smaller than first element if you got to the beauty something part (i hope u understood)

→ Ответить

Swishy123

11 месяцев назад, # |

+25

I think E is easier than D, didn't feel like it belongs there though...

→ Ответить

onlyerror

11 месяцев назад, # ^ |

Can you please share your approach?

→ Ответить

29logN

11 месяцев назад, # |

PAIN 😞

→ Ответить

iiand

11 месяцев назад, # ^ |

I have +- the same, i will not write Edu in future:)(cause on last maybe 4 edu i get -100. But on normal rounds i dont get such huge drop :))

→ Ответить

Something.

11 месяцев назад, # |

C is hard a little but it's very interesting

→ Ответить

11 месяцев назад, # ^ |

What is the idea

→ Ответить

cleanser

11 месяцев назад, # |

What's test 10 for C?

→ Ответить

11 месяцев назад, # ^ |

→ Ответить

cleanser

11 месяцев назад, # ^ |

Never mind. Didn't realize the answer could be negative.

→ Ответить

JEE_MAIN_LOOSER

11 месяцев назад, # |

Why am i getting Wa 9 at Problem C?? I changed every char from A to E and adjusted the change accordingly?? What am I missing?

→ Ответить

prateek_saxena

11 месяцев назад, # ^ |

← Rev. 3 →

Your code is giving wrong answer for these type of input strings: DDDDDDDDDDDDDE . Changing last E to D is optimal.

→ Ответить

JEE_MAIN_LOOSER

11 месяцев назад, # ^ |

I figured out. I wrote some absolute bullSh*t there. Finally did with Dp. I should have thought through dp way too during contest.

→ Ответить

YocyCraft

11 месяцев назад, # |

← Rev. 2 →

+41

A: If n>=5, Alice can combine n-2 ones to make the array {1, 1, n-2}, and Bob can only make it into {2, n-2} then Alice wins. If n<=4, Bob always wins.

B: A beautiful array need to be increasing, or there's an index i where a[1, i] and a[i+1, n] are increasing and a[n]<=a[1]. Therefore, we first need to check whether the queried x[i] is not smaller than the last appended element. When the first time we meet such x[i] doesn't satisfy the condition and x[i]<=x[1], we need to accept it, but we can't accept numbers where x[i]>x[1] from now on.

C: To solve this problem we need to pre-calculate 5 arrays sum[t][i]: the contribution of s[1, i] if s[i+1]==t and s[i+2, n] doesn't exist. We calculate it by the following process: First let cnt[u]=0 where 'A'<=u<='E'. When we see s[i]<t, we let sum[t][i]=sum[t][i-1]-10^(s[i]-'A') directly, since the contribution of s[i] will always be negative. Otherwise, we need to check for u where t<=u<s[i]: We let sum[t][i]-=2*cnt[u]*10^(u-'A') and cnt[u]=0, which means contribution of occurences of u changed from positive to negative. Finally we let cnt[s[i]]+=1. After we calculate the arrays, the problem can be solved by trying every possible change of s[i].

D: We sort ranges by r[i] increasingly and run dp: dp[i]=the maximum number of valid pairs for first i ranges after sorted. The transition is dp[i]=max(dp[i-1], dp[left(i,j)]+1) where j<i, r[j]>=l[i] and left(i,j) = the maximum index k where r[k]<min(l[i],l[j]).

E: Each row is divided into several segments by black cells. By greedy method we want to fill numbers in longer segments (since a consecutive segment of white cells with length k can contribute k-1 to the answer), so we need to calculate for each k, how many segments of length k in the matrix. If we scan the matrix from up to down (from n-th row to 1st row), we can see if a[j]=i, then there's a white segment being cut at position j when we scan to the i-th row. So we can let cnt[n]=n and cnt[t]=0 (1<=t<=n-1) at the beginning, when we scan to the i-th row, we cut segments at position j for all a[j]=i. When we remove a segment of length k, we let cnt[k]-=i, and when we add a segment of length k, we let cnt[k]+=i. We can store these segments by an ordered map. Finally we check segments from length n to length 2, and fill them to get the answer.

→ Ответить

Pacybwoah

11 месяцев назад, # ^ |

In D, how do you deal with cases where l[i]<l[j]? Thanks in advance!

→ Ответить

YocyCraft

11 месяцев назад, # ^ |

We only need to check the maximum index k where r[k]<min(l[i],l[j]).

→ Ответить

MridulAhi

11 месяцев назад, # ^ |

← Rev. 2 →

+47

There's a much easier to implement solution for C. If we change a character with another character having value greater than it, it's always best to change the first occurrence of the original character. And, if we change a character with another character having value less than it, it's always best to change the last occurrence of the original character. So we just have to check values of at most 31 strings, and print the maximum of those.

UPD: at most 21*

→ Ответить

11 месяцев назад, # ^ |

Did the same but initialised max with 0

→ Ответить

pedrosorio

11 месяцев назад, # ^ |

+11

So we just have to check values of at most 31 strings, and print the maximum of those

According to your observation, given a pair (original -> modified), there is only one string that needs to be checked.

There are 5 different characters, and each one can be modified to 4, so shouldn't it be at most 5*4 + 1 = 21 strings?

→ Ответить

shaurya_upd

11 месяцев назад, # ^ |

Used the same implementation but getting wrong answer on test 10. Not able to find mistake. mysolution

→ Ответить

_Dimpal_

11 месяцев назад, # ^ |

← Rev. 2 →

ans can be negative, you shouldn't initialise it with 0.

 int ans=0;
 ans=max(ans,call(s));

change this to

 int ans=call(s);

→ Ответить

shaurya_upd

11 месяцев назад, # ^ |

Thanks

→ Ответить

GTR.3910

11 месяцев назад, # ^ |

← Rev. 2 →

+12

Can't wrap my head around the observation.

Consider this testcase: CCBCEB

Changing B to D, wouldn't it be better to change the last occurrence in this case?

→ Ответить

11 месяцев назад, # ^ |

That's exactly what I want to ask. Seems that the greedy algorithm is not rigorous enough.

→ Ответить

MridulAhi

11 месяцев назад, # ^ |

← Rev. 4 →

+12

Yeah you're right, it should be the first occurrence of the character where changing the character results in a positive value for the character. Not sure how I overlooked this during contest. The original algorithm still works though, because for such cases, it'll be better to change the first occurrence to the character having max value which appears after it in the original string, which is luckily considered.

→ Ответить

Scyther_07

11 месяцев назад, # ^ |

I believe that increasing the first occurrence gives you the best answer. Increasing the later occurrence will give you atmost the same answer as before but it would not be any better for sure. Like in your example changing the 2nd B to D does not give you a better solution than changing the first B to D.

→ Ответить

https://codeforces.com/contest/1841/submission/209597116

11 месяцев назад, # ^ |

How about CEC. changing the 2nd C to D is absolutely better than changing the 1st one to D.

→ Ответить

Scyther_07

11 месяцев назад, # ^ |

Oh, didn't think about this one :(

→ Ответить

aditya0610

11 месяцев назад, # ^ |

But in this example we can change 1st C to E EEC

→ Ответить

LeonardSchulman

11 месяцев назад, # ^ |

I did it slightly differently but the implementation might be cleaner for some.

Basically, realize that you can reduce the problem to

make a new list of intervals that consists of pairs of intervals in the original array that have nonempty intersection, merged. You can do this in O(n^2), and multiple versions of the same array do not matter (e.g. the new list can have duplicates).
solve the "maximum # of disjoint interval problem" on this new list of intervals
your answer is n — 2 * # of disjoint intervals you found in step 2.

→ Ответить

FO7

11 месяцев назад, # ^ |

← Rev. 3 →

sum[t][i]=contribution of s[1...i] if s[i+1]==t and s[i+2....n] doesn't exist.

lets calculate sum[t][i];

intialise cnt['A']=0,cnt['B']=0,cnt['C']=0,cnt['D']=0,cnt['E']=0;

sum[t][i]=sum[t][i-1] here sum[t][i-1] is the contribution of s[1....i-1] if s[i]==t.

if(s[i]<t) sum[t][i]-=value(s[i])

but if (t at (i+1)th position < s[i]) means that bec u added sum[t][i-1] at there but at the ith place bigger element was there hence therefore for all 'A'<=u<= 'E' and u>=t && u<s[i] which were accounted as positive in sum[t][i-1] now need to be subtracted and make cnt[all need to be subtracted for whom s[i] is the greater just next greater element]=0 now ..

recurse

→ Ответить

FO7

11 месяцев назад, # ^ |

← Rev. 2 →

also one more thing dp states are just 5*2e5 ...when ever u see such things try to make dp .in this way the problem is very standard dp otherwise greedy makes the job even simple ...

one more approch that i think will work:

we can construct 5 multisets ...set a ,set b,set c,set d,set e;

we have an algorithm named as next greater element by stack ds.use it to find next greater element of each .

→ Ответить

FO7

11 месяцев назад, # ^ |

my subbmission with that

→ Ответить

tgp07

11 месяцев назад, # |

That feeling when you solve a problem right after the contest is the worst.

→ Ответить

aksnaresh

11 месяцев назад, # ^ |

first time bro

→ Ответить

ayush_n

11 месяцев назад, # |

← Rev. 2 →

Can any body tell me why my Solution is wrong for Problem B https://codeforces.com/contest/1841/submission/209462711

→ Ответить

aksnaresh

11 месяцев назад, # ^ |

see for test case 3 7 9 5 6 output : 11100 if you pass this test case and sample test cases then most probably your solution would be accepted

→ Ответить

bananasaur

11 месяцев назад, # |

+37

I managed to bruteforce C by checking every possibility at every position and efficiently calculating the updated string value, did anyone else do the same?

→ Ответить

karthikeya09

11 месяцев назад, # ^ |

Yes

→ Ответить

demadog

11 месяцев назад, # ^ |

Did the same but getting wrong on test 3.

→ Ответить

greedy logic and easy implementation for C

11 месяцев назад, # ^ |

Take a look at Ticket 16878 from CF Stress for a counter example :)

→ Ответить

puspendra_09

11 месяцев назад, # ^ |

Yes

→ Ответить

Rudro25

11 месяцев назад, # ^ |

can u plz explain your idea ?

→ Ответить

elizabeth_zou_fanboi

11 месяцев назад, # ^ |

← Rev. 2 →

-7

if we are incrementing a character from x to y, do it only for the first occurrence of x and if we are decrementing a character from x to y, do it only for the last occurrence of x.

PS: I didn't implement the above algo and implemented a different algo which took me an hour in the contest

→ Ответить

target-specialist

11 месяцев назад, # |

Can anyone tell me what is test case 9 in Problem C? I am not able to figure out where my code is giving wrong output.

→ Ответить

K_StA

11 месяцев назад, # ^ |

I suppose that is S = "D........DE". I got it wrong too.

→ Ответить

saikumarailwar9

11 месяцев назад, # |

-8

Can anyone tell me why my code fails for problem B... 209470922

→ Ответить

danish_droid

11 месяцев назад, # ^ |

← Rev. 2 →

Consider this test case : q = 8 and array = [1 1 8 8 2 3 8 3] Your output: 11111000 Actual ans : 11110010

→ Ответить

saikumarailwar9

11 месяцев назад, # ^ |

Hey really thank you so much.. Almost I got messed up with all possible unwanted testcases... U given a great testcase..

→ Ответить

aqua4

11 месяцев назад, # |

Can hacks affect penalty time?

→ Ответить

vgtcross

11 месяцев назад, # ^ |

No. In EDU, Div.3 and Div.4, i.e. contests with an open hacking phase, succesful hacks don't give any extra score and unsuccesful hacks don't give any penalty.

→ Ответить

ShivanRawat19

11 месяцев назад, # |

-8

Can someone please review my D submission. I just want to know can we optimize it and get the correct solution using this approach https://codeforces.com/contest/1841/submission/209448066

→ Ответить

Synaptic_Savant

11 месяцев назад, # |

Amazing set of problems.

→ Ответить

shaurya_upd

11 месяцев назад, # |

Does anybody know what is testcase 10 for C?

→ Ответить

Dhruv_Singh_Negi

11 месяцев назад, # ^ |

← Rev. 2 →

For me It was The Testcases In which ans can be negative

→ Ответить

i_pranavmehta

11 месяцев назад, # |

Amazing contest! If you guys feel stuck on any of these problems (Problem A, Problem B, Problem C, Problem D), Please checkout this video editorial on Youtube here

→ Ответить

BadalArya

11 месяцев назад, # ^ |

Thank you for the video sir.

→ Ответить

aneesh2002

11 месяцев назад, # |

The best feeling i got today was when my solution for C was accepted at 1:59:54 :)

→ Ответить

abracadabra

11 месяцев назад, # |

Can someone tell me what is wrong with my solution??? https://codeforces.com/contest/1841/submission/209481347

→ Ответить

K_StA

11 месяцев назад, # ^ |

S = 'D....DE'. Your approach is to change some letter to E whereas this time it is optimal to change last E into D.

→ Ответить

Dontony

11 месяцев назад, # |

← Rev. 2 →

Hi can anyone help me to find a counter testcase where my code gives runtime error. Got runtime error on test 3 and couldn't find the fix till now. Link:- https://codeforces.com/contest/1841/submission/209481108

→ Ответить

https://codeforces.com/contest/1841/submission/209495964

11 месяцев назад, # ^ |

Take a look at Ticket 16893 from CF Stress for a counter example.

(Each string in the input is of length 129 or 130, and only contains the letter "A").

→ Ответить

Bucketsmith

11 месяцев назад, # |

What's the technology used in F? I figured out the goal is to maximize $$$(\sum a - \sum b)^2 + (\sum c - \sum d)^2$$$ but i don't know how and seems LGMs' solutions all involved in vector and convex hull things.

→ Ответить

shadow9236

11 месяцев назад, # ^ |

+29

https://math.stackexchange.com/questions/2481720/given-a-set-of-n-2d-vectors-find-subset-of-vectors-with-sum-length-is-the-gre Maybe this will help

→ Ответить

Bucketsmith

11 месяцев назад, # ^ |

Thank you now I understand how.

So much to learn...

→ Ответить

-1e11

11 месяцев назад, # ^ |

This one uses a similar trick and may be treated as an exercise(?)

→ Ответить

Bosscoder

11 месяцев назад, # ^ |

-8

0-1 knapsack , i got tle with recursion though

→ Ответить

Prime_uwu

11 месяцев назад, # |

Can you guys tell where my code is wrong for B[submission:https://codeforces.com/contest/1841/submission/209450341]

→ Ответить

Tagl

11 месяцев назад, # ^ |

Looks like you might get wrong answer if the first element to break the increasing order is larger than the first element of the array.

Input:

1
1 9
3 7 7 9 4 4 6 3 4

Correct output:

111100010

→ Ответить

Prime_uwu

11 месяцев назад, # ^ |

Thank you soo much brooooo

→ Ответить

priyanshu.p

11 месяцев назад, # |

← Rev. 2 →

+29

Problem F (same solution): Link

where xi = b - a, yi = d - c

→ Ответить

Tahsin13

11 месяцев назад, # |

Can't you do D in O(nlogn) using RMQs? Should've switched C and D or make n = 2*10^5 in D. Then again it's edu so it doesn't matter as much.

→ Ответить

induk_v_tsiane

11 месяцев назад, # ^ |

You could using Segment Tree Beats

→ Ответить

jeal0uspengu1n

11 месяцев назад, # ^ |

Wouldn't that be a bit difficult for a Div2D?

→ Ответить

induk_v_tsiane

11 месяцев назад, # ^ |

It absolutely would, I am just saying that there exists an O(NlogN) solution in D.

→ Ответить

coderdhanraj

11 месяцев назад, # ^ |

A greedy way to solve problem D in O(NlogN) here by MeetBrahmbhatt.

→ Ответить

Miraz173

11 месяцев назад, # |

← Rev. 2 →

for this submission, my pc and ideone.com shows right output, but in cf, a completely different output is shown. can someone pls point out the problem?

→ Ответить

Chifwin

11 месяцев назад, # ^ |

You should initialize k with some value (maybe with n-1), otherwise there is undefined behavior and only compiler decide, what to do.

→ Ответить

Miraz173

11 месяцев назад, # ^ |

exactly the solution. accepted. tnx.

→ Ответить

ShivanRawat19

11 месяцев назад, # |

Please can someone review my code, like what else can I do, and is this approach correct. Please https://codeforces.com/contest/1841/submission/209448066

→ Ответить

HelloFromUnknown

11 месяцев назад, # |

← Rev. 2 →

I am getting TLE in the test case 5 for this solution of the problem c. I have tried a DP solution.

I am not able to get why this solution is giving TLE. I think the time complexity of this solution is O(2e5* 10) or O(N*10). Since here the state is of order: O(N*10) and the transition is of order O(1).

Similarly I am also getting Segmentation Fault when I have run this solution on some random test consisting of string having length nearer to 1e5 on my local system.

The approach, I have used is something like this: For the dp the states were: ind , pos

The first state(ind) is for the index and the another state(pos) is finding two things at any index.

The first thing(last) is the last character occurred till now from the ind+1 to index n-1 and, The second thing(st) is to tell whether we have placed 'E' character or not in some higher index then this index earlier or not.

So over all, I can say: dp[ind][pos] => this will tell me the largest sum I am able to make from the index 0.. to till index ind when the last occurrence maximum alphabet is:'A' + a%5; This last occurrence is from the index ind+1 to index n-1.

So in the recursive function I just try to check If i am able to assign the character 'E' to my current index or not. If I can assign to current character then I will try to get the solution for both the cases when I have assigned to current index and when I have not. and taking maximum of them will be my answer.

If I can not assign then I will just find the value of current character value and try similarly for other lower indexes.

→ Ответить

vgtcross

11 месяцев назад, # ^ |

You call the recursive function is called to calculate the dp state dp[ind][pos], but the return line is

return dp[ind][st] = ans;

This means that the state you're trying to calculate doesn't get stored at dp[int][pos], meaning that successive recursive calls to the same state will not utilize the already calculated dp values, which leads to TLE.

Fixing this gave me WA9. Here is a case where your code fails:

Input:
1
DDDDDDDDDDDDDDDDDDDDDDDDE

Expected Output:
25000

Your Output:
-3000

Explanation: Change last E into D.

→ Ответить

HelloFromUnknown

11 месяцев назад, # ^ |

Thank you very much. I got your point where I made the mistake. I have one more doubt, if you can help me in that reference also it will be really helpful. After correcting the mistakes you pointed out I tried it on codeforce system and it got accepted(link), but I am getting Segmentation Fault when I run that solution on some random test consisting of string having length nearer to 1e5 on my local system. So there will be some problem in my system, can you tell me what can be that?

→ Ответить

Shubham-V

11 месяцев назад, # |

+25

There could be a fun twist to Problem (A):

In every turn the players choose exactly 2 equal numbers and replace them with their sum. They start with $$$n$$$ $$$1(s)$$$ and Alice goes first. The player with all numbers different in their turn wins.
Figure out who will win.

Solution

→ Ответить

IllegalRazer

11 месяцев назад, # ^ |

← Rev. 2 →

I misread the question as this and actually submitted it before I realised that it is wrong: 209389602

→ Ответить

hartiksalaria

11 месяцев назад, # |

In problem C, is it possible to have an answer < 0?

→ Ответить

Dhruv_Singh_Negi

11 месяцев назад, # ^ |

← Rev. 3 →

Yes, See test case 10,Many D and 2 E at last

→ Ответить

hartiksalaria

11 месяцев назад, # ^ |

change last E to D, but i think if specifically answer = -1 is possible than my solution Submission and many other solutions can be hacked as using dp[i][j][k] != -1 is not safe here.

→ Ответить

Dhruv_Singh_Negi

11 месяцев назад, # ^ |

Finding a Test Case which gives -1 exact is hard. Let's wait till the Final system Testing.

→ Ответить

user_user_user

11 месяцев назад, # |

← Rev. 2 →

One of my friend, kehuydiet800cf, has copied Problem C in recent contest, these codes look the same:

209470016 from kehuydiet800cf

209468826 from chhavirana8

I think they has copied each other or from one source.

→ Ответить

Muhammad_Aneeq

11 месяцев назад, # |

One of the toughest contest ever faced??

→ Ответить

the_coder_8297

11 месяцев назад, # |

← Rev. 2 →

Can anyone please help me to figure out... what wrongs in my logic for Problem D... it is giving me wrong answer for 5th test case... I had almost similar approach as others stated here... Any help will be appreciated!

Code Link

→ Ответить

https://codeforces.com/contest/1841/submission/209533875

11 месяцев назад, # ^ |

Take a look at Ticket 16894 from CF Stress for a counter example.

→ Ответить

the_coder_8297

11 месяцев назад, # ^ |

Thanks!

→ Ответить

CodeKar

11 месяцев назад, # |

How much time does it takes to update rating after finishing system testing?

→ Ответить

srijay

11 месяцев назад, # ^ |

+12

Lately in educational rounds it is taking 6-8 hours.

→ Ответить

eklavya_k

11 месяцев назад, # |

for C it was easy to come up with an idea but I found implementation was lengthy and error prone. Does someone have easy implementation for C?

→ Ответить

seriouslyFlawed

11 месяцев назад, # ^ |

this could use a bit of cleanup... but see if you can understand this: solution

→ Ответить

Dan4Life

11 месяцев назад, # ^ |

← Rev. 2 →

Here: 209534617

→ Ответить

eklavya_k

11 месяцев назад, # ^ |

Thank you

→ Ответить

sanidhyas3s

11 месяцев назад, # ^ |

I myself had C fail in system testing, mainly due to having messy code during the contest, I cleaned it up and this I feel is the best way to do it, more optimisations can be made but not really needed.

→ Ответить

rsingh2003

11 месяцев назад, # |

Can anyone please explain to me the approach for problem D. And if possible, please share a list of question to master DP.

→ Ответить

Sreedhar3210

11 месяцев назад, # ^ |

i did it a bit differently without dp, using segment trees

each time pair two intersectable segments, and it is always optimal that we should pair such intervals such that their combined range is more left wards

like say there are k intervals [l1,r1],[l2,r2],.....,[lk,rk]

and let the combined range of paired intervals be [l,r]

we should pair such intervals with minimum r, then remove all the intervals with intersects with this range and repeat the process

you can take a look at my submission : 209523466

→ Ответить

Mirali777

11 месяцев назад, # ^ |

My solution: consider all pairs of segments. If they intersect than you can make a new segment by uniting these segments. Put all these "pair-segments" in a set. Then observe a new problem: you need to find the maximum disjoint subset of this set of "pair-segments". It can be done with dp with coordinate compression for example. The answer will be n — 2*(size of maximum subset)

→ Ответить

TselmegKh

11 месяцев назад, # ^ |

It can be done with greedy too:

From the "pair-segments", sort by the end point of intervals and take from the first, if possible.

Submission for the implementation: 209554396

→ Ответить

Mirali777

11 месяцев назад, # ^ |

Yes, it's better

→ Ответить

Dan4Life

11 месяцев назад, # ^ |

It's CSES Projects with 1 extra step.

→ Ответить

ETO_leader

11 месяцев назад, # |

← Rev. 2 →

+34

I found a small bug in tourist's code!

In the code of his Problem E

He used int where long long should have been used

Here is a python code to make a hack data

import random as rnd
N=200000
print("1\n200000")
for i in range(N):
    if i%3:print(0,end=' ')
    else:print(N,end=' ')
print()

The correct output is 13333200000

But tourist's output is 448298112

→ Ответить

toniskrijelj

11 месяцев назад, # ^ |

+27

hacked

→ Ответить

ETO_leader

11 месяцев назад, # ^ |

So how can I hack a submission?

→ Ответить

toniskrijelj

11 месяцев назад, # ^ |

Go to standings, double click the submission and press "hack it!".

→ Ответить

Lushaojie

11 месяцев назад, # |

Hope to release tutorial earlier.

→ Ответить

Prime_uwu

11 месяцев назад, # |

whats the difference between EDU rounds and simple DIV 2?

→ Ответить

11 месяцев назад, # |

When will the editorial be released?

→ Ответить

BigBadWolf

11 месяцев назад, # |

← Rev. 2 →

can someone explain me dp approach for problem C?

→ Ответить

kkd_6969

11 месяцев назад, # |

can someone tell me how to do problem C with DP

→ Ответить

noobiesAG

11 месяцев назад, # ^ |

← Rev. 2 →

-11

I have made a detailed video (its in hindi language) to solve problem C using different approaches.
Video link : link
Let me know if it helps you.

→ Ответить

BigBadWolf

11 месяцев назад, # ^ |

understood dp for problem C

→ Ответить

saketkumarsingh

11 месяцев назад, # |

Can someone please tell me why my code is failing in D [submission:209540485 Jun/13/2023]

→ Ответить

saketkumarsingh

11 месяцев назад, # |

Can someone please tell me why my code is failing in D 209540485

→ Ответить

11 месяцев назад, # ^ |

Take a look at Ticket 16879 from CF Stress for a counter example.

→ Ответить

ayush_n

11 месяцев назад, # |

Can anybody explain me why my code is Showing MLE on test 6 https://codeforces.com/contest/1841/submission/209499231

→ Ответить

wangxiwen

11 месяцев назад, # |

+20

Finally I became master in this round! And this time I got the highest rank of all Div. 2 round.

→ Ответить

kshqsz

11 месяцев назад, # ^ |

congratulations

→ Ответить

Ice_teapoy

11 месяцев назад, # |

In question E, I do not understand that the answer to the fourth example is 4

4 2 0 3 1 10

Can someone help me?

→ Ответить

Ice_teapoy

11 месяцев назад, # ^ |

n=4

a={2,0,3,1}

m=10

→ Ответить

Sreedhar3210

11 месяцев назад, # ^ |

one possible arrangement could be :

B 9 B B

B 8 B 10

1 2 B 7

3 4 5 6

i think you have misread the question that first a[i] cells are black in ith column not ith row

→ Ответить

Ice_teapoy

11 месяцев назад, # ^ |

Thank you very much :D

→ Ответить

Jack_sparrow_06

11 месяцев назад, # |

Could anyone tell the solution for the Problem C? I tried prefix and suffix sum and got WA :( 209557678

→ Ответить

taotianyi0103

11 месяцев назад, # |

!!!

→ Ответить

Ashis2512

11 месяцев назад, # |

← Rev. 2 →

i was caught for plagiarism in problem C although i did not cheat from any source and completly coded the solution by myself , still but due to the form of question instead of writing the code in main function , in one function i assigned the values of a,b,c,d to 1,10,100,1000 respectively and calculated the sum in another function . Anyone who would have thought of this logic would have coded the solution in similar way. i req MIKE to look upon this situation . As i am innocent

→ Ответить

GetRekt

11 месяцев назад, # |

← Rev. 4 →

sorry

→ Ответить

GetRekt

11 месяцев назад, # ^ |

← Rev. 3 →

sorry

→ Ответить

NegativeElo

11 месяцев назад, # ^ |

← Rev. 2 →

sorry

→ Ответить

streetcodec

11 месяцев назад, # |

Your solution 209461430 for the problem 1841B significantly coincides with solutions marrineha/209439975, Kundan01/209444867, IshaanGaba97/209458276, streetcodec/209461430, anujXthunder/209462090. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

This is the first time I am ever getting such a message, so I really don't know what do to. I gave a contest after a long time, and I feel B part was simple logic. I was missing certain test cases when I submitted the code previously. Then I just cleaned up everything and wrote the code in another code editor which was more familiar to me. And then I just copy pasted that onto the submit code tab but red dots appeared at a start of many lines, so I removed them all, messing my usual indentations. I think my code could have been compromised or it could be pure coincidence. I have my know variable names, I am explain and defend and logic, and also give my thought process A to Z. I request the competent person to not penalize me for some coincidence. I am sorry, I will only use CodeForces editor from now on!

→ Ответить

Untitled_geek306

11 месяцев назад, # |

← Rev. 2 →

I got a message for plagiarism in D, but I didn't cheat. The comparison operator used was inspired by the solution of a problem on leetcode. here . And the rest of the algo was the same, It just needed to sort and iterate the sorted 2d vector with maintaining the check and breaking with the help of the check. Please can you look into it MikeMirzayanov.

→ Ответить

engineering_guy

11 месяцев назад, # |

I got a message that Attention!

Your solution 209453390 for problem 1841B significantly coincides with other solutions submitted by other users.

I want to convey that it's a coincidence only. I have used the same logic which I was using in the previous submission and had made recurrent submission also by changing it, but it did not pass. Then I wrote the code from scratch by clearing previous code, but with the same logic and by giving meaningful names to variables so, I could trace them well. I can explain the logic from scratch and build it. I request the codeforces team not to penalize me for some false positives that have been generated.

→ Ответить

Krishna_2208

11 месяцев назад, # |

← Rev. 2 →

a similar question approach for 1841-D is in Interviewbit

→ Ответить

tanukool

11 месяцев назад, # |

← Rev. 2 →

Please help with “Your solution 209416596 for the problem 1841A significantly coincides with solutions theSSS/209391885, tanukool/209416596.”

The only code I used from the common source is for dealing with IO which is from USACO guide. Other than that the solution is my own and it is actually very simple by the nature of the problem so I guess there might be room for collision. Please reconsider this blame.

Edited: Many people got the same solution with similar coding style except it is c++ (e.g. 209387876).

→ Ответить

knockcat

11 месяцев назад, # |

Grinding till I do not make myself comfortable with solving problem C.

→ Ответить

divyanshgupta351

11 месяцев назад, # |

Attention!

Your solution 209459214 for the problem 1841B significantly coincides with solutions .....

The problem B was quiet easy and there could be multiple people with the same logic and hence coinciding codes, also I had tried the question once and missed by a slight edge case due to which I continued with problem C but at the end I again tried B and made some changes in the the solution and it got an AC. All I want to say is that in such an easy problem there is quiet a chance that codes may coincide. I request Codeforces to look into this matter and do the needful.

→ Ответить

Dev_PRTP

11 месяцев назад, # |

← Rev. 3 →

→ Ответить

silenttkillerr

11 месяцев назад, # |

Any counter test for this code of C

→ Ответить