CodeCraft-22 and Codeforces Round #795 (Div 2.)

2 года назад, # |

+141

Since this event is sponsored by EA, how many dollars needed to unlock problem B?

→ Ответить

shriganesh83

2 года назад, # |

Hows is this made possible , i mean the organizing and stuff

→ Ответить

oversolver

2 года назад, # |

+58

orange

→ Ответить

lbntxdy

2 года назад, # ^ |

$$$\color{red}{\text{orange}}$$$ !

→ Ответить

Rudro25

2 года назад, # ^ |

orange

→ Ответить

bruh09273

2 года назад, # ^ |

+19

orange

→ Ответить

dukhi_insaan

2 года назад, # ^ |

orange

→ Ответить

KunalSin9h

2 года назад, # ^ |

+52

"$$$\; \; \; \; \; \; \; \; \;\; \; $$$"

→ Ответить

2 года назад, # ^ |

orange

→ Ответить

ysislm

2 года назад, # ^ |

Orange

→ Ответить

k1ngash

2 года назад, # ^ |

orange

→ Ответить

b4nanacream

2 года назад, # ^ |

orange

→ Ответить

divad

2 года назад, # |

Hope to see brilliant problems, hope new colors for all

→ Ответить

ZimbabweGod

2 года назад, # ^ |

+59

oh god no not pupil again

→ Ответить

flavius_nebunu

2 года назад, # ^ |

We hope you get blue

→ Ответить

beethoven97

2 года назад, # ^ |

we hope you get black

→ Ответить

BreadsWithCheese

2 года назад, # ^ |

We hope you get orange

→ Ответить

abhinavsingh15682

2 года назад, # ^ |

lol I guess

→ Ответить

Zeardoe

2 года назад, # |

+26

Why only Indian?

→ Ответить

rahulgoel

2 года назад, # ^ |

+43

The prizes are only for Indian participants to avoid logistic issues faced during international shipping.

→ Ответить

Phoenix76

2 года назад, # |

Hope some positive rating change. Have become pupil from expert in the past few contests.

→ Ответить

guptamanav422

2 года назад, # |

+34

Namaste Codeforces!, Great to see the Indian contest

→ Ответить

mircea_007

2 года назад, # |

+82

Time to change my profile country to India.

→ Ответить

guptamanav422

2 года назад, # ^ |

← Rev. 2 →

-32

[DELETED]

→ Ответить

SirPh

2 года назад, # ^ |

+127

→ Ответить

Dhafin

2 года назад, # |

-14

Done

→ Ответить

dukhi_insaan

2 года назад, # |

← Rev. 3 →

-93

upvote or bad luck for this contest

→ Ответить

Miyano_Shiho

2 года назад, # ^ |

Well, well, well.. how the turn tables

→ Ответить

ill_us_in

2 года назад, # |

+48

Tis gonna be crazy..IIIT HYD (One of the best institutes in INDIA ) <3

→ Ответить

2 года назад, # ^ |

-49

One of the best? Seriously bro? Its undoubtedly the best one

→ Ответить

Ghosted

2 года назад, # |

← Rev. 3 →

+29

Although this is an Indian game, I don't think the following conditions are very reasonable...

Random 10 from top 100 (ranks 11-100) Indian participants.

Can players from other countries also participate?

→ Ответить

amul_agrawal

2 года назад, # ^ |

+30

Hey!

I am really sorry. This year our logistics allow us only to deliver T-shirts within India. For future years, we will try our best to bring international prizes too.

→ Ответить

Ghosted

2 года назад, # ^ |

+17

OK, that's understandable.

→ Ответить

Agnimandur

2 года назад, # |

← Rev. 2 →

Hello amul_agrawal To count as an Indian participant, do you have to live in India, or simply be of Indian heritage?

→ Ответить

amul_agrawal

2 года назад, # ^ |

+33

Hey!

