Hello!

Codeforces Round #479 (Div. 3) will start on May 6 (Sunday) at 14:05 (UTC). It will be the first Div.3 round in the history of Codeforces. You will be offered 6 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

Remember that only the *trusted participants of the third division* will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a *trusted participants of the third division*, you must:

- take part in at least two rated rounds (and solve at least one problem in each of them),
- do not have a point of 1900 or higher in the rating.

**Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.**

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to Ne0n25 for testing the round.

**UPD**: Thanks a lot to testers dreamoon, eddy1021, step_by_step and egor.lifar who agreed to test the problems and found the mistakes. Now we are ready to start the round!

I hope that you will like the problems. If suddenly something does poorly with difficulties of the problems, then we will adjust the difficulties in the next Div. 3 rounds.

Briefly about myself. My name is Vladimir Petrov, I am studying at the 3rd year at Saratov State University and from the high-school I am studying at SSU Olympiad Training Center. In ICPC I participate in the team "Saratov SU Daegons" with PikMike and Ne0n25. I like reading and watching science fiction. I’ve read "Song of Ice and Fire" 3 times and wait for publication of 2 more volumes.

Good luck!

**UPD2**: Editorial

**UPD3**:

Congratulations to the winners (official results):

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | cMartynas | 6 | 69 |

2 | nimphy | 6 | 117 |

3 | iman12 | 6 | 124 |

4 | mandinga | 6 | 128 |

5 | raffica | 6 | 144 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | greencis | 36:-8 |

2 | Tlalafuda__Tlalafu | 10:-1 |

3 | STommydx | 9:-1 |

4 | dalex | 8:-7 |

5 | dreamoon | 4:-3 |

6 | shnk | 2 |

97 successful hacks and 297 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | kuzmoid | 0:01 |

B | c650Alpha | 0:04 |

C | Milhous | 0:08 |

D | Milhous | 0:11 |

E | s0mth1ng | 0:09 |

F | DoveDragon | 0:14 |

What is the relationship between div3 & div2 problems. For instance A div1 is equal to C div2

This contest is for div3 only. I do not think there will be a relationship between div2 and div3. I mean can something be easier than Div2A? Maybe Div3A+Div3B+DivC are so close to Div2A. We will see after the round :)

This contest is only Div3 , so i don't think there's any relationship with Div1 or 2.

"We plan to include in these rounds simple training problems that will help beginner participants to gain skills and to get new knowledge in a real contest."

I found a mistake for you :)) Please correct it.

Thank you, it is fixed now!

So will there have Educational Round like the time before updating? :P

Finally!Last three lines was awesome . :D

:P

"The round will be hosted by rules of educational rounds..." Honestly, It's really boring! Given that this is a div3 and problems should be easy.. Then what is the use of the hacking phase ??!!

We will experiment with formats of Div. 3 rounds, but there are some reasons to start with rules of Educational Rounds:

This is what I have been waiting for long time: "**I prefer Div. 3 participants to solve problems during a round instead of spending time trying to hack**". Hacking is a good way to develop debugging skill. But a div3 participants should not spend the whole time trying to hack a problem just to increase rating instead of solving another problem.

Thanks Mike.

But what about the feeling of DIV3 participants. I really enjoyed codeforces round DIV1 / DIV2, due to div1 and div2, DIV3 is also should not be affected. div3 also must be same as daily codeforces round not educational type.

As Mike said, div2 rounds are not affected. So you can just ignore div3 rounds.

First time I saw

about myselfin any round announcement.You might want to take a look at this!

Your link is not clickable. Check it.

where you saw you?

It's rated for me so :D

unofficial participator for the first time :) :D

Why extended ACM-ICPC? Why not like a normal Codeforces round?

Here

Will I become Div.4 user if I lose rating in Div.3 contest?

As of 5/5/2018, there is no such thing as a Div. 4 user. The lowest is Div. 3.

Dude, don't you know about sarcasm?

and neither humor

Hello, If this round is following Educational Round formats than I want to bring something to your notice. See the picture attached.

