Codeforces Round #303 (Div.2)

9 лет назад, # ^ |

Use Dijkstra and modify (d[v] == d[u] + w);

→ Ответить

keyvankhademi

9 лет назад, # ^ |

i used this method.
consider the spanning-tree (shortest path ST) with minimum weights.
delete a leaf from it then it can be prove that the remaining spanning tree is still with minimum weight.
so remove all nodes then add them one by one, in which you add you shout set it parent the node with minimum edge weight.

→ Ответить

9 лет назад, # ^ |

it isnt because i used dijkstra and i got WA. i think you should modify dijkstra so when (d[v] == d[u] + w) happens, you change d[v] to d[u]+w if the trees wieght decreases.

→ Ответить

Morphy

9 лет назад, # ^ |

← Rev. 2 →

Let d[x] denote the minimum distance from u to x. Let's construct a tree in G using this approach: 1. Let u be the root. 2. For all other vertex p, we can choose as a parent any node q such that d[p]=d[q]+w[q][p]. The most natural idea is to select the q with minimum w[q][p].

Since for each vertex we are selecting the edge with minimum weight, the total sum of weights will be minimum. It just remains to prove that for two different vertices, we can't choose the same edge as a link to the parent node (this is a consequence of positive weights)

→ Ответить

akulsareen

9 лет назад, # |

Question similar to E was asked in ICPC regionals this year. Here is the link.

→ Ответить

phpduke

9 лет назад, # ^ |

Actually solution algo was directly google-able too :P one can get ready-made algo for E in 2 clicks :/

→ Ответить

radoslav11

9 лет назад, # |

Problem C was really hard for third problem(C).

→ Ответить

hsnprsd

9 лет назад, # ^ |

It's obvious I think :) But D is easier than C.

→ Ответить

9 лет назад, # ^ |

i think C is the obvious one cuz its a simple DP.

→ Ответить

vatayush

9 лет назад, # ^ |

i think you can solve it by using greedy approach also.

→ Ответить

9 лет назад, # ^ |

i would love to hear how.

→ Ответить

__Joker

9 лет назад, # ^ |

Starting from left, If you can fell a tree left, make it go left else if you can fell it on right make it go right.

Why this works ? If you are falling left then it is easy to see that you are not spoiling the chance of the next tree. The option for next tree is open.

If you are falling the tree to right, may be there is a possibility that the right tree can't fall left. Only thing is worst case scenario you have to select only one of this tree.

→ Ответить

determinism

9 лет назад, # ^ |

← Rev. 2 →

I did the same thing except in a way which is unnecessarily more complex. Why do you think it gets WA? My Submission

→ Ответить

KrK

9 лет назад, # ^ |

+28

It was greedy. All problems were greedy :)

→ Ответить

CMaster

9 лет назад, # ^ |

D easier than A

→ Ответить

d4rkc0de

9 лет назад, # ^ |

Hard ?? why ?? it was a simple implementation .

→ Ответить

rudra_sarraf

9 лет назад, # |

← Rev. 2 →

-48

