Codeforces Round #319

9 years ago, # |

-36

If it can be postponed for 24 hours, that will much better. Friday is not weekend. Go to school or go to work prevent us from getting up late, even though we participate in Codeforces Contest in the evening.

→ Reply

Zzyzx

9 years ago, # ^ |

+26

Please do NOT postpone it.

→ Reply

9 years ago, # ^ |

Of course it won't be postponed. I just complain about the time for me~ However, I am curious for the reason why you disagree with postpone?

→ Reply

I_love_Tanya_Romanova

9 years ago, # ^ |

+32

What about the fact that after moving it 24 hours forward it will clash with TC SRM?

→ Reply

9 years ago, # ^ |

+10

Oh......What a busy weekend!

→ Reply

prateek_jhunjhunwala

9 years ago, # ^ |

+16

I want to start doing TopCoder, but its awful interface discourages me as soon as I open the site. And its applet isn't that good too.

→ Reply

send_nodes

9 years ago, # ^ |

+17

You shouldn't worry about interface, but rather the problems. In general, topcoder problems have better english and more clear explanations, and the challenge phase is a rather interesting element.

→ Reply

duckladydinh

9 years ago, # ^ |

Do u know any tutorial about playing Topcoder? I have tried several times but still dunno how to start.

→ Reply

Gassa

9 years ago, # ^ |

Have you tried reading the official guide? It is a bit outdated but still conveys the idea.

→ Reply

Zzyzx

9 years ago, # ^ |

+34

Oh I have mentally prepared myself for this evening. :P

→ Reply

9 years ago, # ^ |

for me and a lot of contestants Friday is weekend :)

→ Reply

9 years ago, # ^ |

Why? Don't you need to go to school or work on Friday?

→ Reply

9 years ago, # ^ |

+39

In Egypt our weekend is (Friday & Saturday) not (Saturday & Sunday) :)

→ Reply

Shayan

9 years ago, # ^ |

In Muslim countries weekend is Friday

→ Reply

OmaeWaMouShenDeiru

9 years ago, # ^ |

Usually I tend to miss lectures that has CF rounds conflicting with them.

It certainly feels different and the rush is better :D

→ Reply

Sunnat

9 years ago, # |

-14

Thank you for contest, I think in this contest will be interesting and a lot of hacks. Sorry for my poor english

→ Reply

AClover

9 years ago, # ^ |

+13

Why do you think that there will be a lot of hacks?

→ Reply

t3rminated

9 years ago, # ^ |

+20

I like hacks , they save u getting system test failed.

→ Reply

AClover

9 years ago, # ^ |

I didn't say that I don't like hacks. I just wonder why he is in this thought..

→ Reply

t3rminated

9 years ago, # ^ |

this contest had more system test failed than hacks.. :(

→ Reply

Namnamseo

9 years ago, # |

Will the problems be sorted in an ascending order of difficulty?

→ Reply

Ahmed_Hussein_Karam

9 years ago, # ^ |

the statement in the post: "In order to increase the probability of finding that task, please read all of the problem statements" means alot

→ Reply

Xellos

9 years ago, # ^ |

I think it doesn't, since "that task" refers to "everyone will find a satisfying problem". The question wasn't if the problems will be sorted in ascending order of satisfying-ness.

→ Reply

Alhelal_01

9 years ago, # |

weekend or not weekend ,i hope contest will be running.

Because it is div2 round and it will happen after a long time.

→ Reply

MedalPluS

9 years ago, # |

Thanks for this holding this CF round and hope everyone can get good score!

→ Reply

AminAnvari

9 years ago, # |

I hope the problems will be short and to the point. Not with long stories.

→ Reply

nazaninnnnn

9 years ago, # ^ |

-23

But I hope The problems will be short and the point. Not with long stories.

→ Reply

Nezzar

9 years ago, # ^ |

+13

But I hope the problems will be short and intersting, Not with direct statement "please calculate something"

→ Reply

saurabhverma

9 years ago, # |

-30

Wish me positive contribution :P

→ Reply

daga

9 years ago, # |

looking forward for your first set of problems :D

→ Reply

send_nodes

9 years ago, # |

-8

Hope that more contests will be scheduled at 11:00 instead of 11:30

→ Reply

9 years ago, # |

+49

Time to lose red!

→ Reply

9 years ago, # ^ |

who know maybe time to get new max :)

