175 is also a div2-only contest :D.

11 years ago, # |

+26

hope this round be successful

→ Reply

Stratonov

11 years ago, # ^ |

Hope all.

→ Reply

11 years ago, # |

-14

Let's get ready for fun!

→ Reply

Shuaib

11 years ago, # |

+10

Lets just hope this contest goes fine and rated. :)

→ Reply

rumman_sust

11 years ago, # |

Wish this contest will be rated. BTW thanks for early announcement. :)

→ Reply

11 years ago, # |

+18

Oh MY god!!!I have taken part in three CF round...But I am unrated now(Because all of those three round have something wrong...)= =...SO I don't want to miss this one ....But ..At 23:30 on Thursday, I will on the train to Chengdu to take part in a invitation match.....WTF....Who can help me!!!!!

→ Reply

ron2794

11 years ago, # ^ |

let me play for you. :D

→ Reply

11 years ago, # ^ |

only joking....

→ Reply

Stratonov

11 years ago, # ^ |

This is life.

→ Reply

11 years ago, # ^ |

Yes...life is cruel...

→ Reply

11 years ago, # ^ |

What kind of help do you expect?

→ Reply

11 years ago, # ^ |

+14

I need a laptop when I am on the train.... and a wifi....Although I usually write code on the cellphone by c4droid and submit by chrome....But...as you know, it's not convenient...

→ Reply

11 years ago, # ^ |

So...please the judge system good luck and don't have fun ....please this round can be rated....I want to be rated!!

→ Reply

absi2011

11 years ago, # |

I hope everything will be ok this round.

→ Reply

nikalosaberidze

11 years ago, # |

-13

For Furko its his first codeforces round and i hope that it will be very easy or very hard :)))

→ Reply

BGbigchickenleg

11 years ago, # |

-7

THIS IS MY FIRST CONTEST IN CODEFORCES ....WISH ME GOOD LUCK T-T

→ Reply

topkek

11 years ago, # ^ |

+16

Good luck.

P.S: Your Captain Obvious

→ Reply

11 years ago, # |

Thinks for this round.I'm so glad it's coming soon.

→ Reply

11 years ago, # |

hopefully this round will be successful! good luck everybody! :)

→ Reply

11 years ago, # |

This is going be heavy loaded contest. 2177 and still counts.

→ Reply

HackMeNow

11 years ago, # ^ |

Not so "heavy" loaded. April fools day contest has 3200 registered user, and #175 has just a little more than 3000.

→ Reply

11 years ago, # ^ |

Don't forget it's just Div2 contest. I think many Div1 coders will not participate in it.

→ Reply

HackMeNow

11 years ago, # ^ |

-8

175 is also a div2-only contest :D.

→ Reply

11 years ago, # ^ |

Ok. I'm not saying, that contest is going to be the most busiest :)

→ Reply

dario-dsa

11 years ago, # |

After hard Chinese problems, I think easier European.

→ Reply

chrome

11 years ago, # |

← Rev. 3 →

Gl && hF

→ Reply

dario-dsa

11 years ago, # ^ |

hv?

→ Reply

abhay26

11 years ago, # ^ |

good luck have fun.

→ Reply

11 years ago, # |

This is the most unlucky hacking attempt, isn't it? :(

→ Reply

ScottPilgrim

11 years ago, # ^ |

← Rev. 2 →

hmm... i'm pretty sure that you writed this contest from this account http://mirror.codeforces.com/profile/kingofnumbers2

→ Reply

dont_lose_the_hope

11 years ago, # ^ |

← Rev. 2 →

-10

But I didn't cheat :)

I only used one account in this contest

→ Reply

sasha.sochka

11 years ago, # ^ |

+11

Anyway, creating 2nd account is prohibited by rules.

→ Reply

yeputons

11 years ago, # ^ |

+53

I think, this one is worse:

→ Reply

11 years ago, # ^ |

my submission 3800641 came pretty close to TLEing too.....thankfully it didnt exceed 2 seconds! :)

→ Reply