My friend solved Problem A and his solution for problem C failed. I solved Problem C and my solution for problem A failed. I just want to point out that Problem C was tougher than Problem A and anybody who solves tougher question should get better rank. I think people will say that it is for learning new skills and I should not concern myself with the rating. But I still think that this is unfair.

Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy.So, I think, there will be no issues with Div3 problems, as at some points, we will figure out that it is eventually too easy, regardless of which problem in a contest (A, B, C, D, E, or even F).

In other words, soon we will realize none of any Div3 problems will be any tough to be obliged to be distinguished.

Still, the point system is better than the penalty system in my humble opinion.

ACM-ICPC scoring is used in many contests.

If you don't like the format of educational round, you don't have to participate.

If you don't want to be rated because of these rounds, you can always do virtual participation of solve problems regardless.

I am fine with whatever format you want to use, I am asking is it fair?

1) You complained about the rules of the contest.

2) You just said "I am fine with whatever format"

3) ?????????

4) Now you ask if the rules are fair.

Yes, they are since your signed up knowing them.

As I said, if you disagree with this type of scoring just don't participate. If you are annoyed at messing up on problem A check over your code more before you submit.

Hmm, thanks for helping.

One more chapter is going to open from May 6 (Sunday) at 14:05 (UTC)..!!

Div3 => noobs?

once you, too, was thus noob

Hey bro cyan isn't too hot either. We're all noobs, just some less nooby than others.

Effective...

So which one do you like better? The books or the TV show? Vovuh

I like books better than the TV show, but the TV show is also wonderful =) Especially Natalie Dormer =)

You've probably meant Natalie Dormer

Oh, yes, you are right, i made a mistake

Can't Wait :D****

Still messi is better than ronaldo

Hoping For short Problem statement

As CF is introducing div3 for begginers, it is also good to change title/color to make it interesting for begginers, like 1000-1200 is begginer, <1000 is newbie !!

Earn bitcoins while browsing the Internet https://getcryptotab.com/1065838

Looking forward to concise problem statements without unnecessarily long storylines!

I think it's need to make div 4 for under 1000.

Div3 finally comes! No more falling scores!

One can only hope^_^

OK, then just bless!

is it rated?

lol

tourist do you want to join us in div 3 :) ?!!

don't worry, they'll open div 0 for him

for tourist? I think Petr has higher priority in the current time.

see who will put problems for him Your text to link here...

He does not even need to look to the problems to solve them. :)

lol.u can't solve some problem even by reading them :)

Will div 3 participants be allowed to take part in div 2 contest?

Obviously...

Will it be rated for div 3 contestants?

when it is only div 2 contest then the user who's rating is less than 2100 can participate in this round and when both div 1 and div 2 round will be held , user who's rating less than 1900 can participate in div 2 contest as a official participant.... official means rating will be update

How many problems will be there?

You will be offered 6 problemsWaiting for a DIV2 contest. The sooner, the better. The more, the merrier. :)

"8093" Registration in Div 3 !! wow <3 .

I usually solve C in div2..Which prob i should choose to solve in div3 ??

Problem A : Print "Hello World"

HTTP Response: 500, 502. Website failed.

20 minutes of penalty is too much.

for a 2-hour contest, indeed. 20 minutes seems better with 3~5 hours contest.

Failed at B

Don't understand what C is asking

Input #1 of F is wrong? Surely largest is 5~ cba to attempt as maybe I'm misreading like C

RIP, time for gaming instead

AH ? I can't register while the contest is running !

What a pity!

20 minutes of penalty is too much.

I used 19min to solve all the problems.

But I got 1 penalty.. doubled the time..

20 mins of penalty is standard ACM rules. It encouages coding correctly instead of coding fast, which I think is ok. Also, the contest is targeted at people who can't solve all problems in 19 mins :)

Penalty is calculated as the sum of times each problem solved (+ 20mins penalties), not as the time of the last solution. So it's not doubled because of that, don't worry :)