→ Reply

9 years ago, # ^ |

← Rev. 2 →

Do you have any pointers on how to get out of green zone?

→ Reply

9 years ago, # ^ |

+30

Increase your rating to 1500+ :D

→ Reply

EKGMA

9 years ago, # ^ |

+41

Or probably decrease it to 1200- :D

→ Reply

9 years ago, # ^ |

No thanks EKGMA :p

→ Reply

9 years ago, # ^ |

← Rev. 3 →

+14

If you are heavily color-blind like me then you already look red!

→ Reply

OmaeWaMouShenDeiru

9 years ago, # ^ |

you have to solve at least A and B to stay at the blue zone.

Along with those, solve C and your chances to be purple are pretty high.

→ Reply

9 years ago, # ^ |

I hate A,B. And I suck at C,D. Its a viscious trap.

→ Reply

shank_punk

9 years ago, # ^ |

You did it :D Congrats.

→ Reply

9 years ago, # ^ |

Thanks! It feels good to see the progress as a color change.

→ Reply

9 years ago, # ^ |

Yay, I was right! :(

→ Reply

9 years ago, # ^ |

Hah, it seems we rise and fall together. If only C had 3-4 seconds instead of 2...

→ Reply

http://mirror.codeforces.com/contest/576/submission/12963316

9 years ago, # ^ |

← Rev. 3 →

I hope you never again use c++ streams, your C passes in under 1 second using printf...

→ Reply

9 years ago, # ^ |

NOOOOOOOOO

→ Reply

tweety

9 years ago, # ^ |

Or time to lose bottom yellow, after this revolution. :P

→ Reply

Ninjo

9 years ago, # |

hope understand from first time read :3

→ Reply

AClover

9 years ago, # |

← Rev. 3 →

+25

Did you notice that registration finishes as time contest starts not 5mins before...
P.S No That was an error I think? When I looked both times were same..

→ Reply

Vladik

9 years ago, # ^ |

Not anymore =(

→ Reply

m.khooryani

9 years ago, # |

Thanks to author!

contest was great

,how to solve "Modulo Sum"?

→ Reply

9 years ago, # ^ |

← Rev. 2 →

I used set, but might TLE. Saved all possible modulo remainders for each element, basically.

→ Reply

9 years ago, # ^ |

That's not enough. You need to combine each remainder with each remainder to get new remainders.

→ Reply

9 years ago, # ^ |

Yeah that's what I did. Instead of iterating over a 10^3 array, I used set, that's all. But sets have a huge constant associated with them, which is what is making me nervous.

→ Reply

9 years ago, # ^ |

And you can also combine the remainder with itself certain number of times. I cannot view the solutions yet, but I'd like to see how you solved that.

→ Reply

9 years ago, # ^ |

"And you can also combine the remainder with itself certain number of times." why?

→ Reply

9 years ago, # ^ |

← Rev. 2 →

For example,
3 3
1 1 1

→ Reply

electro

9 years ago, # ^ |

There was given sample test
6 6
5 5 5 5 5 5
So obviously, he must have considered that.

→ Reply

9 years ago, # ^ |

Actually, you can't sum one number more than once, the only strange thing was that after n, the subsecuence could continue in 1, but without repeating any number.

→ Reply

moxlotus

9 years ago, # ^ |

its actually coin-change. treat the remainders as the coin that you have, how many numbers can you make. check through these numbers to see which are divisible by m. and you are done.

→ Reply

9 years ago, # ^ |

NO, is not like that, because is a subsecuence, not a subset, a subsecuence is of continuous numbers.

→ Reply

MPeti

9 years ago, # ^ |

← Rev. 2 →

It didn't have to be a contagious subsequence. One of the examples had a non-contagious solution:

4 6
3 1 1 3

YES

→ Reply

9 years ago, # ^ |

Yes, but I thought It could be circular, so, after the final 3, continues the first one.

→ Reply

9 years ago, # ^ |

contagious=transferrable, like diseases contiguous=one after another

→ Reply

9 years ago, # ^ |

At least that is what I thought, but now I see my answer received a WA in the 39 tests

→ Reply

MPeti

9 years ago, # ^ |

← Rev. 2 →

I think there's no way it's impossible if N >= M. My not-very-rigorous-but-you-get-it proof:

Imagine you're doing a simple dynamic programming solution, with the elements sorted in ascending order first. If a number's multiples "circled back" all the way to 0 (this might mean going around the modulo space several times), we're done. So assume that didn't happen yet. If we can prove this means we'll always get at least one possible new modulo value when adding each number, it's proven. So take a new number X. There are 3 possibilities:

This number already occurred. It can't have circled back, so by adding it to the last iteration, we get a new value.
It's a multiple of a previously occurring number. Since that number hasn't circled back, we can get several new values just like we did in the first case (from the last few iterations).
It's a relative prime to all that occurred before. Obviously, X%M hasn't occurred before, so that's a new value.

→ Reply

ialwaysusethisaccount

9 years ago, # ^ |

-8

i found this during the contest http://math.stackexchange.com/questions/699857/proof-subsequence-of-n-integers-is-divisible-by-n

if you understand the proof please explain it here in plain english. thanks.

→ Reply

moxlotus

9 years ago, # ^ |

this is a different problem. for this subsequence, it doesnt have to be contiguous, whereas the link that you have shown seems to talk about subsequence in contiguous form.

→ Reply

9 years ago, # ^ |

But if there is a contiguous subsequence, then there definitely is a not necessarily contiguous one. I fail to see how this is not relevant.

→ Reply

MPeti

9 years ago, # ^ |

← Rev. 3 →

Appears I was right, yay! :D Anyway, what I posted above is a plain English proof of this statement. But I guess the one given on Math SE is simpler, so I'll explain that one as well:

Let's assume M == N. I'll only use N in the proof.

Let's define the series R_1, R_2 .. R_n like this: R_k is the remainder of the sum of the first k elements, that is, (a_1 + a_2 + .. + a_k) % N.

If for some k we have R_k == 0, take that subsequence and we're done.

Otherwise, there are N numbers in the R series. They can have N-1 possible values (since none of them was 0). This means there are two equal numbers in R, so there are two prefix sums in the original series whose remainder by N is the same. Let's say R_i == R_j, and i < j.

This means that adding a_(i+1), a_(i+2), ... and a_j to R_i didn't change its remainder by N. So the subsequence a_(i+1) + a_(i+2) + ... + a_j has a remainder of 0 by N.

This also showed that there must be a CONTAGIOUS subsequence that satisfies this.

EDIT: ffao managed to explain this proof much simpler than I did, look at his explanation if you don't get it :)

→ Reply

9 years ago, # ^ |

← Rev. 2 →

The (easier, I guess?) rigorous proof:

Let the sum of the first i elements modulo m be S[i]. There are m different possible values of S[i]. If we find S[i] such that S[i] = 0, we're done. So suppose none of them is zero. By the pigeonhole principle, at least two of S[1], S[2], ..., S[m] must be equal, say S[x] = S[y]. But then a[x+1] + ... + a[y] = S[y] — S[x] is divisible by m!

So it's always possible if n >= m.

→ Reply

binary_eagle

9 years ago, # ^ |

Thanks GrandMaster ffao

For the case of n < m, can i add dummy values of 0 so that n >= m and then argue that if we can't find S[x] and S[y] then it was not possible with the initial sequence ?

→ Reply

9 years ago, # ^ |

Adding dummy values of 0 is not a valid modification as it changes the answer to the problem. That happens because you can always select your newly added 0 as the divisible by m subsequence, which will make it always possible.

→ Reply

kostka

9 years ago, # |

+95

What is happening? Why the contest is still running when everybody stopped and there was even a window with information that coding phase has finished?

→ Reply

kostka

9 years ago, # ^ |

I haven't seen any notification about extending the round and a lot of people too. Was it a bug or there was no notification at all?

Nevertheless, I think that the submissions after the original time should not count...

→ Reply

MikeMirzayanov

9 years ago, # ^ |

+18

The system gone to total gc on 1:23 :( We are working to reduce memory consumption and prevent such situations.

We increased contest duration while backed was restarting. Unfortunately, we were unable to send notifications.

Right now our highest priority task to fix it. Sorry to inconvenience.

→ Reply

kostka

9 years ago, # ^ |

No problem, I understand, but I was a bit surprised. Thanks for quick reaction!

→ Reply

9 years ago, # ^ |

+16

People had started discussing the problems too.

→ Reply

VastoLorde95

9 years ago, # |

+23

Was the round extended? Cause I did'nt get any notifications.

→ Reply

rsFalse

9 years ago, # |

-7

Seriously, no adding minutes for the round? And system is not available last 5 minutes of contest.

→ Reply

9 years ago, # |

+35

Are you going to cancel submits after 2:00?

Btw. I lost 5-6 minutes not knowing that round goes on. And I found a bug 10 seconds after the final end. I hope it wouldn't get AC — http://ideone.com/6DVME8

→ Reply

subscriber

9 years ago, # ^ |

Well, at least your contest went without any problems :)

→ Reply

9 years ago, # ^ |

clarification: I'm not ranting. More like crying or something :D

→ Reply

9 years ago, # ^ |

;_;

→ Reply

etal

9 years ago, # |

← Rev. 2 →

+20

I hacked 2 C-div1 problems with carefully written cases to solutions close to what I believe is the correct answer (somehow partitioning the space in chunks of size 1000xsth and move around them properly).

However, if they are partitioning them in chunks of something different but close to 1000, my test cases probably won't work because their structure is completely messed up,since they are meant against partitions of 1000 (could have been 1001, nothing special in 1000).

Can you come up with a way of creating a challenge that doesn't assume a particular number with which partitioning space? There should exist some of those in system testing, but I cannot come up with them.

→ Reply

etal

9 years ago, # ^ |

PS: the system test probably didn't have them because one of the programs I hacked got accepted just by changing the partition number from 1000 to 1500.

→ Reply

micklepru

9 years ago, # |

When will editorial be available?

→ Reply

OmaeWaMouShenDeiru

9 years ago, # |

For C div2, My solution is to print all prime and perfect square numbers that are less than or equal 'n'.

Why is it wrong ??

→ Reply

Alwahsh

9 years ago, # ^ |

→ Reply

nicky_ua

9 years ago, # ^ |

you must also print 3, 4,5... powers, that less or equal n

→ Reply

9 years ago, # ^ |

for each prime, you print prime^i if this is <=n.

→ Reply

nazaninnnnn

9 years ago, # |

How solve problem C div1 ?

→ Reply

DanAlex

9 years ago, # |

Wow , do we have a new dreamoon_love_AA : .o. ?

→ Reply

Endagorion

9 years ago, # |

+84

The problems are awesome. Hard to believe none of them had been used before. =)

→ Reply

dalex

9 years ago, # ^ |

-18

Why do you call B and C awesome? Some arguments? B is 'write two if-s', C is 'think of the correct partition', both are boring and non-interesting for me.

→ Reply

Endagorion

9 years ago, # ^ |

+45

Well, B ends up somewhat involved while being really simply stated (also I tend to like problems somehow connected to graph isomorphism =)), and C has a constructive flavour which is always nice. The 'think of the correct partition' is for sure more creative than 'implement the segment tree for the bazillionth bloody time'.