Avitella

11 years ago, # ^ |

← Rev. 2 →

I think your IO is very very slow, because my solution get sum from 0 to n every iteration, but it's pass for 400ms. Try to use ios_base::sync_with_stdio(false).

→ Reply

shovonshovo

11 years ago, # ^ |

what is the function of ios_base::sync_with_stdio(false) ?

→ Reply

Avitella

11 years ago, # ^ |

This

→ Reply

kmamp

11 years ago, # |

← Rev. 2 →

-8

wasted so much time trying to find out why my brute force solution didn't work for the second problem when a very easy dp implenetation I made in the end passed all the pretests... yet another bad contest for me :(

→ Reply

LashaBukhnikashvili

11 years ago, # |

how solve problem D?

→ Reply

adelnobel

11 years ago, # ^ |

I was going to ask the same question!

→ Reply

11 years ago, # ^ |

dp[i][j] = minimum cost to repair j holes from the first i holes Complexity: O(N^3)

→ Reply

Ac-93

11 years ago, # ^ |

how do steps?

→ Reply

11 years ago, # ^ |

Try every i <= k < N, dp[k+1][new_j] = min(dp[k+1][new_j], dp[i][j] + minCost(i, k)). minCost(i, j) can be precalculated in O(N^3).

→ Reply

Temirulan

11 years ago, # ^ |

How to precalc minCost(i, j)?

→ Reply

11 years ago, # ^ |

You take all the intervals from the input and then do something similar to Floyd–Warshall.

→ Reply

uerobert

11 years ago, # ^ |

The floyd-warshall part is not necessary.

→ Reply

niyaznigmatul

11 years ago, # ^ |

← Rev. 2 →

+18

Hey, do you have cerealguy's permission to use his photo? :)

→ Reply

uerobert

11 years ago, # ^ |

I didn't know there was already a cereal guy here when I chose this pic.

→ Reply

cerealguy

11 years ago, # ^ |

+10

You have my permission.

→ Reply

Tyr

11 years ago, # ^ |

there are some minor differences, size of head and also bowl or even the table !

→ Reply

11 years ago, # ^ |

first of all, each cost[i,j]=INF.

for each l,r,c you get, cost[l,r]=min{ cost[l,r] , c }

then cost[i,j]= min{ cost[i,j] , cost[i-1,j] , cost[i,j+1] }

→ Reply

pswgoo

11 years ago, # ^ |

Uhn!Could you explain what is the meaning of the recursion formula and the 'minCost(i,k)'?

→ Reply

11 years ago, # ^ |

You have currently decided what to d with the first i holes. You repaired j from them. You try to repair every interval (i,k), i <= k < N. The cost to repair this interval is minCost(i, k) which is precalculated. You end up at dp[k+1][new_j] because you have already decided what to do with the first k+1 holes and you repaired some additional holes. Also, you can decide not to do anything at this hole (go to dp[i+1][j]).

→ Reply

nims11

11 years ago, # ^ |

← Rev. 10 →

dp[i][j] = minimum cost for fixing j holes out of first i holes.