Thank you for asking this, I realize that the prize distribution which is written in the post is indeed a little unclear.

The purpose of giving T-shirts to Indian participants only is to avoid the logistic issues that we have to face during international shipment. Hence, by the Indian participants, we mean the people who have a home in India, so that we can deliver the T-shirt there. People who have their Country set to India in their CF profile will qualify as Indian participants.

Apologies for this confusion. I will update the blog soon with this detail.

→ Ответить

MiceMirzayanov

2 года назад, # |

+74

on account of the overwhelming interest of competitive programmers to avail this round's T-shirt, here is a helpful link.

→ Ответить

OmarWae1

2 года назад, # |

It is the time to see my new color wish me luck (:

→ Ответить

2 года назад, # ^ |

-25

That's what she said

→ Ответить

JEE_MAIN_LOOSER

2 года назад, # |

Very Excited for this Round !!

→ Ответить

2 года назад, # ^ |

-27

That's what she said

→ Ответить

Saurabh_059

2 года назад, # |

Expecting a good quality ques and super excited for the round.

→ Ответить

yoyobunt

2 года назад, # |

wanna hit specialist so bad wish me luck

→ Ответить

JEE_MAIN_LOOSER

2 года назад, # ^ |

Becoming specialist today means speed-forcing A,B,C. Let's see if you can?? Hope for the best . Prepare for the worst

→ Ответить

_Fahd_

2 года назад, # |

The scoring distribution?

→ Ответить

rohitchak

2 года назад, # |

How's The Josh guys?

→ Ответить

sumit21

2 года назад, # ^ |

High Sir!!

→ Ответить

just_fun

2 года назад, # |

all the best guys, hope to see your colour change

→ Ответить

2 года назад, # ^ |

-12

No god please no, I don't want to be specialist again

→ Ответить

Minh

2 года назад, # |

-9

Very interesting D

→ Ответить

onlyerror

2 года назад, # ^ |

hint?

→ Ответить

2 года назад, # ^ |

Problem requires multiple subtask.

Subtask 1 hint: In which subarrays element at index i will be the maximum

→ Ответить

Minh

2 года назад, # ^ |

+11

define l[i] as the max index such that l[i] < i and a[l[i]] > a[i], r[i] as the min index such that r[i] > i and a[r[i]] > a[i]. Then for each i you need to find indexes l' and r' with the max sum of a[l';r'] such that l[i] <= l' <= i and r[i] >= r' >= i.

→ Ответить

1e18iq

2 года назад, # |

lmao. Was C so easy that so many people solved it? Implementation seemed so difficult.

→ Ответить

barun511

2 года назад, # ^ |

Just move a 1 to the right if you can, and then to the left if you can.

→ Ответить

steve004

2 года назад, # |

Can someone please tell me what's wrong with my code for problem C? https://codeforces.net/contest/1691/submission/159053938

→ Ответить

onlyerror

2 года назад, # ^ |

← Rev. 2 →

testcase

ans is 10 but you code gives 11

→ Ответить

onepunchAC

2 года назад, # |

+62

I think we need to block meggage when ongoing contest. Ban++!

→ Ответить

2 года назад, # ^ |

← Rev. 2 →

I started codeforces recently and got super mad at cheaters but now I stopped caring. It happens every contest man. That’s why no one responds anymore. There are too many cheaters to do manual check, and they just find ways to trick the plagiarism detector anyway. It stops matter once you solve D or above

→ Ответить

2 года назад, # ^ |

If there is an opportunity to ban a sussy baka cheater, then why not to use it?

→ Ответить

2 года назад, # |

boring ABC, D classic segment tree. Thanks for the round!

→ Ответить

ashu_3916

2 года назад, # ^ |

did without segment tree code

→ Ответить

2 года назад, # ^ |

how?

→ Ответить

Fuehrer

2 года назад, # ^ |

← Rev. 2 →

1-> there cannot be 2 consecutive positive values

2-> replaced consecutive negative values with their sum as a whole they don't change the result

3-> not considering the values which are zero

4-> only checking till 3 length subarray by contradiction we can prove that
if more than 3 lengths give us no we can do it in 3 or less than 3 lengths (but I checked till 50).

→ Ответить

2 года назад, # ^ |

4 -1 -1 4. How can we do in 3 length subarray? Is there something I am missing.

→ Ответить

2 года назад, # ^ |

He said that he is replacing all the consecutive negative numbers with the sum of them. Anyway, that approach fails for this:
1
9
12 -39 44 -36 30 -14 8 -9 18

I had to submit it again and lost around 400 points, also I could have completed E if I had not seen that test case after submission.
Very unlucky day for me :(
Still not sure whether my solution for D will pass or not

→ Ответить

2 года назад, # ^ |

Wrong answer on test case 65 :(

→ Ответить

2 года назад, # ^ |

I have written a brute force method in D checking all the positive position pair wise which is n^2 but is still passing.

→ Ответить

WAtoAC2001

2 года назад, # ^ |

I have hacked your submission now. I wonder how they missed to add this basic case of alternating 1 and -1 in system tests.

→ Ответить

2 года назад, # ^ |

I have even messaged them to add the test case which I have posted in the above comment. But still, they didn't add. Is it not allowed to add any test case during the contest?

→ Ответить

sam07a

2 года назад, # ^ |

https://codeforces.net/contest/1691/submission/159062928 Hack this

→ Ответить

freehandle

2 года назад, # ^ |

How to hack after the contest?

→ Ответить

2 года назад, # ^ |

only >=1900 rated people can hack after contest

→ Ответить

2 года назад, # ^ |

Yes, it's a basic test case and they should have added it. I have asked the setter to the add the case. I think it will be reevaluated.

→ Ответить

kobebryan9

2 года назад, # ^ |

Can explain more on how this work? like if the testcase is 5 {-4 4} {-4 4}...(same for n times) 5, can it still be processed?

→ Ответить

AAK

2 года назад, # ^ |

I did it using a slightly modified Kadanes, where I checked if:

(Max sum till index) $$$>$$$ (Max element in subarray under consideration) $$$\forall$$$ $$$i$$$ $$$(a[i]>0)$$$

and then checked the same in reverse. I don't have a proof to why this worked, just intuition.

Code

→ Ответить

Mohamed_Hesham

2 года назад, # ^ |

← Rev. 2 →

Your code prints wrong answer for this test

6
10 -8 2 4 -8 10

→ Ответить

AAK

2 года назад, # ^ |

Damn, yeah you're right. I guess I was lucky.

→ Ответить

ashu_3916

2 года назад, # ^ |

← Rev. 5 →

lemma 1 : we should not have 2 consecutive positive integers
lemma 2 : consider 2 positive integers [a, b] which appear next in order in the array having a segment of negative integers between them whose sum is say p ie : a p b then max(a , b) >= a+p+b this we can check for all such segments.
lemma3 : consider 3positive integers [a, b,c] which appear next in order in the array having a segment of negative integers between them whose sum is say p1 , p2 ie a p1 b p2 c now among all the possible combination of order of max value of [a,b,c], we need to check for the case , where b is the smallest among all three. for other combination we can boil down back to lemma 2 (a p1 b , b p2 c) [you can do a little math ;)] so i checked for case of 3 numbers too
lemma 4 : n>3 positive integers can be broken into lemma3 then lemma 2 , so we don't need to check more .

hopefully doesn't give FST

→ Ответить

akshat_porwal

2 года назад, # ^ |

← Rev. 2 →

I also implemented the same but just missed the lemma3 point i.e. if b is min(a,b,c).

→ Ответить

ashu_3916

2 года назад, # ^ |

I got hacked

→ Ответить

d1tm3hcmus

2 года назад, # ^ |

I was thinking of using the maximum stack technique.

→ Ответить

2 года назад, # ^ |

Explain please

→ Ответить

I_Love_Hailee

2 года назад, # ^ |

← Rev. 3 →

How is D giving AC for some solutions with O(n^2) time complexity for other with completely similar logic

→ Ответить

2 года назад, # ^ |

← Rev. 3 →

Even i have a brute force method and it is giving accepted answer. 159061569

→ Ответить

Aquanox

2 года назад, # |

Approach for E?

→ Ответить

Omer223

2 года назад, # ^ |

← Rev. 2 →

Do a classic sweepline. The main observation is that if at some moment during the sweepline there are open intervals of both colors, then all those intervals will be in the same connected component. Therefore, if there's a moment with both colors present, it's enough to unite all active intervals, and keep the interval with largest right endpoint of each color. Notice that during each moment in the sweepline, the set of active intervals will be either unicolor, with each interval belonging to a different connected component, or both colors will have one active interval. Therefore, when encountering a new interval it's enough to unite it with all intervals of the opposite color, and the complexity will be $$$O(nlogn)$$$.

→ Ответить

Giselus

2 года назад, # ^ |

I like overkilling tasks, so here is my approach, but it's basically the same as previous answer. Let's create a segment tree, for every red segment we will add it to vectors of nodes covering this segment. So it's standard adding on range operation, instead of increasing some variable, we're pushing to vector. Now, for every blue segment iterate down the tree. When you're in some node, add edge to every red segment in this node, now all of them are connected, so it's enough to leave only one of them in vector.

Repeat this approach for blue segments stored in tree and queries for red vertices.

Now you'll get something like n * log(w) edges, where w is maximum coordinate of segments. So you can do standard DFS now.

→ Ответить

Aglaya

2 года назад, # ^ |

How do you store segments in the tree? the range of left and right ends is too big to pass memory limit

→ Ответить

Giselus

2 года назад, # ^ |

I believe it's called dynamic segment tree. Every operation you do on segment tree is just some pass from root. So we dynamically allocate nodes only when we try to reach them. You will need as well only n*log(w) memory for this. You can check my submission: https://codeforces.net/contest/1691/submission/159060219 And for constructing graphs on segment tree you can also check this nice problem: https://codeforces.net/contest/786/problem/B

→ Ответить

Aglaya

2 года назад, # ^ |

thanks :D

→ Ответить

Or_ion

2 года назад, # |

Approach for C??

→ Ответить

adamant

2 года назад, # ^ |

Just tedious casework...

        if(L && R && L + R <= k && cnt > 1) {
            cout << ans - 11 << "\n";
        } else if(R && R <= k) {
            cout << ans - 10 + !(L || cnt > 1) << "\n";
        } else if(L && L <= k && (R || cnt > 1)) {
            cout << ans - 1 << "\n";
        } else {
            cout << ans << "\n";
        }

Here $$$cnt$$$ is the number of $$$1$$$ bits, $$$L$$$ is the distance from the beginning to the first $$$1$$$ bit, $$$R$$$ is the distance from the last $$$1$$$ to the end. And if $$$cnt=0$$$, output $$$0$$$.

→ Ответить

Newtech66

2 года назад, # ^ |

I mean, it's also possible to brute force all possibilities if you're lazy. The result only depends on the first and last digits.

→ Ответить

lkjhgfertyul

2 года назад, # ^ |

sum is minimum only if there are 1's on both the end points, for example: 100001 is better than 010100. Just check for closest 1's to index 0 and index n-1 Also priority should be first 1 at n-1 index than at the 0th index

→ Ответить

2 года назад, # ^ |

Every element except 1st and last element contributes at ones place and tens place. Last element contributes only to ones place. First element contributes only to tens place

→ Ответить

abdzag

2 года назад, # |

GeeksForGeeks have working challenge (impossible) I tried this code for but couldn't get it to work.

→ Ответить

anujdhillxn

2 года назад, # |

← Rev. 2 →

+28

The most ridiculous mistake I ever made was in today's E. I used the following function to check whether two intervals are intersecting.

Function

bool intersect(array<int, 3> &p1, array<int, 3> &p2)
{
    if (p1 > p2)
        swap(p1, p2);
    return p2[0] <= p1[1];
}

The intervals are passed by reference, and therefore change the order of the intervals in the original array. Fml :)

→ Ответить

spookywooky

2 года назад, # |

For me A,B,C where simple to guess but hard to prove.

→ Ответить

2 года назад, # ^ |

B can be proven by noticing that if there's at least an element that's unique in the array, then you can't swap it with anything. Why? Swap with a smaller is disallowed, and swapping with a larger element is also not allowed, bc the larger element now has the smaller element. Then just swap indices with the same integers, a way to do it is in the example.

For C, any 1 that is not at 0th or n-1 index will add exactly 11 to the sum. So you just have to try to move a 1 to the back first, and then to the front.

→ Ответить

dleunji

2 года назад, # |

← Rev. 4 →

OMG. It was my first contest in codeforces and I totally failed. In Problem B, I made sections with each size. like [1, 1,][3, 3, 3] by searching with Two Pointers. And I flipped the idx in each section. In upper example, the answer will be [2,1][5,4,3].

Then I got WA in pretest 1. I'm really curious about Problem B.

Why my submission failed in Problem B?

→ Ответить

cleanser

2 года назад, # ^ |

Cuz if u flip the idx of a section with an odd amount of people, the middle person in the section has the same shoe as before. In ur example, person 4 gets his own shoe back.

→ Ответить

2 года назад, # ^ |

Bro read community guidelines. Don't post full code directly. Post in either spoiler or post link

→ Ответить

Your_Bunny_Wrote

2 года назад, # |

help pls https://codeforces.net/contest/1691/submission/159055446

→ Ответить

variety-jones

2 года назад, # ^ |

Failing testcase: Ticket 8946

→ Ответить

Your_Bunny_Wrote

2 года назад, # ^ |

why I can't use CF Stress?

An error occurred while downloading your submission. Probably Codeforces is down.

→ Ответить

ldyllic

2 года назад, # |

What did I miss for problem C? 159077051

Will be grateful for an explanation :)