→ Reply

9 years ago, # ^ |

+16

I agree that such original problems are the best. Like misof said, "The less it resembles anything I've seen before, the better!"

→ Reply

duckladydinh

9 years ago, # ^ |

It is because you are too good For beginner, like me :'( , they are too interesting

→ Reply

dalex

9 years ago, # ^ |

Lol, I'm yellow forever

→ Reply

al13n

9 years ago, # ^ |

The idea of E is old though. For some reason it's still not very overused, I've only seen it maybe four times.

→ Reply

http://se.math.spbu.ru/SE/diploma/2012/s/Kopeliovich_diploma.pdf

9 years ago, # ^ |

Can you provide some links? malcolm and sankear invented this idea while solving some completely different problem (having nothing common with this kind of semi-online dynamic connectivity) in a pretty complicated but elegant manner.

→ Reply

al13n

9 years ago, # ^ |

(for the dynamic connectivity; the DSU with flags is new to me and was a nice touch)

→ Reply

9 years ago, # ^ |

Of course the dynamic-connectivity-offline itself is well-known thing, we do not pretend on inventing it. What I asked you is idea that while traversing the tree of divide-and-conquer we can still modify information in the future in a manner similar to segment tree. Did you see such approach before?

BTW, DSU with flags (as I understand you mean a data structure for adding edges and checking if the graph is bipartite) is described on e-maxx.