dp[i][j] = min(seg.cost + dp[i-seg.size][j-seg.size]

where seg = {l,r,c} and all seg.r == j

I didn't submit as I was a minute late, but I believe it to be correct.

UPD: Nah, not correct logic, small modification required to it.

→ Reply

tenstep

11 years ago, # ^ |

My idea is the same as yours but got wrong answer on pretest4.In fact,we won't fix a hole more than one time. try this test: 3 2 3 1 2 1 2 3 2

→ Reply

AlimA

11 years ago, # ^ |

This is my idea but my code wasn't right for samples: First I define dp[i][j][k] = minimum const to fix at least k holes in j first holes using first i companies. while companies are sorted by their right points. And the update: dp[i][j][k] = min (dp[i — 1][j][k], dp[i — 1][j — (j — company[i].left + 1)][k — (j — company[i].left)] + company[i].cost)

I saw that the difference between second and third dimensions of dp is always the same, so I omitted third dimension. And so this dp is my solution: dp[i][j] = minimum cost to fix at least j — n + k holes in first j holes using first i companies while companies are sorted.

Is this solution right ? :-?

→ Reply

nebulae

11 years ago, # |

I hope tests for problem C are good enough to fail Java solutions which use Arrays.sort().

→ Reply

Furko

11 years ago, # ^ |

+12

Such test are included to pretests.

→ Reply

11 years ago, # ^ |

Yeah. I couldn't pass test 11 on Java. I finally pass them, when rewrite solution to C++

→ Reply

Darko

11 years ago, # ^ |

Thanks for trying to include that test, but my solution passed pretests just to time out on test 48 (Is that a hack input?).

I guess it is my fault to keep forgetting not to use Arrays.sort() on arrays of primitives

→ Reply

11 years ago, # ^ |

I add shaffle to my solution in Java and get TL too. Probably we need to read input data faster

→ Reply

11 years ago, # ^ |

I think it's 100% unfair. Quick-sort is the same for every language, Java probably have more overhead, but again — I think it's unfair.

→ Reply

bakharev.k

11 years ago, # ^ |

Shaffle array before sort it in Java.

→ Reply

11 years ago, # ^ |

Ok. I got it, it looks like tests are written to kill exactly Java implementation of quicksort. Good job!

→ Reply

Gassa

11 years ago, # ^ |

The default way of sorting things is not the same in every language. Modern compilers (GCC, Python, .NET starting from version 4.5, Java when sorting objects) tend to use $\text{[math]}$ worst-case algorithms, mostly Introsort and Timsort. However, in Java, integer sorting still uses double-pivot quicksort which is O(n²) in the worst case.

→ Reply

11 years ago, # ^ |

So, is it way to fix it? Write your own sort?

→ Reply

Elun

11 years ago, # ^ |

Randomly swap some items of array. And after that u can use Arrays.sort()

→ Reply

yeputons

11 years ago, # ^ |

You may want to know about Collections.shuffle routine.

→ Reply

11 years ago, # ^ |

Yeah, according to javadoc — Collections.shuffle runs in linear time. So it's a good solution. Thanks

→ Reply

Gassa

11 years ago, # ^ |

Or, box int-s into Integer-s and use an object sorting routine (Collections.sort?). It may be slower though in the general case.

→ Reply

http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort(int[])

11 years ago, # ^ |

Funny stuff. I shaffle my List, but get TL again in practice.

→ Reply

sentinel45

11 years ago, # ^ |

submit in java 7

→ Reply

Zzyzx

11 years ago, # ^ |

The sorting algorithm used in Java for Arrays.sort(int[] arr) is tuned quicksort which offers very good average case performance.

Many contestants used Arrays.sort() today for problem C and have passed System tests. I think if the solution fails, the problem lies elsewhere.

→ Reply

jdillet

11 years ago, # ^ |

My solution was using Arrays.sort() and failed pretests with TLE.

The same solution is passing after these changes: - Use FastScanner implementation by martinezgjuan (which uses BufferedReader + StringTokenizer). - Use Java 7 (not Java 6)

Now is passing with worst running time 951ms (no need to shuffle the array).

→ Reply

dalex

11 years ago, # ^ |

Java 7 also uses quicksort, it's just your luck that nobody has made anti-java-7-hack.

→ Reply

sentinel45

11 years ago, # ^ |

AFAIK java7 uses TimSort

→ Reply

tenstep

11 years ago, # |

I am really curious about what the pretest 4 of problem D is.

→ Reply

PAP

11 years ago, # |

← Rev. 2 →

that was a great contest after ... :)

→ Reply

Pancake

11 years ago, # |

May someone introduce the intended method for Problem E ?

→ Reply

11 years ago, # |

anybody knows why system testing is taking very long time today??

→ Reply

sasha.sochka

11 years ago, # ^ |

← Rev. 4 →

Big number of testcases for problem C, I guess. Also, contest is merged for both divisions, so there is a lot of participants => solutions to judge