During coding phase,Earthquake at NEPAL-INDIA border ruined everything!! :( :(

→ Ответить

khatribiru

9 лет назад, # ^ |

← Rev. 2 →

+56

I am From Nepal (Original) . Please Don't Make a Joke about Earthquake

→ Ответить

utsav_deep

9 лет назад, # ^ |

I am from north India. There was no such earthquake.

→ Ответить

utsav_deep

9 лет назад, # |

+93

unexpectedly easy problem set. appears as if we are participating in a DIV 3 contest

→ Ответить

sheri.mori

9 лет назад, # ^ |

if the difficulty level was "standard" ANY of problems A,B,C,D could be Div2. A or at most Div2. B.Because no specific algos were needed,and problem C had some tricky coroners and wasn't actually difficult

→ Ответить

rsFalse

9 лет назад, # |

Thanks for nice contest for Div.2. There were interesting problems. Maybe pretests could be a bit weaker.

→ Ответить

MasterVinci

9 лет назад, # |

Why am I still unrated after this contest? (It is my first btw)

→ Ответить

vintage_Vlad_Makeev

9 лет назад, # ^ |

You will get rating after system tests and rating recalculation

→ Ответить

ayushrocker92

9 лет назад, # |

What was the 7th pretest for C :(..Kept getting WA

→ Ответить

I_love_Captain_America

9 лет назад, # ^ |

It was DP. You should initialize 0th tree at -infinity(-10^14) and n+1th tree at infinity.

→ Ответить

xlwinner11

9 лет назад, # ^ |

Well, that's obvious. But what about other trees, could you please explain to me? I couldn't code a working solution.

→ Ответить

I_love_Captain_America

9 лет назад, # ^ |

Either a tree doesn't fall at all, or falls on left or right. So, 3 arrays to hold these results.

→ Ответить

VashTheStampede

9 лет назад, # ^ |

Actually when the tree falls on the left or doesn't fall generates the same sub-problem!

So you can use only 2 arrays :)

→ Ответить

pas.andrei

9 лет назад, # ^ |

I did C in a greedy manner: keep 3 arrays(one for trees position, one for trees height and one for where will the rightmost part of the i-th tree be). I initialised the rightmost part of the first element as the position of the first tree and the (n+1)-th with INFINITY. Then for each tree starting from the second to the last i check first if i can make it fell to left(using the rightmost array), if i cant i check if it can fell to right and it is still impossible i move to the next tree without increasing the amount of trees that can be cut.

PS sorry for bad formating.

Here is my source code: CODE

→ Ответить

martinezgjuan

9 лет назад, # ^ |

Actually it could be solved in a greedy way without any extra space.

The first tree is toppled to the left and the last to the right.

Keep a variable "lastUsed" initially equal to the position of the first tree.

For trees [2, n-1] try to topple it to the left. If not possible try toppling it to the right and update to x[i] + h[i]. If it couldn't be toppled or it was toppled to the left "lastUsed" gets updated to x[i].

My code

→ Ответить

balalaika

9 лет назад, # |

← Rev. 2 →

+11

Hmmmm.... either I drunk too little coffee or I have to participate in Div3 contests....

→ Ответить

theRevenant

9 лет назад, # |

+31

It was a GREEDY contest!! :D

→ Ответить

Handled

9 лет назад, # |

+15

A car is good if it turned over in no collision --> RIP English

→ Ответить

durt

9 лет назад, # ^ |

What's the problem?

→ Ответить

martinezgjuan

9 лет назад, # ^ |

A car is good if it was not turned over in any collision

→ Ответить

9 лет назад, # |

This was easier than Codechef Lunch time contest, which is supposedly designed for school students.

→ Ответить

darkshadows

9 лет назад, # ^ |

+11

Have you actually participated in those, because I certainly feel that overall level of lunchtimes is at par with Div2 contests(old ones when I used to participate :)) and most of the times even difficult than that.

→ Ответить

9 лет назад, # ^ |

Yes, I have and I believe that last two problems of Div2 contests are harder than last 2 problems of lunchtime. The level of first three problems are more or less the same. But today first 4 problems were very easy and 5th was direct implementation.

→ Ответить

motherofgod88

9 лет назад, # ^ |

I don't think you can judge the difficulty of problems which you can't solve in contest time. Just because the solution uses a familiar concept or uses less code doesn't necessarily mean it's simple. Have you solved Div2 E or the last problem from Lunch Time contest?

→ Ответить

motherofgod88

9 лет назад, # ^ |

+14

IOI is also for school students. Do you think it's easy?

→ Ответить

9 лет назад, # |

Codeforces favors C++ over Java too much. I cant make E accepted with Java, got TE all of the time. The algorithm I implemented is exactly same with accepted C++ version.

→ Ответить

phpduke

9 лет назад, # ^ |

There have been many Java AC too ,so probably your implementation could have been slightly slow ?

→ Ответить

http://codeforces.com/contest/545/submission/11164079

9 лет назад, # ^ |

Could you please give me a link to Java source of whom got AC? Many thanks!

→ Ответить

phpduke

9 лет назад, # ^ |

Also you can search by language as parameter too ,if you want to see more solutions :)

→ Ответить

percywtc

9 лет назад, # ^ |

I think the status filter is good enough for what you want:

And here are some of the source who got AC with Java: http://codeforces.com/contest/545/submission/11161969 (fastest in Java 7) http://codeforces.com/contest/545/submission/11163503 (fastest in Java 8)

→ Ответить

9 лет назад, # ^ |

Thank a lot! It's very useful.

After looking deep into the solution, the trick for Java developers is re-implementing ConsoleIO and PriorityQueue (Heap).

It is still a bit favor for C++ developers, since the built-in STL is pretty good already.

→ Ответить

hsnprsd

9 лет назад, # |

Only 3 "Failed System Test" solutions in my room. wow... XD

→ Ответить

balalaika

9 лет назад, # |

Can anybody explain this?

