Vladik's blog

Codeforces Round #394 (Div. 2)
By Vladik, 8 years ago, translation, In English

Hi there!

Codeforces round #394 for the second division will take place at the time of Tuesday, 31 January 17:35 MSK. Participants from the first division can compete out of competition. Contestants will have 2 hours and 6 problems to solve.

  • Problems were developed by me (Vladislav Vishnevki) and Denis Anischenko (altruist).
  • Alexey Vistyazh (netman) helped us as a contest coordinator.
  • Aliaksandr Drapko (sdryapko) and Alena Yaros were reading the statements carefully.
  • Vlad Khala (haposiwe) tested the round.
  • Olya Yakovchik drew amazing illustrations for the problems.
  • Yuri Shilyaev (hloya_ygrt) translated editorials and round announcement for you.
  • And of course the round couldn't happen without (MikeMirzayanov), the author of platform polygon and codeforces, and also author of the idea to one of our problems.

Thanks everyone listed for the contribution you made to the contest preparation!

The main character of the legends is tiger Dasha, which loves to solve puzzles and make origami figures.

Good luck everyone! :)

UPD Round will consist of 6 problems.

UPD 500-1000-1500-2000-2500-3000

UPD Contest finished. It was decided to make round unrated, because codeforces is unstable now. I am really sad about that :( I hope everyone found a problem he liked. Editorial will be posted soon.

UPD Top 10 participants from second division: 1. DefinitelyNotGreenGrape
2. udwztb804
3. Inhibitor
4. Border_Collie
5. HanwhaEagles
6. Vergara
7. zelta
8. GGOSinon
9. P_Nyagolov
10. tonykky

Top 10 participants from first division: 1. eddy1021
2. Myungwoo
3. dreamoon_love_AA
4. natsugiri
5. Shik

Congratulations to the winners!

UPD Editorial.

  • Vote: I like it
  • +346
  • Vote: I do not like it

Comments Comments (232)
| Write comment?
»
8 years ago, # |
  Vote: I like it -52 Vote: I do not like it

Will be easy contest to all of you, i feel

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I am having my exams... but still eager to participate in the contest... Hoping for a positive rating change.

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it -38 Vote: I do not like it

→ Reply
»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Tiger__the national animal of both Bangladesh & India. It lives mainly in Sundarban Mangrove Forest.

→ Reply
»
8 years ago, # |
  Vote: I like it -23 Vote: I do not like it

It's time for me to change the color again :P

→ Reply
»
8 years ago, # |
  Vote: I like it -191 Vote: I do not like it

Let me introduce myself to you all:

My name is Donald John Trump the 45th's president of the great USA, but mostly famous as the father of Ivanka Trump in the past period I conquered the whole USA through the elections, and I raised a campaign called "Let's make America great again!!!" So now, i am planing to conquer the whole world, but it's you top rated American coders who I seek there help, the likes of:

scott_wu, ecnerwala, waterfalls, DemiGuo, winger, cgy4ever, zxqfl, lawrenceli, pacu, msg555 and others....

You should help me conquer Russia, and as a start with your help for your beloved elected President you will send me your Accepted codes in tomorrow's round, just to help me finish first in the round, and end those stupid pair of Russians tourist and Petr and that crazy china town boy who changes his handle every year jqdai0815, to end there dominance on the top standings...

Top American coders send me your codes or I will send my FBI agents, to kick your asses away from the USA borders...

God Bless you, God bless America, and Let's make America great again!!!

PS#1:

if(you_voted_for_me)downvotes++;
else upvotes++;

PS#2: I hope you liked my new hair style...

→ Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it +4 Vote: I do not like it

In the email, it is mentioned that there would be 6 questions. Please confirm? I see above its five.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Round will consist of 6 problems.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      I like six problem contests, it cause reasonable deviding scores as usual. Thanks.

      → Reply
»
8 years ago, # |
  Vote: I like it -23 Vote: I do not like it

As a Div. 2 contestant, I want to thank you for preparing the contest for us.

And since it's a Div. 2 contest and there will be a lot of competitors from both divisions, I want to kindly ask the Codeforces team to make sure we will have an acceptable queue and a responsive Codeforces. Thank you.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

Very cute tiger, I like it. Where is it from or it was made by you just for the contest?

UPD: Oh, sorry, I usually miss the part which thanks people :))

→ Reply
»
8 years ago, # |
  Vote: I like it -48 Vote: I do not like it

To all Acmers, Last warning, if you don't send me your codes, then I won't let you travel to my country for the World Finals, I will be there alone to win the first place...