→ Ответить

variety-jones

2 года назад, # ^ |

Failing testcase: Ticket 8941

→ Ответить

2 года назад, # ^ |

← Rev. 2 →

→ Ответить

variety-jones

2 года назад, # ^ |

Take a look at Ticket 9475

→ Ответить

lazy_loop

2 года назад, # |

solved D for the second time(last time got hacked). Hoping not to get fst today.

→ Ответить

shiro

2 года назад, # |

Start the goddamn system testing, I want to send my code.

→ Ответить

2 года назад, # |

Misread B, moved on. Failed C, moved on. Solved D in 20 mins. Went back to C, but still failed. Went back to B, and understood that I have misread it, yet failed again. What a round... I am quite confident about my solution for B (also for C but whatever), but I get WA in case 3... any help? 159066034

→ Ответить

akshaywairagade2

2 года назад, # ^ |

I think you have done mistake in case when total 1 count is 1. Try this 7 2 0000100

→ Ответить

2 года назад, # ^ |

My code for C gets output 1 for this input. I may have some other mistakes, although I don't understand why my code for B fails.

→ Ответить

notrandom

2 года назад, # ^ |

Case 3 of B is n=1

→ Ответить

2 года назад, # ^ |

-10

Yeah, and my code for n=1 has output -1, isn't this correct?