→ Reply

PAP

11 years ago, # ^ |

and a lot of submit in contest

→ Reply

accidentallygivenfuck

11 years ago, # ^ |

← Rev. 2 →

-15

Ask messi. He is best ;)
EDIT : I thought there are more FC Barca fans than others in CF and I'll get pluses. 8)

→ Reply

Alex7

11 years ago, # |

Problem D is really beautiful, solving it was tons of fun!!

→ Reply

Pancake

11 years ago, # |

O(N³ + M) on problem D got me TLE :(

→ Reply

WildUtah

11 years ago, # ^ |

It's funny. My O(N^4) passed.

Sometimes the speedy inner loop is more important than the asymptote. I wrote carefully to eliminate 31/32 of the transitions in the dp without computing them.

→ Reply

Calvinxiao

11 years ago, # ^ |

Mine solution is even slower, but passed.

→ Reply

MrDindows

11 years ago, # ^ |

← Rev. 3 →

haidora1, I think that the cycles

for(int n = 1 ; n <= N ; n++){
for(int k = 1 ; k <= n ; k++){
for(int i = 0 ; i < f[n].size() ; i++){
for(int h = n ; h >= 0 ; h--){
...

if f[N].size ~ M , give you O(N³ + MN²) .

→ Reply

Pancake

11 years ago, # ^ |

← Rev. 2 →

Thank you , I can see what's wrong now.

→ Reply

selfcompiler

11 years ago, # |

TLE-SOLUTION passed solution why the second solution passed and the first one get TLE

→ Reply

latvian

11 years ago, # |

Wow, so many AC for problem C which pass with execution time of exactly 2000 ms, which is the TL for that task. Ofcourse on the other hand some codes definitely fail by only a few ms in this case. Now I wonder — is the TL set a little too low and hence might reject some codes with TLE even with the correct idea/implementation of solution OR is the TL a bit too high and that's why it lets some weaker codes pass that actually shouldn't?

→ Reply

11 years ago, # ^ |

The Time limit is enough, those codes probably used slow input methods

→ Reply

whatbeg

11 years ago, # |

-33

unrated?

→ Reply

adelnobel

11 years ago, # ^ |

Why lol?!!

→ Reply

ealevel

11 years ago, # |

-19

So, what is the point for CodeForces to support several languages as they do if you will have problems that cannot even run within the time limits using that language, regardless of how efficient you do it. You may have the exact same code in Python and Java, but you get TLE in Python (The same happens sometimes with Java and C++). Then, why support Python? Why don't you just get serious and support languages in which problems can be done like in TopCoder? Or just increment the time limit for certain languages, whatever you feel more confortable with. That would be a lot easier for contestants! In my opinion, it is NOT fair to get a problem wrong when the algorithm is identical to others who got it right, being the code language the only differentiator.

→ Reply

adelnobel

11 years ago, # ^ |

-13

Can't agree more. The same algorithm runs in time if coded in C++, but in python it gets TLE. This happened in problem C for many Contestants.

→ Reply

WildUtah

11 years ago, # ^ |

← Rev. 2 →

+18

Python is easier to write correct code in than C++.

The syntax is simpler, the edge case and corners are less likely to cause you trouble, the array bounds are checked so that errors show up right away, debugging and tooling is better, Python has a repl so you aren't always compiling-testing-compiling-timing just to try an idea, and you don't have to worry about static type declarations. C++ is a pain with cruft from legacy implementations, the syntax is verbose and cryptic, the template system is full of hidden troubles waiting to bite during a contest, and even the compiler error messages are indecipherable.

But C++ runs about ten times faster than Python.

So there are advantages and disadvantages to both. You are allowed to switch languages between problems. You can even pick your algorithm and then choose your language for each problem based on speed and convenience.

Being able to choose wisely is part of competing here.

→ Reply

ealevel

11 years ago, # ^ |

-9

I have to disagree with you there. I know Python have a lot advantages over C++ in terms of readability, testing and debugging; that's the main reason I code in Python rather than C++, or even Java that I use as my second choice.

I believe it can be challenging enough to come up with an algorithm that works for a particular problem and also have a quite good and reasonable complexity. So, why would my solution be wrong when is as good as yours?

I can see how almost every C++ coder codes everything in C++, but you can say that you have to "choose wisely" your code language for a particular problem, when even the easiest problem you already code it in C++. So, when do you actually choose? I believe that is not the reason.

→ Reply

gustavoatt

11 years ago, # ^ |

I think the main issue here is that it was not possible to get AC in Python with any solution. While I understand that you have to think about efficiency twice in python (sometimes naïve code gets accepted only in C++ while in other languages you have to think of smarter solutions), I still consider that the most important ability to learn in these competitions is algorithmic skill, not language syntaxes or quirks.

In my opinion, is better if, for these kind of problems, Codeforces won't accept Python to avoid the misleading information that is possible to solve the problem with Python.

In short, we (at least me) are not here to learn the syntax and tools of languages, we are here because we would like to solve algorithmically challenging problems.

→ Reply

martinezgjuan

11 years ago, # ^ |

I think the constraints were not very well checked for the problem C. My code in Java barely passed the tests (1880ms) by even using fast custom made I/O routines and with an O(n lg n) algorithm. Had I not used the fast I/O library my code would have easily failed. And Java is not even one of the slowest languages supported. So either time limits should be loosen up a bit and maybe also increase the input constraints so algorithmically worse solutions fail even in C++.

→ Reply

xenoslash

11 years ago, # ^ |

I don't think so. This for loop might be the reason why the code is slow. for(int i=1; i<=n; i=4*i){ for(int j=0; j<i;j++){ total+= nums.get(j); } }

There are ways to do the for loop in a single pass by noticing the math pattern. E.g. http://mirror.codeforces.com/contest/313/submission/3799994

→ Reply

martinezgjuan

11 years ago, # ^ |

Oh, then it could have been a bit faster. Thanks for the tip :)

→ Reply

xenoslash

11 years ago, # ^ |

Your pass is not that slow though :). 1 + 4 + 16 +... ~ 3 passes of the array.

→ Reply

Calvinxiao

11 years ago, # ^ |

When I see n <= 10^5 and I have a O(nlog(n)) or faster solution, Python is the first choise.

→ Reply

andreyv

11 years ago, # ^ |

← Rev. 2 →

+21

Or just increment the time limit for certain languages

So… You have a job, your boss gives you a task and you implement it in Python. Everything is great, until customers start complaining that they have to wait minutes for your software to run. But you don't see it as a problem and tell your boss: "I know, it's Python, just tell them to wait more!" Does this sound realistic?

In my opinion, programs should be judged against real-life criteria, such as real running time and memory usage, not against arbitrarily chosen adjustments so that "different languages are equal". This is fair, and treating programs in different languages differently is not fair. If your language fails to be on par with others, then it is the language's fault, not Codeforces' fault.

It is about using the right tool for the job. C++ and Python have their advantages, and also have their disadvantages. C++ is fast, but hard to program in. Python is easy, but slow. You consider both options (which is more important — short code or fast code?) and choose the better tool in order to achieve a better result. If you knowingly chose the inferior tool, then it is your mistake and you will get penalized for that.

Now, here you might say that you had no idea your Python code would run so slow. But this is just a part of the learning process — you tried it and received negative feedback, and this will affect your future decisions (you will likely choose not to do the same thing again).

→ Reply

Srantik_13

11 years ago, # |

My same code got Time limit exceeded in contest but Accepted in practise...

I wonder why???

TLE code : 3800440 AC code : 3803673

→ Reply

11 years ago, # ^ |

← Rev. 2 →

thats really mysterious....u should probably report this issue to the admin with the above details.

→ Reply

Srantik_13

11 years ago, # ^ |

How to report?

→ Reply

11 years ago, # ^ |

sorry, i'm not sure of that.....but i suggest u send a message to MikeMirzayanov as he's the host of this site...

→ Reply

FlaminRage

11 years ago, # ^ |

The same thing happened to my friend!

TLE: 3801046

AC: 3804156

So very wierd :|

→ Reply

ealevel

11 years ago, # ^ |

Probably the way they measure the runtime of a code is not smart enough. Report it so they can do something about it, if possible. Not only your particular case but in general.

→ Reply

MeHdi.KaZemI8

11 years ago, # ^ |

← Rev. 2 →

TLE code : 3799383 AC code : 3804162

→ Reply

Tyr

11 years ago, # |

It is really funny, IceTube has become purple and Goldensea is blue ! and I think he can't compete in Div 1

→ Reply

deinier

11 years ago, # |

I had no idea about the difference in runtime between read using scanf/printf and cin/cout in C++. I always use scanf/printf in codechef and spoj but I was confident here in codeforces. I got TLE in problem C and I change cin/cout by printf/scanf and I got AC in 1 sec. Great, I will use scanf/printf here too.

→ Reply

FlaminRage

11 years ago, # ^ |

Try resubmitting the exact same code that gets you TLE again. It could get AC now. A lot of participants have had this problem today. If so, I think you should report this to the authority.

→ Reply

deinier

11 years ago, # ^ |

Thanks man, personally, I will stop using cout/cin in everywhere.

→ Reply

ilink

11 years ago, # ^ |

The fact is, if you notice execution time, it gets clear why this happened.

→ Reply

dsm

11 years ago, # ^ |

take a look here deinier: http://mirror.codeforces.com/blog/entry/925

→ Reply

deinier

11 years ago, # ^ |

← Rev. 2 →

Thanks for your help man, I read this great post. lol, using (_ios_base::sync_with_stdio(false);_) it was faster than using printf/scanf. Thanks a lot. Here is my submission.

→ Reply

11 years ago, # ^ |

Sometimes, writing a function to read is faster than printf/scanf.

→ Reply

FlaminRage

11 years ago, # |

It seems like many participants' solution of problem C got TLE during the contest but the exact same code gets AC after the contest! This is really unfair for the people who've faced this.

→ Reply

lxfind

11 years ago, # |

Any quick explanation on how to solve Problem E?

→ Reply

11 years ago, # ^ |

Greedily, i in set A should add m-i-1 in set B. If the amount of i are more than m-i-1 's, we should add m-i-2. Before that wo should do i+1 add m-i-2. So use a stack to solve it. Complexity O(m+n). The O(n) is printing answer.

→ Reply

11 years ago, # ^ |

I'm sorry that I don't know how to write clearly. Please read my code if you interested. 3803851

→ Reply

zzxchavo

11 years ago, # |

What is meet-in-the-middle algorithm ?

→ Reply

Labib666

11 years ago, # ^ |

I have only used this algo once, with some help from a friend. So I might not be able to explain efficiently. Still giving it a go.

Here's a demo of the algo -

You have a set of integers consisting of no more than 34 elements and want to find the number of subsets such that the sum of the integers in a subset is an integer N (N is a known value).

A brute solution would be to try all 2^34 ways, which is not efficient.

So what we do is we split the set in two equal subsets (meet in the middle algo), try to form all possible subsets for each set and record the results (the number of results is at most 2^17 for each set), then for each element in one set, run binary searches to find upper limit and lower limit for compatible results in the other set.

I don't know if this explanation is good enough. Maybe you can take a look at this. http://www.infoarena.ro/blog/meet-in-the-middle

→ Reply

water

11 years ago, # |

Why my code got WA on testcases 11 ?3805151

→ Reply

Nezzar

11 years ago, # ^ |

use long long to store the answer. The maximum is near 2*10^6*10^9 ~ 10^15

→ Reply

11 years ago, # ^ |

Read clearly, he used.

→ Reply

water

11 years ago, # ^ |

I used, thank you all the same.

→ Reply

timonti

11 years ago, # |

Can someone give me an idea for Problem C??

I was actually trying to simulate, but I think it is unnecessary... can someon eplease help?

→ Reply