God Bless you, God bless America, and Let's make America great again!!!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    At this rate you'll be able to get the worst Contribution in CF.

    → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

what is the score distribution?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck lads !

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck!

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Good luck amigos!

→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Hoping to learn something new regardless of a rating change. Good luck to all, and a big thank you to the contest setters for making CodeForces awesome

→ Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Site very slow

→ Reply
»
8 years ago, # |
  Vote: I like it +71 Vote: I do not like it

I don't think it's a good idea to make this round unrated...

→ Reply
»
8 years ago, # |
  Vote: I like it +57 Vote: I do not like it

It's such a pity that this contest of all faced technical issues. I really loved the problem set of the contest, and the difficulty level of questions was well balanced.

→ Reply
»
8 years ago, # |
  Vote: I like it +67 Vote: I do not like it

Thank you Codeforces!

I am happy to see this nice and cute picture for the first time :D

→ Reply
»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

It's a shame this round became unrated, though the problems A-E were all on the easier side.

→ Reply
»
8 years ago, # |
  Vote: I like it +38 Vote: I do not like it

I don't think the standings not working is a good reason for the contest to be unrated, it shouldn't affect a lot if anything.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I agree. Everything was fine but the standings. It didn't offer an unfair advantage. Therefore, it was a bad call to make it unrated.

    Kinda feel like this was a waste of time.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Rooms were closed , so people who wanted to hack , didn't have a chance to !

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Are you sure? My solution was hacked by someone.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Yes, it stopped working after about an hour and half from the start of the contest .So , you could have been hacked during the first hour and half

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Aside from the standings, hacking was also influenced.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Also, while it probably depends on the person, in my case I do check the standings quite often. I happen to be a slow coder. So I'm tactical of which problems to solve (I won't have time to code all of them) and which problems to hack, etc. The standings serve as great reference to what problems can be approached quickly (not necessarily easily) and which problems may have easy to hack cases.

    → Reply
»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

me passing problem E's pretest.

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I think this error is not the first time. I think this site need to move to a cloud server like Amazon.

→ Reply
»
8 years ago, # |
  Vote: I like it +58 Vote: I do not like it

The first time I ever solve 5 problems during contest and it's unrated... FML

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    mine was 4 .

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    The same with me, bro. Five. Now I hope all of them will fail systests, otherwise — I want to kill myself

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    My internet traffic limit off, so I was pay going to paynet, solve 4 problems, surprise contest is unrated...

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Yay my C didn't pass, I can now sleep at night

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      ++++ XD

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      C failed on the 7th test. A was hacked but then resubmitted. A,B,D,E solved.

      I'm thankful to this round that finally I found my long-lost twin)

      → Reply
»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

tfw tyou don't know what your score is

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Unrated when I solved 4 problems :(

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It Was Interesting And Exciting,But hated problem B Explanation :/ took me 45 mins to start understanding, overall it was nice

Thanks

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

it is so painful that this round is unrated.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

I am really sorry for you. Compared to what we see recently, your problems were so amazing :))
Edit: In my opinion, if what I wrote is correct, then E was way too easy for E. On the other hand, F is a very beautiful problem. I think I can solve it but the time wasn't enough for me. Can anyone tell me if I am right? My idea is to find some random picture which gives us a minimum distance. And if I find it, then there is surely some special photo which gives the same minimum distance. :)

→ Reply
»
8 years ago, # |
  Vote: I like it +114 Vote: I do not like it

Sorry, it was a kind of magic for me. We didn't touch the code around of standings about years. And today it started to throw exception in unexpected place. Additionally I'm out of Saratov now and it was impossible to fix it during the contest. For sure, I'll find the reason!

There were 2 problems here by my ideas and it is an additional reason for me to be sad today.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

How to solve E? I started with root at origin and then going 1e16 far for level 1 in 4 directions, 1e16 / 2 far for level 2 and so on. There was a bug in my implementation, so I don't know if it's correct or not.

Really great problems though, thanks for the contest!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Yes, that's the main idea.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Man, it is nice to know that I got the idea right at least :D

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I think I can start from random node (let's it'll be the first) and then my first step would be 2^28, the second 2^27 and so on, can't I? Even if my tree grows only in one side it will fit the requirements.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess we should start from the origin first going 2^n in four directions, and for each new level on the tree we should divide that value by 2.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    with 1e16 + 1e16/2 + 1e16/4 + ... + 1e16/2^(n-1) you will get integer overflow.

    → Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Thank you Codeforces!

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