→ Ответить

bit_lower_bound

2 года назад, # ^ |

← Rev. 2 →

-10

ok i missed

→ Ответить

2 года назад, # ^ |

-10

But in the line right below, I fill ans[j]. I didn't go up to j because at index j I append i (wrap around).

→ Ответить

2 года назад, # ^ |

-13

I got it... I actually am retarded.... I have print instead of println and I misprint.

→ Ответить

2 года назад, # ^ |

wrong output format Expected integer, but "-1-1-12" found (test case 3)

→ Ответить

2 года назад, # |

Is problem F kidding? I think it's even easier than problem C,for which I will consider its difficulty as *1700.

And I also would like to know why I got TLE on pretest 2 (the given sample to which the answer is 849) at the first attempt (nothing wrong with it in my PC) , and after I add two "inline" ,I got an AC.I think it may be the judge's fault, not mine.

→ Ответить

ltc.groverkss

2 года назад, # ^ |

Your pretest 2 fails not because of the judge but seems like it's the compiler. You are probably running your code with no optimizations. Try adding -O1 (or 2,3). It segfaults. Exploring why this happens further.

→ Ответить

2 года назад, # ^ |

plz can you tell me more details about it? for example how i can add -O1(or 2,3),and why i haven't encountered any fault like this when solveing other problems before?