You're right.. But I got "502 Bad Gateway" for 30 mins LOL

So? That's completely irrelevant to the discussion. Nobody cares how well you did in a div3 contest, mate.

Thanks Vovuh for this round , and thanks MikeMirzayanov for Div3 !!! This is the first time that i am able to solve all problems .

Spending 30 minutes to solve the last problem. Is it a little bit slow compared to how such contestants like me (1800s-rating guys) are supposed to be?

Why are there some (not all) unrated accounts in the official standings?

What exactly? Please, give me some examples of such handles.

official rank #1 for me is readers5 and rank #4 T_van for example

That happens pretty often in div2 if not all the time, even in older contests.

My guess has always been that some of those are smurf accounts created by high rated people just to be on the top spots in a contest. A lot of them are legit skilled people on their first contest, but some are left inactive after one contest.

Yes but the thing is that it's not supposed to happen with the new div3 rounds.

Sorry, you're right. Forgot that.

I think this was too easy even for div 3.

I agree. In Div 2, very few experts (the highest eligible rating) solve the set. In this one nearly every specialist and their mother solved it (not really but you get the idea). You never see 200+ eligible participants solve the set in a round.

Yes, It should be a little harder so only about 50 or less gets full. NOT 200. Even me solved the whole set! Maybe it should be for users whose rating less than 1400

First time in my whole life! I solved all problems! (but... It is div3)

Holly cow, I'm experiencing something in Java I never ever experienced in a contest!

For problem "C" I'm doing a sort using Arrays.sort. My code times out (it takes more than 2 seconds for testcase 6). But, if I randomize a little bit the input, i.e., instead of doing:

I do:

the solution passes!

Does anybody know how can this be?

It seems that there are arrays that take O(n^2) time to sort in Java, using Arrays.sort(): http://codeforces.com/blog/entry/4827

Most likely test case 6 is such an array and was designed to discourage people to use the O(nlog(n)) solution instead of the linear one...

Is there simple linear solution for C?

Yes, you can use quickselect to find the k-th smallest element in an array in linear time: https://en.wikipedia.org/wiki/Quickselect

In C++, you're right (because there is std::nth_element). But I mean that in many standard libraries, there is sort, but there isn't nth_element. So in this languages linear solution will be much harder.

No, quickselect has a worst case of n^2, similar problem to your sort

Quickselect have O(n^2) worst time, nth_element in C++ have O(n*logn) worst time, but here is Medians of medians algorithm (or Introselect variation), which have O(n) worst time.

But it's not simple (or not obvious at least).

It seems the difficulty is something like:

Div3 A, B = Div2 A

Div3 C = Div2 B

Div3 D, E = between Div2 B and Div2 C

Div3 F = Div2 C

I think Div3B is too simple for Div2B

Possibly. Honestly Div2 A and B feel more or less the same difficulty, at least in my opinion. Only thing I've seen is that Div2 B sometimes has annoying edge cases, so yeah you're probably right, it's probably A level.

Intially i was not able to look at question and was getting a continuous error of Bad Gateway 502