Task D. Sort and calculate got AC. But in query 1 1 1 1 1 1 1 5 two satisfied. But in query 1 1 5 1 1 1 1 1 1 three satisfied. Where am I wrong?

→ Ответить

anthonyhkf

9 лет назад, # ^ |

Because we sort the array first, so both of them will produce 1 1 1 1 1 1 1 5. The answer should be three: serve the first two, and serve the last person.

Hope it helps!

→ Ответить

Kemal

9 лет назад, # |

+10

what an awful contest ?! Everything depends on problem E!

→ Ответить

Mano

9 лет назад, # |

What did solve task C? I am build dinamic and found states with binary finder... Why it was not correct: http://pastebin.com/PHVYYqWC ?

→ Ответить

Bekmyrat.A

9 лет назад, # ^ |

o_O what a grammar ?!

→ Ответить

Mohamad_sa

9 лет назад, # |

The pretest was so strong i got two times WA in problem C&D and at last AC.I scanned the whole c++ coders of my room and there was no sign of mistakes in their codes :D

→ Ответить

keyvankhademi

9 лет назад, # |

My room 1016, NO successful hacking, NO system test fail. :|

→ Ответить

BekzhanKassenov

9 лет назад, # ^ |

The same situation is in my room, 1014.

→ Ответить

wrong0o

9 лет назад, # |

-23

rasoolll and Behnam.B cheated look at their submissions : 11152882 and 11153982 they are also from same university (shame on ferdowsi university of mashhad)

→ Ответить

Zlobober

9 лет назад, # ^ |

+28

Code doesn't look 100% similar. Their outputs on the third test differ also.

→ Ответить

khatribiru

9 лет назад, # ^ |

This is Common Problem With Short code. Two code can Have similar Idea ( Even These Code seems to be same but not Exactly Same). And another thing is, Generally Student from same University have closer Idea about many problems.

→ Ответить

CATIGERN

9 лет назад, # |

I am new to this site, and this was my first ever coding contest. I managed to solve 3 problems getting a rank of 1802. However, I cannot see any rating being alloted to me. Can anyone explain the reason for this, and how I can earn a rating.

→ Ответить

xlwinner11

9 лет назад, # ^ |

System testing wasn't finished. It is finished now. Your rating's 1448, gratz on your first contest!

→ Ответить

CATIGERN

9 лет назад, # ^ |

Thanks, I also wanted to know that few people were awarded more marks for certain questions, and I lost out on few points. For example Problem #1 was of 500 points, where as I was awarded only 408 points, even though I didn't fail any submission. I read somewhere about hacking other people's code and some room concept. Can someone explain me my roles about hacking and what am I supposed to do in a room.

→ Ответить

quizywiz

9 лет назад, # ^ |

you get less points if you take more time to solve. If you are sure of your solution you can press the lock button on the dashboard. Then you can view others' solutions to that problem by clicking the score in the room. If you find a mistake in their code, give a test case which satisfies constraints and gives sub optimal answer wwith their code. You get +50 if their code gives wrong answer and -50 otherwise. Also, if you click the lock, you cant resubmit for that problem.

→ Ответить

poikniok

9 лет назад, # ^ |

It is actually +100 for correct hack.

→ Ответить

thezodiac1994

9 лет назад, # |

Finally into DIV 1 (purple) after almost a year on CF :D

→ Ответить

9 лет назад, # ^ |

Congrats

→ Ответить

thezodiac1994

9 лет назад, # ^ |

Thanks.

→ Ответить

irfan_gooner

9 лет назад, # |

Answers to both of my wrong submissions (WA on pretest one in Problem A and Runtime Error in Problem D) is showing correctly on my computer. anything i am missing here?

→ Ответить

9 лет назад, # ^ |

When a[i][j] == 3 || a[i][j] == 1 you should skip entry. i cant understand your code seems like you do the same for a[i][j] == 2 and it give WA.

→ Ответить

Wild_Hamster

9 лет назад, # |

+42

In my opinion, problemset was like A-B-B-B-D, but it's just my opinion.

→ Ответить

Igorjan94

9 лет назад, # ^ |

+20

A A B A D in implementation imho

→ Ответить

9 лет назад, # |

Can anyone tell me why this solution gave WA for test 11 question C? I used DP where prev=0 means previous tree wasn't cut, prev=1 means previous tree was cut to left, prev =2 means previous tree was cut to rightLINK

→ Ответить

9 лет назад, # ^ |

its simple because you assume tree number 2 will always be cut in code: int ans=1+func(2,1); ans=max(ans,1+func(2,2));

→ Ответить