→ Ответить

ltc.groverkss

2 года назад, # ^ |

← Rev. 2 →

I'm not able to find the assembly to show you but the problem is that you use scanf("%d%d") instead of scanf("%lld%lld") (which clangd will warn you about :D). I'll try to find the exact assembly diff if I can, but this is the major problem.

The reason your second code passed is that you luckily used some other I/O way. inline is usually useless in the same file, compilers are now smart enough :D

→ Ответить

2 года назад, # ^ |

thank you for your help. I will look into it

→ Ответить

Aryan_raj_

2 года назад, # |

159066950 why i am getting mle on this code question b

→ Ответить

2 года назад, # ^ |

plz never use unordered_map.

→ Ответить

Aryan_raj_

2 года назад, # ^ |

-10

159039176 can u also tell me why i got runtime error on this code

→ Ответить

robostac

2 года назад, # ^ |

You always need to read all the input per test, even if you know the answer before it's all read. When n is 1 you return early and all the following tests will be read incorrectly.

→ Ответить

2 года назад, # ^ |

when n = 1 you should read the number $$$a_1$$$ .

for example, the input is :

2 1 5 3 1 2 3

then you will find that your code reads "n = 5" in the second test case.

→ Ответить

2 года назад, # |

-18

Problems were really very good and contest was very well balanced, Kudos to the problemsetters