→ Reply

al13n

9 years ago, # ^ |

Oh, ok, I guess that's new. Sorry, haven't thought about it as a separate idea. Probably because in the implementation I'm used to it's a straightforward modification.

→ Reply

Temirulan

9 years ago, # |

How to solve Div1-D?

→ Reply

CurbStomp

9 years ago, # |

Div 2 D anyone??

→ Reply

Miryu

9 years ago, # ^ |

Div 2.D == Div 1.B

→ Reply

AtomRush

9 years ago, # |

← Rev. 2 →

please make testcase so as to fail all n*m solutions mine n*m failed while this HURTS

→ Reply

9 years ago, # ^ |

That solution is not n*m. That solution is min(n*m, m*m). (The loop will always break after at most m iterations, for reasons discussed above).

In other words, that solution is correct.

→ Reply

9 years ago, # |

Anybody who solved C(Div 1) as follows. Divide into 1000 blocks with 10^6x1000 rectangles. in each rectangle sort points by (x[i]+y[i]), I think it can be proven that will give 2n \sqrt(n) bound.

→ Reply

9 years ago, # ^ |

No, you can create a test giving 3E9 if you don't alternate the sort order.

→ Reply

ifsmirnov

9 years ago, # ^ |

It seems that it works if each block is 1414x10^6.