very good contest i loved the problems . i wish it was rated !

→ Reply
»
8 years ago, # |
  Vote: I like it +23 Vote: I do not like it

This creature is going to be my nightmare for the next couple of days !

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

first time solved 3 problems, and unrated((((

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

It was a really interesting problem set actually , it's a bummer that it was unrated , although i don't see what does the standings page have to do with the rate.... thank you for this round but i hope it's rated

→ Reply
»
8 years ago, # |
  Vote: I like it +22 Vote: I do not like it

I wonder if the reason for the system error was the abnormal amount of hacks... did total hack counter overflow? :)

On another note: thanks to creators for the interesting problem set with nice difficulty distribution.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Constraints for problem A is pretty interesting .. my solution got hacked within 30 seconds of submission.

    → Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Problems were little bit easier as compare to other regular contest. But I think there was no problem in submitting answers and dashboard. Technical problem was only in room and standing page, So I think it is not a good decision to make this contest UNRATED.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Not being able to make hacks can be a big roleplayer in the outcome of the contest.

    In addition, the site was even slower than usual today. I saw 502 — Bad Gateway many times too.

    → Reply
»
8 years ago, # |
  Vote: I like it +24 Vote: I do not like it

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what was hacking test for problem A? As I understand the statement if the difference of those two numbers is at most 1, then there exists such segment.

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

My first codeforce round ever is very memorable....

→ Reply
»
8 years ago, # |
  Vote: I like it -27 Vote: I do not like it

thanks mike

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    He has explained, that it was an unexpected error. Don't be sad, if you did so good this contest you can do next one as well. Good Luck

    → Reply
»
8 years ago, # |
  Vote: I like it +124 Vote: I do not like it

That feeling, when you were in top 10 and then notification tells you that the round won't be rated.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +96 Vote: I do not like it

    Ahah... But top 1)

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Oh my god 141 successful HACKS only in top 10 !!! i don't see where the problem was with the round ... i think it should be rated.

    → Reply
»
8 years ago, # |
  Vote: I like it +32 Vote: I do not like it

WHENEVER PROBLEMSET IS VERY NICE,WHY CODEFORCES DO CONTEST UNRATED?

→ Reply
»
8 years ago, # |
  Vote: I like it -17 Vote: I do not like it

SHIT! SHIT! SHIT!

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i would pass out if my E get accepted !

→ Reply
»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

The odd thing is that the disabled standings somehow affects everyone, and the round is made unrated. Opening standings does not make you think faster or code faster. Does not make that much sense for me, I think.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    The issue is say somebody locked a problem to hack. Now they can't hack, and say they find problem with their solution. Now they are very disadvantaged, because they have none of the benefits of locking problem, and all of the downside, by no fault of their own.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      I must disagree. ~10 minutes before contest end, I successfully hacked a solution of a person in my room. So hacks weren't affected(standings couldn't be opened though)

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You must tell me your ways, I must know, how could you hack a solution when the room standings were unable to be opened? Or are you staying that you were able to open your room standings, as I tried many times and was not?

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it -21 Vote: I do not like it

          Yes, I was able to open it. Maybe it's because you are Div.1, who knows? And looking at the hacks there have been some at 19:33, so it has been possible to do hacks during the (almost) whole time.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +18 Vote: I do not like it

            You know, some people could hack  ≠  everyone could hack.

            → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's what I am talking about

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think hacking was the problem because room page wasn't working too. but I still think make this round unrated was not a good idea

    → Reply
»
8 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Is it rated?

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

can someone please tell me how to hack others solution? What i did was, locked my solution, then i didnt know what to do next. help please :(

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    you can enter your room then click on other contestants' solutions in your room and then click hack. Then a window for writing your tricky testcase will appear.

    → Reply
»
8 years ago, # |
  Vote: I like it -26 Vote: I do not like it
We must
→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

good problemsets :) I'm sad to hear that it's unrated, is it really because of the scoreboards?

→ Reply
»
8 years ago, # |
  Vote: I like it +62 Vote: I do not like it

Ok. Let's vote: Click

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problemset was very good! It's unfortunate that the round is unrated!

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how to solve B?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    If the sorted arrays are the same, the answer if yes.

    Then let's move any player 1 step back. Subtract 1 from all the values in smb's array (remember that 0-1=L-1). Check again. Shift again, check again, etc.

    Do it until you make a full circle of shift. Total complexity is O(L*N) or O(L*N*log N) depending on how do you handle sorting.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    determine the space between all the barriers for Kefa and Sasha! Keep them in two vectors. Then compare one vector with another by rotating the elements of one vector!

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Create an array of the distances between each adjacent obstacle in the array input. There will be two such arrays. The basic idea is that these two arrays should be a cyclic permutation of each other for the track to be same, and this can be easily checked by checking if Array B is present as a contiguous array in Array A appended to Array A.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If two tracks are identical , then the difference between every two consecutive barriers are the same. You calculate the difference between every two consecutive barriers and than you must find out if they can be covered in such a way that the differences are the same.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks to all of you.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Assume that 1st person starts from 1. and then mark which points he visits ..

    And then for the second person .. Check all starting points and find which points 2nd one visits.. if you find any solution where they both visits same points then print "YES", otherwise "NO"

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Can be done in O(n) and it's super easy in python.

    First find the lengths of all the intervals anti clockwise. This can easily be done by taking differences between consecutive numbers. interval1 = 2nd element — 1st element and so on..

    After that append the first interval as L+1st element-last element

    Make 2 such interval lists for both the arrays.

    Now join both the interval lists to make a string.

    Now you have 2 strings s1 and s2. If s1 and s2 can be found by rotating each other then it's the same track. To find how to do this refer to this awesome thread http://stackoverflow.com/questions/2553522/interview-question-check-if-one-string-is-a-rotation-of-other-string

    My Python solution http://codeforces.me/contest/761/submission/24306742

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can make a string which represents places with and without obstacles. First make a string of length L: ',' x L. Second change , to e.g. o in appropriate places. Make this procedure for both runners, got 2 strings. Finally instead of rotating first string, you multicat it by 2 (e.g. ',oo' x 2 ==> ',oo,oo'), and search if shorter string is found in longer one. Solution with Perl regex — 24394802

    → Reply
»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Codeforces really needs to scale up to handle more users.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Yea sad, I ended up having to start the contest 3-5 mins late as the main contest page wasn't loading..

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the next contest be held? :P

→ Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

We wish you health,codeforces!!

→ Reply
»
8 years ago, # |
  Vote: I like it +197 Vote: I do not like it

ugh..

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What does standings have to do with problems. Can someone explain why this round is unrated????

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    In a contest with plenty of hacks (such as this one) not having access to ROOM can change the outcome of the contest quite a bit.

    → Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it +34 Vote: I do not like it

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it will be better for Codeforces to have some external servers like from Amazon or Microsoft (cloud). (Use it when it is needed) We had 8k registered users for this contest, probably, the problem is because of underperformance of current servers.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it will be better for Codeforces to have some external servers like from Amazon or Microsoft (cloud). (Use it when it is needed) We had 8k registered users for this contest, probably, the problem is because of underperformance of current servers.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the part of the code which records scores broken too? If not, why make this round unrated? Not being able to see standings is not a major problem.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, that's true, our scores are shown in the room standings

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think there is problems with the room too, which influence the hacking as well.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

I knew that round is unrated for me so I didn't worry a lot :)

Problemset was interesting, I spent two great hours !

Maybe better score distribution would be :

500 - 1250 - 1250 - 1750 - 2000 - 3000

P.S. I have no idea how did 350 coders solve fifth, for me it was pretty hard, not as usual fifth, but also it is not so easy :)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    C > D in my opinion

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I just used simple dfs to solve problem E

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Yeah I have used dfs too ( I failed final system testing, I do not reason, I will see). But also you need some constructive algo to put points on good distance, I do not say it is hard, but I spend 1 hour to solve it :)

      EDIT: I forgot one pair of brackets :(

      → Reply
»
8 years ago, # |
  Vote: I like it -11 Vote: I do not like it

WTF ?! why unrated ? I spent 2 Hrs of my time for Nothing ! :D

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    How so? What is more important ­— your rating or the competing experience you gained? Rating will go up and down, but the experience stays. And even if you value rating more, the 2 hours was well spent even for the experience.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You know ! I need more rate ! Experience is an important but I need some rate :) I was able to do many thing at that time ! Right ?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Do you really want anything else in 2 hours instead of solving these great problems :/

        → Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Told you, am here to conquer codeforces and Russia...

→ Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I just want to leave this comment by yeputons, 4 years ago:

WHY THE HELL?

Good problems, great social platform, but still going down during rounds. What's the problem? Slow code? You're programmers, optimize it! You cannot, because you need 'readable' code? Damn it, the website doesn't work during rounds, who cares about program's code if it doesn't work?

Too much users? Set limit of participants, like TopCoder do. At least rounds will be reasonably rated.

Not enough servers? VK offered you, not even once. If your code is good, it should be easy to scale on 10 servers.

Please, stop being prideful and make Codeforces a stable system!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Easy to say, tough to do! Well, I do agree with your points, but i think MikeMirzayanov and his team is putting a lot of efforts in making this platform better! And BTW it's still BETA! :)

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I think codeforces should be made opensource.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I agree, here's a lot of great programmers who are able to make a good contribution to the platform.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    I must notice that that particular comment was written in a rage and is pretty emotional and non-respectful, which I'm sorry for.

    I'd like to advise future commenters to refrain from using that as a reference.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think you want to advise to refrain from using that as reference.

      → Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

lets play never have i ever !

never have i ever became this happy to see my solution failed !

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You can use Dynamic Programming with N*M*64 Time complexity

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DP -> http://ideone.com/PaBMNW

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    For each string calculate the minimum distance to each kind of character. Store each distance in an array. For example, if the ith string is "a8*", then the arrays will be like:

    dist_letter[i] = 0;

    dist_number[i] = 1;

    dist_special_char[i] = 1;

    After that, we can iterate through all the combinations between the indexes of the arrays and get the min possible answer. (0, 1, 2), (0, 1, 3), (0, 2, 1), etc

    You can calculate that with recursion or simply 3 for's.

    Here's my code: http://codeforces.me/contest/761/submission/24320657 (failed it in contest because I was trying to acess an invalid position of the array lol gg)

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

Typed '$' instead of '&' and still passed pretests for problem C :(

Edit: Just submitted by correcting it and I am happy to see that it was not the only bug :)

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Solved 4 questions for first time. Contest become unrated. :(

→ Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Div1 guys now feel satisfaction :)

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hints for problem E?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Hint: The all edges' length can be formed of 2^n like 1, 2, 4, 8,..., 2^32,...

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Depth-first search the tree with arbitrary root, let the length of edge at depth d be 230 - d.

    → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve F?

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -14 Vote: I do not like it

I think round was unrated because:
Standings are unaviable even for codeforces admins -> They can't calculate new rating(it is based on your position in the ranklist) -> Round is unrated

→ Reply
»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Can anybody explain why my code is giving WA on test56 in c++11 while giving "accepted" in c++14 ? http://codeforces.me/contest/761/submission/24300137

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it +10 Vote: I do not like it

    You probably just got lucky with C++14. In if(v1[x]==v2[j])k++;, sometimes j becomes >= v2.size() in your code. (for i=1 in test 56) resulting in undefined behavior.

    PS: This code gives "NO" on both C++14 and C++11 on my local compiler after adding j%=n. PPS: Accepted

    → Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

After every contest, I hate myself for not being able to solve the problems.

After reading the editorials, I hate myself even more for not being able to solve such easy problems -_-

fml

→ Reply
»
8 years ago, # |
  Vote: I like it -29 Vote: I do not like it

There was one more issue.People in my room were able to hack even after their solution was hacked.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    That is intended behavior.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, I meant that this user hacked other users and then his solution got hacked even after that how he could he was able to hack more people.Is it intended?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        As far as I know, you can hack, if you could lock your submission even if you were hacked.

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        Yes, this is the intended behaviour

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        That screenshot is of my hacking. Notice, that I managed to get payback mere 13 seconds after getting hacked myself :) That was a coincidence though.

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My biggest issue is, if almost all of the comments are saying to make it rated, why wouldn't they make it rated?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    This would be unfair, because they announced that the round is unrated halfway trough the contest.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      When 25 minutes were left. I think it's still ok

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's make this round rated again! :D

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Solved three problems for the first time. Contest becomes unrated. FML

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This time lots of Hacks :p !!!

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +75 Vote: I do not like it