→ Ответить

epicsaga

2 года назад, # ^ |

-18

Except problem C , it was not good

→ Ответить

2 года назад, # ^ |

why not?

→ Ответить

https://codeforces.net/contest/1691/submission/159019206

2 года назад, # |

Problem A: https://www.hackerrank.com/contests/coderush-nit-surathkal-2022/challenges/easy-transform

→ Ответить

RBurgundy

2 года назад, # |

← Rev. 2 →

+41

Cheesing D by just checking some of the intervals. Happy hacking!

EDIT: Hacked by tourist, I'm honored!

→ Ответить

shadow9236

2 года назад, # ^ |

← Rev. 2 →

You need to check all intervals [i .. j] where either a[i] or a[j] is the largest number in the interval

Someone hacked you before me :( Here is my testcase https://pastebin.com/6aBxXZuP

→ Ответить

Newtech66

2 года назад, # ^ |

I can't believe I got beaten to it by tourist because I somehow copied my testcase incorrectly. I'm so mad right now.

→ Ответить

aman282571

2 года назад, # |

← Rev. 2 →

For problem B can anyone tell me why this code exceeded time limit for test 30? this is O(n) solution. Link to the solution. https://codeforces.net/contest/1691/submission/159016521

→ Ответить

Penguin07

2 года назад, # ^ |

Don't use unordered_map.

→ Ответить

shadow9236

2 года назад, # ^ |

https://codeforces.net/blog/entry/62393

Don't use unordered map

→ Ответить

robostac

2 года назад, # ^ |

https://codeforces.net/blog/entry/62393

Unordered_map can be made very slow by carefully selecting certain input values.

→ Ответить

https://codeforces.net/blog/entry/62393

2 года назад, # ^ |

→ Ответить

carnation13_2

2 года назад, # |

← Rev. 2 →

I made the array smaller and RE on test 30 of problem B,that i can't go blue this time,f**k the fst!!!

→ Ответить

_Tatakae__

2 года назад, # ^ |

You would still, probably!

→ Ответить

I_Love_Hailee

2 года назад, # |

← Rev. 3 →

D was interesting Any simple solutions without segment tree ?

→ Ответить

catsareliquid

2 года назад, # ^ |

Not sure about the simple part but people are discussing it above

→ Ответить

HowtobeRed

2 года назад, # |

← Rev. 2 →

Isn't problem F too easy? The rerooting solution is so obvious, although the top rankings' solutions seem to be shorter.

→ Ответить

Igorjan94

2 года назад, # |

E is waaaay easier than D. One more confirmation that proper tactic is to "read all the problems"

→ Ответить

https://ideone.com/mnFtIx

2 года назад, # ^ |

+15

Nope, D has 4 times more solves than E. It's your personal opinion.

→ Ответить

Igorjan94

2 года назад, # ^ |

+24

Of course it's my opinion. But nobody knows how many solves it'd have if swapped with D: do not forget that majority solves A->B->...

→ Ответить

ScarletS

2 года назад, # ^ |

I thought so too

→ Ответить

gopi_ldce

2 года назад, # |

← Rev. 2 →

I think the test set for problem D are not strong enough because I just tried a brute force kind of solution and it passed.I would request to rejudge Solutions with strong test set.

Here is my solution : https://codeforces.net/contest/1691/submission/159082582

→ Ответить

Mahim

2 года назад, # |

← Rev. 2 →

159067765 this solution should be wrong. For test case:

100 -30 -20 50 -30 -20 50 -30 -20 100

It should give "NO". But the solution give "YES".

→ Ответить

Mahim

2 года назад, # ^ |

← Rev. 2 →

And a large test case like this pattern can hack a lot of submissions.

→ Ответить

Mohamed_Hesham

2 года назад, # |

← Rev. 2 →

This code for D got AC after the contest had finished, can anyone prove why it works?

→ Ответить

2 года назад, # ^ |

Its similar to Kandane's algorithm. I had thought of the same at first but thought and I still think that this should fail

→ Ответить

Mohamed_Hesham

2 года назад, # ^ |

I found a case that won't work:

6
10 -8 2 4 -8 10

→ Ответить

29logN

2 года назад, # |

← Rev. 2 →

+27

My brain during contest:

Spoiler (Problem C)

→ Ответить

Aquanox

2 года назад, # |

Noticed?

→ Ответить

2 года назад, # |

Is it allowed to add the test case by authors during the contest? Or only test cases which were used to hack is added automatically?

→ Ответить

wicked_knight

2 года назад, # |

-15

Hey amul_agrawal, akcube and others from the team.... The post says "It is rated for all people who are below yellow! (rating under 2100)"

However, after the contest, my rating has not changed... I assumed this was because solutions were not checked on main test cases yet, but that process is now complete.

I can see this contest under "Unrated Contests" on my profile... why is that so? I thought this was rated. It was a fantastic contest and I had a lot of fun trying my hand at the problems, thank you. It is not a problem even if it is unrated, I was just expecting it to be rated for me, since I am below 2100 rating.

→ Ответить

Submission 1 Submission 2 Submission 3

2 года назад, # ^ |

Have you checked your profile? It's already changed!

→ Ответить

br0hum

2 года назад, # |

1599. 1599!

→ Ответить

bobyao

2 года назад, # ^ |

Your solution of D is so amazing!

→ Ответить

jeal0uspengu1n

2 года назад, # |

← Rev. 2 →

Why these O(n^2) solutions pass? Is there any additional neat trick that will reduce the complexity?

UPD: okay 2 of them hacked, the last one's is still AC

→ Ответить

Serval

2 года назад, # ^ |

UPD2: The last one is hacked! :P

→ Ответить

Aravind

2 года назад, # |

Oh god! I'm getting nervous for A and it's setting up or spoiling my mood for the rest of contest based on whether pretests of it are passed or not.

→ Ответить

nirjhorJU

2 года назад, # |

-10

What is uphack? I still got AC after being hacked in problem D. Even the rating changed. I don't understand. Someone please explain if you know something. This my submission for D

→ Ответить

SixtyWithoutSchool

2 года назад, # ^ |

← Rev. 2 →

According to me the hacking is open even after the contest ends for those who have rating greater than 1900. Your code has passed the the testcase provided by the contest writers but there maybe some testcase on which your solution may give Wrong Answer or Runtime Error or Time limit exceeded on which your code got hacked.

Later these hacking testcases gets merged with the system testcases, so if you will try to submit the same code after some time you may get WA or TLE.

I am not sure of the rating changes though, according to me they will be updated after all solutions are re-judged.

→ Ответить

djm03178

2 года назад, # ^ |

No. Uphacking doesn't change contest result and rating changes. It is for adding test cases for future practice submissions or virtual submissions. It doesn't rejudge contest submissions.

→ Ответить

magga

2 года назад, # |

← Rev. 2 →

I am never rerooting again :')

Pain

void transferRoot(int i,int to){
    curr = sub(curr,mul(dp[i],sizeOfSubtree[i]));
    curr = sub(curr,mul(dp[to],sizeOfSubtree[to]));
    sumOfdp[i] = sub(sumOfdp[i],add(dp[i],sumOfdp[to]));
    dp[i] = add(dp[i],sumOfdp[to]);
    dp[i] = sub(dp[i],ncr(sizeOfSubtree[i],k));
    sumOfdp[to] = sub(sumOfdp[to],dp[to]);
    dp[to] = sub(dp[to],ncr(sizeOfSubtree[to],k)); 
    sizeOfSubtree[i] -= sizeOfSubtree[to];
    sizeOfSubtree[to] += sizeOfSubtree[i];
    dp[i] = add(dp[i],ncr(sizeOfSubtree[i],k));
    sumOfdp[i] = add(sumOfdp[i],dp[i]);
    dp[to] = add(dp[to],ncr(sizeOfSubtree[to],k)); 
    dp[to] = sub(dp[to],sumOfdp[i]);
    sumOfdp[to] = add(sumOfdp[to],dp[to]);
    sumOfdp[to] = add(sumOfdp[to],sumOfdp[i]);
    curr = add(curr,mul(dp[i],sizeOfSubtree[i]));
    curr = add(curr,mul(dp[to],sizeOfSubtree[to]));
}

→ Ответить

2 года назад, # ^ |

+29

nice profile pic and name bro.. only indians can have this much of creativity

→ Ответить

2 года назад, # ^ |

to get so many upvotes just say something about india and indian user will show their presence :)

→ Ответить

Aging1986

2 года назад, # ^ |

I dont think it needs so complicated transformation?

→ Ответить

magga

2 года назад, # ^ |

← Rev. 3 →

Yup, It can be reduced to half it's size. I maintained dp states in a little more detail than i needed

→ Ответить

Aging1986

2 года назад, # ^ |

I only kept the size of each subtree if the whole tree is rooted at 0, then do some calculation.

→ Ответить

2 года назад, # |

Indian students and colleges are organizing such contest . Great to see that indian education system is improving :) | but this will never happen in tier 3 :(

→ Ответить

shriganesh83

2 года назад, # |

how can one know if he/she has won the random tshirt between 11-100 rank, i am ranked 64 is there any form to fill? or way to know?, this is my first time so pls help.

→ Ответить