→ Reply

omarkhaled

9 years ago, # |

Why there wasn't any announcement for the extra 10 minutes!!

→ Reply

pokorski

9 years ago, # ^ |

I tried to submit solution 2 minutes before contest end and I could not do it. 15 seconds before end I could submit, but I was not fast enough. I waited 2-3 minutes to see if contest is extended, but it was not. The only good think is that my solution would be incorrect anyway as I checked.

→ Reply

rsFalse

9 years ago, # |

Div 2. A. What is a worst test case time complexity for this solution? 12930538.

→ Reply

CodeForceps

9 years ago, # ^ |

It seems to be that the worst case for that solution is a n = 10⁵ and x = Highly composite number below 10⁹. It may be something like divisors(x) * n. On a quick analysis it seems that x has more or less 10³ divisors. So, the result should be 10⁸.

→ Reply

9 years ago, # |

LoL, why this solution gives TLE:12934189? Is it because of using vectors?

→ Reply

CodeForceps

9 years ago, # ^ |

No, because you did O(n*m). Beign n <= 10⁶ and m <= 10³ you have a 10⁹ solution. That's slow.

→ Reply

9 years ago, # ^ |

← Rev. 2 →

You are dividing 1E9 times but divisions are expensive so you can't make a lot more than 1E8 of them per second.