SOLUTION TO PROBLEM F
I just've got it ACed. In short words:

  1. Compute cnt[i][j][c] = count of photos that have character c at position (i, j)
  2. Using cnt, compute cost[i][j][c] = what this cell (i, j) contributes to the total distance if we try any photo that have char c there
  3. Compute sum[i][j][c], the prefix sums for previous cost array
  4. With this sum array you can try every photo and finally get our answer.

O(n2k) time and memory (hence the unusual ML), where k = 26, the alphabet.

Separated, each of these problems is easy enough to solve. That is about 100 lines of different array tricks, just code it carefully.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

please tell me hoe to solve A

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Consider the thing that a and b can both be 0 at the same time.And there is not any 1<=l<=r which satisfies the condition. My solution got hacked because of this. :(

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah me too. I was so frustruated when i got hacked. Took me ages to find out.

      → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I guess D can also be solved using binary search here is my solution.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes, i also solved using binary search but little different from yours http://codeforces.me/contest/761/submission/24327048

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It can be solved by greedy too :24329320

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain the idea of your codes? Thanks!

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        first you should notice that compressed C shows the position of the Ci after sorting array C.

        so the one Ci who is bigger than all other Ci s number 1 in compressed C.

        let Pi be the position of number i in compressed C;

        so C[p[1]] should be the biggest .thus b[p[1]] should be small as possible .

        so b[p[1]]=L(cause it's smallest );

        also you now that c[p[i]]>c[p[i+1]]

        so c[p[i+1]]<=c[p[i]]-1

        now we know that b[p[i+1]]>=a[p[i+1]]-c[p[i+1]].

        we greedily take the smallest possible for b[p[i+1]]

        (if a[p[i+1]]-c[p[i+1]]<l b[p[i+1]]=l)

        (or if a[p[i+1]]-c[p[i+1]]>r there is no possible number for b[p[i+1]];

        so we do it with all i and get the array b (sorry for bad English);

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          I got it ! Thank you very much ! :)

          → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Greedy for D.

    → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I have applied brute force approach in problem C. I am shocked to see that it passed within the time limit. Can anyone tell me why is it not getting TLE? Link to my solution. http://codeforces.me/contest/761/submission/24319247

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

"Top 10 participants from first division" 5 participants listed

→ Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The new year I will become more powerful.

→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Why isn't there any editorial of this contest?

→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Editorial?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone figure out what is wrong in my code for problem C. Is is giving wrong answer on test case #5 http://codeforces.me/contest/761/submission/24333316

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have 2 bugs:

    1) '0' — also number. else if(c[i][j] >= '1' && c[i][j] <= '9') -> else if(c[i][j] >= '0' && c[i][j] <= '9')

    2) Some characters may not be in line. For these lines you must make big value in temp. int p1 = n+1,p2 = n+1,p3 = n+1; -> int p1 = 10000,p2 = 10000,p3 = 10000;

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Okay i got it right but I have one more doubt when I change p1, p2 & p3 to INT_MAX it gives me wrong answer. Why is it so?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You add temp[j][0] + temp[i][1] + temp[k][2]. If temp equal to INT_MAX, then you have overflow

        → Reply