:(

I Accepted F after contest finished 1 sec...

(Sorry for my poor English)

how can solve the ploblem c?

Case 1:- If

`k=0`

then check if`arr[0]=1`

. If yes the print`-1`

else print`arr[0]-1`

.`Case 2:- If`

k==n`simply print`

arr[n-1]`Case 3:- Check the value of

`arr[k-1]`

. If`arr[k]==arr[k-1]`

then print -1 else print`arr[k-1]`

This is sample test case 2.This is all in a sorted array.

oh ,i forgot to judge if arr[0]==1, anyway,thank you!

Sort the elements, and the k'th element (1-indexed) is your answer. If k = 0, then just subtract 1 from the first element.

The no solution cases are when the k'th element equals the k+1'th element (why?) and when k=0 and the first element is 1, because subtracting 1 would be outside of your range (you may be tempted to try to be clever and subtract 2 so you don't have to handle that case separately, but that fails if the smallest element is 2).

I don't get how, for k=0, there could be an answer different than -1.

I mean, as I read it, there is no x «such that exactly 0 elements of given sequence are less than or equal to x.», regardless the value of the first element. Am I missing something?

What exactly do you mean by «because subtracting 1 would be outside of your range»? I guess you refer to the range [1, 10^9], but why should I subtract something?

Thanks

k=0.

Output a number x such that 0 (no) elements from the sequence are less than x.

If the smallest element in the range is l and max is r.

Then.

If you take an element >r then all elements will be less than r and k=0 will not be satisfied.

If you take an element>=l and element<=r then some elements in the range will be less than x and again k=0 will not be satisfied.

As for last case if l==1 then you can output 0 because no(0) elements will be less than 0. However since the answer must be in the range[1,1e18], in this case the answer will be 0. For all other cases output l-1.

Say your sequence is 10 26 4, and k=0.

Simply output the number 3, and that is 0 elements from the sequence are less than or equal to 3. If the smallest element is 1, then there is no answer that is in the range from 1 to 1 billion.

That make sense. I should have been less superficial. Or more, depending on how you view it :) Thanks Kognition and horcrux2301

Can E be solved using this logic: LINK

if you mean E,E is simple. Just for each connected component see that every node is connected to

exactly2 other nodes.I tried this for problem D.

Take a boolean array

`check[n]`

and mark all as false. Then I tried making chains. Take the first element and mark it as true and this will start a new chain. Then for each other false element in array check if it can be added to the chain started by this element, either by appending it to the beginning or to the end. If yes mark this as true too. For beginning, check if the new element divided by 3 is equal to first element in chain or if new element multiplied by 2 is equal to first element in the chain. Similarly we do for the end.However, I couldn't figure out how to decide a way to print all these chains in a valid manner. Is there any way to do figure this part out.I think your approach is wrong or maybe i understood it wrong anyways this is what i did: A move consists of dividing by 3 (if divisible) or multiplying by 2. This means given a number we are taking away 3's and giving it 2's. So a state once reached will never be reached again. Why? Because to reach that state either you need to multiply by 3 or divide by 2 both of which is not a part of move. So what we can do is treat every element as starting element once and try generating the sequence from elements available. If all the elements are used you can just print that sequence.

This can be done by thinking of an array as a directed acyclic graph, and do a topological sort.

No need for directed graph...just make undirected edges and start from any end that fits into any one of given two operation.

Thanks, soham_1234. I got it.

Can you check out the link I shared? There is a formula given to get the count of all cycles. Is it correct?

No, take the graph

4 6 1 2 2 3 3 4 4 1 1 3 2 4

Number of edges = 6. Number of vertices = 4. Number of connected components = 1. 6-4+1=3, but the answer is 2 because there is only one connected component and it isn't a cycle.

Got it. Thanks.

it has defined cycle differently not the traditional cycle we know of. See the examples and diagrams.

The contest page was not visible for the first 10-15 minutes, and the problems were not accessible for the mentioned period (well,at least for me). So will it be justified to keep it rated?

Can someone help me? http://codeforces.com/blog/bakrocker

was this contest rated as written in the blog ?! "Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you." I didn't see any rating for the problems.

Ratings will be changed after whet Open Hacks Phase ends (in 12 hours approx)

GOGOGOGO SO FST LKE A SNIC X

Thnx Vovuh for your efforts in making harder pretests. Really Appreciate it ! :-)

The round was good! Even though problems were easier quality remained high. It kind of reminds me of Atcoder Beginner Contests.

Angel.Yan (rank 578)'s submissions and __beyond (rank 581)'s submissions are almost the same (the differences are libraries, useless fors, spaces, blank lines). I believe they are cheating. Correct me if I'm wrong. Vovuh

problem C ;

Output Print any integer number x from range [ 1 ; 10 9 ] such that exactly k elements of given sequence is less or

equal thanx . If there is no such x , print "-1" (without quotes).equal to not equal than

Vovuh

Thanks, but next time please send it via private message.

I can just delete the comment if you want !

Not necessary =)

Can anyone please explain why this submission got TLE while this one got AC ? I just changed the language from Java to C++. There was no I/O issue as well. I was clueless about my solution getting TLE and then in just hit and trial I converted it to C++ and it got accepted. :(

Vovuh explained here: http://codeforces.com/blog/entry/59281?#comment-428862

"6-th test is anti-qsort test especially for Java solutions. Replace int with Integer and it will be ok."

Oh! Okay. But when it says specially for Java solutions, isn't it a bit unfair? Anyway, Thanks for the contest Vovuh ! :)

If I didn't add this test, somebody else would. So it's fair i think

Okay, got it Vovuh . Thanks for the Contest !

The fixed problem at the beginning will affect penalty and so the rating changes.., many contestants have 2 or more problems tested at the same time and submitted earlier so..

Is it possible to solve problem E using disjoint set union?

my idea, maybe wrong.

UPD: solution 2

In fact, we are to check, if after each edge deletion, component becomes tree.

However, this solution is very complicated.

Simpler ones:

component is good if each node touches 2 edges

component is good if it contains k nodes and k edges (sorry, it turned out to be wrong)

"2. component is good if it contains k nodes and k edges"

Actually, this approach is incorrect as this is not a cycle component.

I tried this problem using disjoint set union. If I find a cycle, I checked if the degrees of the nodes having this edge is 1. If they aren't 1, that means that connected component is no longer a valid cycle. If they aren't in the same connnected component, then I check if any of them were part of a cycle. If they were, then I change that value to 0, signifying that the corresponding cycle is no longer a cycle. Can someone tell me what I'm missing here? I got a Wrong Answer on test case 18.

Really we enjoy this contest . Thankyou Codeforces team

Look at what Tlalafuda__Tlalafu does in hacks section (for problem B). He specifically wrote several solutions with this kind of code

And then he hacks himself several times.

Is this kind of behaviour legal in codeforces?

Why can't I hack solutions on C++17? The system gave me an "Unexpected verdict" several times on different solutions. Please rejudge all the hacks with this verdict, it is very important.

UPD: I can't even hack my own solutions which aren't on C++17. What's wrong, Codeforces?

Could you please explain the test you used to hack so many F solutions? I tried to find something in common in the solutions you hacked but failed to see the pattern. Your test seems to be tricky.

Div 3 noobs like me didn't know that using unordered_map makes the solution O(N^2).

http://codeforces.com/blog/entry/44731

So, this was an "anti-hash" test against STL's unordered_map... I'm new to Educational Rounds so I didn't think people actually use dirty tricks like anti-hash and anti-quicksort. I don't get why people do this but this broke all solutions with unordered_map instead of map. Well, learned something new, won't be using unordered_map on contests next time :)

I believe this hack does not necessarily mean that you should not use unoredered_map at all.

The thing is, the standard hash function which accepts integer values does nothing, it just returns the same number it accepts, so there is no problem with hashing itself.

The problem is solely with buckets count, because in a hash table there is a remainder operation "key % buckets_count" and in case if you take a lot of numbers with the same remainder, unordered_map will work slowly.

However, if you use it and call reserve(10000000) in the beginning, you will fix the amount of buckets to be over 10 millions and the hack simply would not work anymore. The maximum time conplexity will not be more than 100n, which is enought to pass 1 second time restriction.

Correct me if I am wrong.

This wasn't exactly what I meant, but I agree that reserve() will work for F. The problem is that this workaround will only work for this particular problem because of the 10^9 restriction. Given less tight bound (10^18) it will still fail.

And with 12-hours open tests you can even generate counter test for any particular hash function from universal family (not necessarily identity) and any particular buckets_count. The only way to protect against this attacks seems to be random sampling of hash function from universal family with good source of entropy.

The point was — why do you even need to bother about such details on a contest if you can just use map instead? It might be a bit slower but at least it has worst-case guarantees and it allows you to focus on a problem itself.

Problem solving is fun. I don't think it's fun to protect against hashmap-attacks.

I see, I would myself prefer map container to make sure my solution will work.

I was just too disapointed by the fact that a programming contest makes us choose the structure which 10 times faster in 0.0001% cases and 10 times slower in 99.9999% cases, that is why I tried to figure out the way how to use unordered_map and remain unhacked.

Anyways, codeforces is not only about good ideas of solutions, it also requires us to know the low level of how c++ works, it is just as it is.

I think it's because some of the author/tester solution fail on the same test.

Testers' solutions receive time limit exceed, because of this your hack gave an "Unexpected verdict". I hope I have fixed it now. Sorry for long delay.

Will there be any tutorial for this round??

It's already posted, here

is it rated for newbie ?

Yes

Hello Vovuh. My rating is 1500 because I hasn't joined any contest before. However you said "if your rating is less than 1600, then the round will be rated for you." So why I'm not rated after this contest.

The contest has not done with the large test case. So we need to wait for the final result and you will see your ranking changes.

i passed all of the problems!! yayyy

When will system testing start?

Yeh same question,i wonder how can i know when the sys test will start ? the contest just said "Finished"

When will the ratings be updated?

Ratings are updated as of posting this.

Pls, somebody explain, how my solution http://codeforces.com/contest/977/submission/37965169 for Problem F was hacked. But when i changed "unordered_map" to "map" it got accepted. It seems realy strange to me

Afaik Unordered_map is slower than normal map.

That'_s not true. unordered_map is getting slower when many hash collision happens. Otherwise, unordered_map is much faster than normal map.

unordered_map is based on Hash table. Normally a search operation of hash table works in amortized(1) but worst is O(N) (caused by hash-collision). std::map, on the other hand, is based on red-black tree, which has O(logN) complexity in search operation on average. Your solution was hacked by anti-hash test.

Why unrated participants get rated in this round?

You said that they need to do at least 2 Div.2 contest and solve at least 1 problem to get rated

`Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.`

So although unrated participants are nottrusted, they are still rated.But why they but them in a separate room?

Can anyone tell me what's wrong with my F approach? 37990081

You ignored MAP[A[i]] that was originally stored.

test : 9 10 11 12 8 9 10 11 10 11

ans = 4 yours = 3

Oh.. i thought map in c++ overrides values that exists already just like in Java

Yes, so change your "//m.insert(mp(a[i], m[a[i] — 1] + 1));" to "m[a[i]]=max(m[a[i]],m[a[i]-1]+1);", and this is the AC code which has a little change from your code

Yes, i got AC, thank you ;)

Thought C++ maps work as Java maps where you just use map.put(v1, map.get(v1 — 1) + 1) and it overrides v1 value if exists

How about the ratting changes? Can a people get the same ratting changes if he got the same place(among rated people) in div 2 and div 3 contests?

It's a wonderful effort for beginners like us to learn and improve !

It grow the internal effort of beginner programme,make hope to became a good programmer, I like it

You might also would like to take a look at the incredible achievement of Tlalafuda__Tlalafu, who made 10 wrong submissions for problem B and found bugs in all of them!

Думаю, что вам также будет интересно увидеть невероятный успех Tlalafuda__Tlalafu, который не поленился отправить 10 неверных решений по задаче B, а после этого смог обнаружить баги в каждом из них!

He just hardcoded a wrong output for some random input 10 times... is this sarcasm?

is no one here concern about rating inflation? In a normal div2 round, it seems like there's usually about 100 users who will be promoted to expert and some of the expert will drop, but this round, there seems to be about 250 promoted with 0 expert demoted.

I would request the host to conduct more number of Division 3 contests. I am sure that many other users like me with rating less than 1600 are finding it difficult to solve Division 2 problems easily and obtain better ranks. I would suggest to conduct 1 Division 3 contest for every two Divison 1/2 contests so that we can gain confidence and hopefully aim to perform better at Division 1/2 contests.

I would like the opinion of other people too.

Thanks.