→ Reply

9 years ago, # ^ |

But my solution is O(m^2)( I consider case when n>m).

→ Reply

9 years ago, # ^ |

Ah sorry, I think the problem is that you are reading a million ints using cin, c++ streams are often too slow for such huge input.

→ Reply

9 years ago, # ^ |

← Rev. 2 →

that would be really sad as i also seem to have O(m**2) but i am reading data with cin :(.I also think this should have been covered in pretests

→ Reply

9 years ago, # ^ |

cin is fine; just add this magical command:

ios_base::sync_with_stdio(false);

See here.

→ Reply

mondayguy

9 years ago, # ^ |

Magical command helps a lot, but anyway cin is much slower then scanf, even with command.

→ Reply

9 years ago, # ^ |

+17

Ironically, I've had my first experience with that just now.

But it is fairly rare. Still, I'll use scanf from now on.

→ Reply

9 years ago, # ^ |

Do you ever clear xp? I think xp might be getting really big near the final iterations...

→ Reply

9 years ago, # ^ |

Oh, thanks. I think that was actual problem:)

→ Reply

Xellos

9 years ago, # |

← Rev. 2 →

Ugh, I only had a bit less than one hour for the contest. To be precise, I'm travelling and the only place where I could do the contest was one train/bus station (next to each other). But the train station's net hotspot didn't work and the bus station only has a 3rd party connection with 1 hour free, then nothing. So I hurried a lot and I think I'm going to fail both B and C.

Why couldn't the round be 2 hours earlier... I could've done it at home then...

UPD: yes, I failed both B and C.

→ Reply

9 years ago, # ^ |

Why didn't you leave this one for virtual contest if you were travelling?

→ Reply

Xellos

9 years ago, # ^ |

+13

Because it'd be yet another one. Most CF contests have had awful dates for me recently (which means the last few months, because there have been so few). When I'm home, there's nothing, then I leave somewhere without net for a few days and a CF contest is guaranteed.

→ Reply

9 years ago, # ^ |

So, you prefer losing ratings than not enjoying a contest. That is very inspiring Xellos :)

→ Reply

Golovanov399

9 years ago, # |

2s * 617sols * 50tests ~ 900 min testing (task C)

Where am I wrong?

→ Reply

Golovanov399

9 years ago, # ^ |

Ok, I can't into parallel calculations and good solutions which work fast (or fail early), but it still slows testing, thank you for the limits

→ Reply

KADR

9 years ago, # |

+141

Am I the only one who mistakenly read the constraint in problem C as 2.5·10⁸ instead of 25·10⁸? The common agreement about scientific representation of real numbers is to use normalized notation and according to it the constraint in problem C should've been 2.5·10⁹.

→ Reply

JKeeJ1e30

9 years ago, # ^ |

+12

You are not alone)

→ Reply

JKeeJ1e30

9 years ago, # ^ |

And our solutions is very similar. We both tryed to solve it O(n*logn), TL.

→ Reply

Nicolas16

9 years ago, # ^ |

← Rev. 2 →

+12

At first I also misread it, but the points (1000*i, 1000*j) with 1 <= i,j <= 1000 are such that the shortest Hamiltonian path has length ~10^9

→ Reply

9 years ago, # ^ |

← Rev. 2 →

In fact it was possible to understand that you understood something wrong by noticing that for the 1000x1000 uniform lattice (all points of form (1000a, 1000b)) the answer has order of 10^9.