»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

When we will get Editorial...

→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Problems in the round very good.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how to solve F?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    In order to quickly compute the difference between a picture and a group of pictures at a certain pixel, we can precompute the sum of pixels in different cases (LT or GT the pixel), thus getting rid of the absolute value function. If we "stack" all the k pictures together (which each of the pixels carry k color values), then this action could be used between any pictures and the whole set of picture. (Note that we don't care if the picture being compared is also in the set, why?)

    But comparing pixel by pixel is rather slow, to improve this, note that if an area is a uniform color, you could treat that area as an pixel to compare over the area on the set of pictures. For the remaining area which has arbitary values, as they are the same for all pictures if not affected by the paint action, so we could precompute the value of the difference between the original picture and all other pictures. Then, to compute the difference between a editted picture and all other picture, just replace the precomputed difference of the editted area with the value computed by the comparison method mentioned above.

    2D Prefix sum is sufficient for storing and retrieving the values. Here's my rather ugly code: 24339537

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    linkhttp://codeforces.me/blog/entry/50107?#comment-340677_

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please could someone help me to better understand the hacking procedure?

I thought that only solutions of people who locked their problem could be hacked. I did not locked my problems but my solution was hacked. Is this behaviour intended or is it a bug?

Thanks.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    Only people * who locked their problem * may hack, but they may hack any solution.

    And id somebody is hacked before they locked the problem, they may submit again.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you! Would there be additional penalties if I submitted a right solution after the hack?

      This question is about the "penalty for being hacked" doubt in the example below:

      • I submitted (pretest passed), I submitted again (pretests passed, system tests passed).
      • I submitted (pretest passed), someone hacked my solution, I submitted again (pretests passed, system tests passed).

      First case:

      • penalty for +1 submission

      Second case:

      • penalty for +1 submission
      • (?) penalty for being hacked -- not sure about this
      • minor implicit loss (because the hacker gained additional points for successful attempt)
      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No difference from resubmitting yourself

        btw, you didn't mention penalty for time of submission. It's here in both cases

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The this the round the was the good. (should have written it right after the end)

→ Reply