Nevertheless, you are right, writing 2.5 * 10^9 could've been much better.

UPD: oh, Nicolas16 said the same thing before me.

→ Reply

KADR

9 years ago, # ^ |

← Rev. 2 →

+27

Well, the statement said "it's guaranteed that the answer always exists for given input" so I didn't worry too much about that :)

→ Reply

Nicolas16

9 years ago, # ^ |

← Rev. 2 →

Yeah but then there would have been input where the minimal length is exactly 2.5 * 10^8, which means that we would have had to find the exact minimal path in this particular case (which did not seem to be the the goal of the problem).

However, I had to remark all these things during the contests and I lost some time before understanding I misread the bound, so I am not saying you are wrong :-)

→ Reply

ifsmirnov

9 years ago, # ^ |

← Rev. 2 →

I thought it was a trick to obscure the desired complexity. 2.5·10⁹ looks pretty much like $\text{[math]}$ while 25·10⁸ is «what the wierd constant is it?!»

I really thought of it as a nice beautiful obfuscation, no irony here.

→ Reply

9 years ago, # |

Too scared to look at my submissions page.

→ Reply

9 years ago, # ^ |

congrats you passed all three you attempted:)

→ Reply

9 years ago, # ^ |

Honestly, I would not have opened the page at all. Thanks for telling me :)

→ Reply

Bat-Orgil

9 years ago, # |

Those permutation problems are cool

→ Reply

Tochi

9 years ago, # |

+22

→ Reply

geniucos

9 years ago, # |

What is special at test 9 from div1B? I looked at my source 10 times bbefore submitting it to be sure I don't miss anything. I've even hacked some sources=)))

→ Reply

9 years ago, # ^ |

printf ("%d %d\n", nod1, nod2);
for (int i=2; i<=N; i++)

Isn't this going to miss node 1 if it is not either nod1 or nod2?

→ Reply

geniucos

9 years ago, # ^ |

← Rev. 2 →

Yes, it does...stupidest bug ever.Thanks.I don't know why I pressed 2

→ Reply

9 years ago, # |

I might be the happiest blue coder to-be ever!!!! Should be out of green right??!!!!

→ Reply

9 years ago, # ^ |

seems likely all the best !

→ Reply

9 years ago, # ^ |

Thanks!! :)

→ Reply

RetiredAmrMahmoud

9 years ago, # |

+14

"and it's strongly disadvised to skip it."

Nice trap

→ Reply

mredigonda

9 years ago, # |

+22

Look, the green coder latisel is the winner of a Div2 contest!, oh wait look at his previous contest here.

→ Reply

9 years ago, # ^ |

Worse than worse . Unbelievable!

→ Reply

9 years ago, # ^ |

+11

some red seems to be having FUN!

→ Reply

Nicolas16

9 years ago, # ^ |

+19

I guess he did so because he was "only" second. That's crazy how people think they will become "famous" by winning a Div 2 contest...

→ Reply

JKeeJ1e30

9 years ago, # ^ |

+14

Alone man who won div2 and became famous was just sorry_dreamoon.

→ Reply

wrong_order

9 years ago, # ^ |

+14

→ Reply

FatalEagle

9 years ago, # |

+34

I passed D with "bad" solution $\text{[math]}$ :) Only optimization is order of for loop in matrix multiplication — I remember reading somewhere that you can make naive multiplication cache-friendly by switching order of for loops from i, j, k to i, k, j. And after that, all that's left is a trivial if statement that checks a[i][k] isn't 0 before multiplying it with the for loop with j.

→ Reply

9 years ago, # ^ |

I thought about submitting that, but I was pretty sure it wouldn't pass... Guess I shouldn't underestimate the CF servers after all :)

→ Reply

9 years ago, # ^ |

Looks like that is the wanted complexity... Makes me think D is a pretty bad problem now, is it just "submit the obvious solution and hope that it passes"?

→ Reply

9 years ago, # ^ |

There is a typo in editorial I think. It should be "it's not enough", not "now enough". So /32 was intended.

→ Reply

malcolm

9 years ago, # ^ |

Yeah, it's definitely a mistake, thank you.

→ Reply

KAN

9 years ago, # ^ |

I think I have the same solution (12942073), but it got WA44 and I can't find the bug now...

→ Reply

aaaaajack

9 years ago, # ^ |

← Rev. 3 →

Edit: You didn't clear "nextcur".

→ Reply

KAN

9 years ago, # ^ |

Oh, really, AC now. Thank you!

→ Reply

dhruvgaur

9 years ago, # |

for DIV2 B: can any one find whats wrong with this submission: http://mirror.codeforces.com/contest/577/submission/12944993

→ Reply

9 years ago, # ^ |

What is this?

for(int j=1;j<= ht[i];j++)
  sum = (sum + i);

→ Reply

dhruvgaur

9 years ago, # ^ |

← Rev. 2 →

after putting number into buckets within %m.....

I am iterating over each bucket for count of #'s in it...this loop is for that....

Thanks for your reply...

I can understand if this goes on and gives TLE but i want to know why WA....

→ Reply

dhruvgaur

9 years ago, # ^ |

Hi....thanks again for looking into my code....it turns out just a shift of loops here and there and it got AC.

here is the submission: http://mirror.codeforces.com/contest/577/submission/12963454

→ Reply

vedaanta

9 years ago, # |

← Rev. 2 →

why does the use of pow function from math library give a WA while without that its AC... Ans 1 : with pow func http://mirror.codeforces.com/contest/577/submission/12941362 Ans 2 : without pow func http://mirror.codeforces.com/contest/577/submission/12947283

→ Reply

karunk

9 years ago, # ^ |

← Rev. 2 →

Its happening with me too!!!!!

codeforces is giving me this output for test case_ 7_**** 19 32 16 8 4 27 9 24 2 3 5 7 11 13 17 19 23 29 31 37

but my system is giving this output! 19 32 16 8 4 27 9 25 2 3 5 7 11 13 17 19 23 29 31 37

→ Reply

vedaanta

9 years ago, # ^ |

for me its test case 4... cf : n=15 -> 9 2 3 4 5 7 8 9 11 12 ideone : n=15 -> 9 2 3 4 5 7 8 9 11 13

→ Reply

9 years ago, # ^ |

Pow uses floating point values and you round them down when you convert them to ints. It should pass if you add an epsilon.

→ Reply

dush1729

9 years ago, # ^ |

-8

Try using powl()

→ Reply

Danlark

9 years ago, # |

+139

al13n got 90 tests on problem E, but Endagorion got TL on 96 test, wtf?

→ Reply

9 years ago, # ^ |

We are already investigating this.

→ Reply

9 years ago, # ^ |

Fixed. That was not a judgement error, but only an error of verdict page showing information not for all testcases.

→ Reply

kev11

9 years ago, # |

-7

hi.. i think that there is something wrong with codeforces compiler this code gives wrong answer on test4 problem C http://mirror.codeforces.com/contest/577/submission/12937746 i tried the same input with the same code on my computer and on ideone (http://ideone.com/hIQ3BM) and it gave the right answer.. could any one pleas tell me what is going on?!!

→ Reply

9 years ago, # ^ |

You can't trust the pow function since it uses floating point arithmetics.

→ Reply

kev11

9 years ago, # ^ |

-7

Thanks JohStraat..but i can't really understand ..is using pow function causes undefined behavior?? ..so what do you suggest instead using pow function in general?

→ Reply

9 years ago, # ^ |

as suggested by dushyant use powl or make your own pow it will be a short function

→ Reply

Lord_F

9 years ago, # |

Div1 C checker is awesome!)

→ Reply

Swistakk

9 years ago, # |

+103

→ Reply