oversolver's blog

Codeforces Round #276
By oversolver, 10 years ago, translation, In English

Hello everybody!

Today will be Codeforces Round #276, which take place in both divisions. Start time is 19:30 in moscow time (follow this link to see time in others zones). For preparing contest i say thanks to Zlobober, for translating to Delinur, and to MikeMirzayanov for project Codeforces.

Good luck to all, hope you will enjoy problems :)

UPD Score distribution will be dynamic (see more information here). Problems will be sorted in increasing order of difficulty, however, do not forget to read all problems before the end of the contest.

UPD The contest is over! Thanks to everyone who solved the problems despite everything. Analysis will be published later.

UPD Editorial can be found here.

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

Comments Comments (158)
| Write comment?
»
10 years ago, # |
  Vote: I like it -86 Vote: I do not like it

Please short explanation for problems. --> Because read story of problems is too tedious.

Also explanation of sample tests. For better understand problems.

" THANKS FOR READING

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

Please give me '-' till my contribution reaches 0 and then stop.

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

Now I know the reason behind late , Bug oversolver

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

1 hour later is not good for me

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

I am new to code forces.What is div 1 and div 2 in round #276?I could not register in div 1 so have registered in div 2 .May i know how div 1 and div 2 users are distinguished

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

your last contest(#256) has nice problem.thanks~

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

What's a good tool to visualise the call graph of my code as it solves a sample test case? And that won't take much time overhead to use during a contest? (For Python or C++.)

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

    so for simple:

    foo() {
    bar();
}
main() {
    for ( int i = 0; i < 10; ++i ) foo();
}

    you want to see what?

    main
	foo
		bar
	foo
		bar
	foo
		bar
	foo
		bar
	foo
		bar
	foo
		bar
	foo
		bar
	foo
		bar
	foo
		bar
	foo
		bar

    ?

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

    In Visual Studio you can see good visualisation (screenshot is in previous edit) Is it what you want?

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

      I cannot see the screenshot (in Rev. 1)...

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

      Something like that. But also a bit different: it should be a graphic so I can take one look at it and know what went wrong. I think I'll have to write my own. It would be easy to parse the output such as what appears in your screenshot or of a profiler for either Python or C++.

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

Hope short and simple problem description just like the announcement :)

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

Very bad time for Asian participants

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

    What time it is for you? Because in Europe (let say Central Europe) time was not changed, probably because of summer time...

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

    You are right...It's 0:20 AM in China...

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

    Not in Iran ( 8:00 PM ) :D

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

not able to wait..

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

1 hour later is very bad for China. It is 0:30 for us, what a sad story!

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

    I have to move to China, quite good time for me...

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

    And it is 1:30 for Japanese...

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

    It was 3:30am here when the contest started. These coding events remind me how much I like to work in the peace of the night.

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

I hata the start time, it's too late in our country

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

I'm Unlucky in dynamic score :(

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

Please unlike me :) Plz

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

I am always curious to know why do the authors declare the score distributions at the last moments. Has it anything to do with the number of registrants??

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

    I am always curious to know why do the participants care about score distribution before the last moments

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

Hope to see a nice problem-set and +ve rating growth.. Dynamic-Scoring has always haunted me :P

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

Server is too busy and can't open any of the problems, is it only me?

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

    Nope.

    The server is very busy, it's impossible to submit or even access to the statements !

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

    Server is stuck (

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

      As always when contest is running and lot of participants...

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

    me too

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

I don't know what happened, but there are more than 1000 submissions waiting for judging.

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

Nice problems but server is always busy!!! I submitted the code for A-Bits 10 minutes ago and it's still in queue

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

I can't send any problem. Is the round going to be rated?

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

Is it rated today?

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

    In my opinion, it shouldn't be...

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

In queue

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

It's 11 p.m. I tired to wait. And I'm going to sleep.

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

Nice set of problems, but the system is making it almost impossible to compete.

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

    Agreed, the last 3 problems look equally challenging.

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

    Yes. 30 minutes to send the solution, waiting the submit page opens..

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

Good short statements ;)

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

seems round will be unrated ;( ... anyway, keep solving!

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

unrated :)

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

"This round will be unrated due to technical issues."

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

if contest rated , I will up rating, but it is unrated. I am very sad !

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

How about providing the problems in pdf, as in the gym, along with the online version, so that if server is getting overloaded then people can do with them (download that file initially as a back up)

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

    Open all the problems as soon as the contest starts.. Works for me everytime..

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

After the contest started I thought, "Awesome problems, awesome statements. I really hope I everything goes well today! :)" An hour later... "Long queue, contest is unrated for technical issues". Now I'm thinking, "Why did I have to jinx it?! :(("

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

this round is like BAYAN contest ... great problemset but ...

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

And a buggy round by oversolver :(

Waited long for a DIV2 round and got this :/

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

    I don't think that it's oversolver's fault

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

      No, but the irony in his handle :D

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

      I know it's more like a server fault. But I noticed that Div2A points were changed twice. First it was rated 1000, then 500 and now 1000 again. So, I do suspect that some way or the other, oversolver is at fault, if not majorly.

      Update: It's 500 point problem again.

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

        The points are changing only because the score distribution is dynamic. If C is solved by many people by the end of the round, it will probably bring only 500 points.

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

          I know its dynamic. The guy in the top of my room had 900+ point in problem A. Now he has 480 points. The score of an individual changes after correct submission too? I'm sorry, I didnt knew about it.

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

            I don't think you know the correct meaning of dynamic scoring. The scores change based on the number of correct submissions on a problem. The lower correct solutions, the harder the problem is thus higher the score and vice versa.

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

        this is normal to happen in dynamic score, first the score is 1000 then more people solved the problem makes it 500 then more people make wrong submission as a first submission(or solved another problem) which increase number of participants making the points of the problem back to 1000

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

          Oh thanks. I didnt knew about it. I take my criticism back :P

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

            In Soviet Codeforces, you can't take it back.

            Aren't you aware of the Russian proverb: "a word ain't a sparrow: once released — it can't be recaptured"!

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

    Such a pain, when there's finally div1 contest where you can participate... and clar says it's unrated :'(

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

If only I can punch person to death I will punch myself. Such a waste of precious sleeptime.

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

contest is unrated . . . keep calm and . . start self mutilation. . . :-"

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

Solves div2 C in 5 minutes -> unrated round.

Tough luck =(

Is anyone having trouble locking problems? i want to try to hack some solutions, but i can't seem to find the button to lock a problem.

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

Well, I decided to improve my ranking. Not destiny :)

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

5th November of 2k14... the day that Codeforces died...

http://i.imgur.com/LN2DJZV.png

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

    "Remember, remember, the fifth of November" Codeforces Edition

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

      Keep calm friends. I know codeforces is not doing well today, but instead of backfiring at it why dont you try to solve the problems, or even go to sleep, than blaming contest writers, platform etc. Remember, the joys the platform has given you, the job you got by practicing at this platform, the money, fame so many things. And one day it is bad and you show this attitude towards it. I am sorry If I sound harsh, but it preety much shows people's character.

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

        It was just a joke m80 (matey)

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

          It was not directed particularly to you mate, but to all such comments above.

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

    Somehow it reminds me about Black Day of Codeforces

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

Ow God knows when the next contest will be ... :(

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

ridam to contest :) tnx

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

Remember, remember the fifth of November, the Gunpowder treason and plot; I know of no reason why the Gunpowder treason should ever be forgot!

I guess Codeforces system blew up in the spirit of Guy Fawkes Day!

But in serious matter, there were 5000+ competitors and this is the 276th round. One would expect the system to be more stable by now. I personally feel sad for oversolver because that was one good problemset and I think he deserves some credit and I'm quite sure that it wasn't his fault at all. And about changing problem scores mentioned above, scores are dynamic, of course they will change!

Well, anyway I liked the problems so thanks for the good problemset :)

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

it is my worst contests always "Busy Server" or "in queue"

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

I`m so sorry but I have to give up this contest for many reasons:-( Expecting next competition ! :)

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

Is hacking disabled due to the contest being unrated? I cannot lock my problems

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

There are still 40 minutes remaining, but I'm very sleepy. I will sleep now.

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

Sorry, guys. It seems that it was my fault. I don't know all the reasons why everything happened bad. The main reasons are:

  • ext4 partition on one server switched to read-only mode because of unknown reasons (I will try to diagnose this),
  • judging code used old version of our http-wrapper library with resource-leak.

Sorry again about it. I apologize to the writer oversolver he did his job great. Be sure, some sleepless nights are waiting for me!

P.S. Fefer_Ivan, it is hard without you...

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

    I also want to say thank you for those who didn't stop participating just because of contest being unrated and who continued solving nice tasks that oversolver prepared.

    I hope that we will see new contests set up by him again!

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

    no problem at all

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

    Nothing to sorrow. At least I learned something by trying the problems. Just it will be nice if we have the upcoming contest soon. Thanks! :)

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it
    ext4 partition on one server switched to read-only mode because of unknown reasons

    The kernel remounts a filesystem read-only if it encounters an I/O error on the underlying device. If this is what happened, then the kernel log should contain the details.

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

how to solve div-1 d .

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

    You want to partition the sequence in subsequences each of which will be "going up" or "going down". Solution is a DP where you state is (position, down or up).

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

    My solution (possible solution, I don't know if it's the correct one) was the following: - You can build a DP like dp[i] = min j < i(dp[j] + maxValue(j + 1, i) — minValue(j + 1, i) - The solution above is too slow O(N²), but you can notice that maxValue(j + 1,i) — minValue(j + 1, i) is increasing as we decrease 'j' and that dp[j] is increasing as we decrease 'j'. The sum of one increasing function with one decreasing function is a function that increases and then decreases. - Given that fact we can actually do a ternary search on the maximum 'j', so now we reduced our solution to O(N log N)

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

      "The sum of one increasing function with one decreasing function is a function that increases and then decreases."

      Are you sure?

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

        Not so sure, that's why I don't know if my solution is actually right.

        My intuition was telling me to assume that dp + max — min is a function that can be ternary searched.

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

          It's actually false: Sum 1 3 7 9 and 9 8 3 2

          yields 10 11 10 11 which increases, then decreases and finally increases again.

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

            Yeah, you're right. I guess the lesson is not to trust your gut at all times, they may be wrong!

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

      The sum of one increasing function with one decreasing function is a function that increases and then decreases

      Nope , you're wrong take this example:

      A= 10 20 30 40
B= 50 45 25 20
Sum= 60 65 55 60
      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    DP. Sequence rises up and down.And the key-point is you will never separate a continuous sub-sequence into more than one sub-sequences if this sub-sequence is straight up or down.For example:

    -2 4 5 1 -7 3 6

    you should divide them into :

    -2 4

    5 1

    -7 3 6

    or

    -2 4 5

    1 -7

    3 6

    or something like that.

    You can figure out that the only thing you need to handle is which part should the peak and the bottom of the sequence belong. Turns out a DP problem.You can check my code.Hope that helps.:D

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

    Also it has simple O(N) solution:

    x = -a[0];
y = a[0];
ans = 0;
for (int i = 0; i < n; ++i){
	ans = max(x + a[i], y - a[i]);
	x = max(x, ans - a[i + 1]);
	y = max(y, ans + a[i + 1]);
}
cout << ans << endl;
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Could you please explain why this works? I looked at it for a long time, but I can't figure out what x and y represent. Thanks in advance.

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

        In optimal answer any segment that making a group contains their minimum and maximum values on borders. So, we can write following dynamic solution, which find answer on each prefix of array:

        or

        Therefore it is sufficient to remember and update the maximum values of ansj + aj + 1 (y in my code) and ansj - aj + 1 (x in my code) at each step.

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

When will system testing begin?

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

i really loved the C Problem, i'm not sure why, but i just loved it :D

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

No rating is not bad for mee, round was difficult... waiting system test...

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

How I solve problem D?

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

Thanks for the Nice problemset oversolver , I just wanted to tell you that I enjoyed the round despite the technical difficulties that were being caused by codeforces .

PS:If you like what I have said above then give it a '-' .

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

Is there some tricky case for Div1 A/ Div2 C?

I solved it as follows: let the answer be stored in res. go through the bits of the 2 numbers(from left to right). If the current bit is 1 in both then set that bit in res. If it is 1 in r only then set it to 0 in res and make all next bits 1. In the end count the number of 1s in res and the number of 1s in r. output the one with the max.

What's wrong with that?

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

    So... I have finally seen the test that failed me and it seems to work fine locally but outputs a wrong answer in Custom Test... Can anyone tell me what could've gone wrong here? Submission

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

    i had the same problem but i fixed it, you must think what happens when you have a case like this:

    Left = 6 ; Right = 7

    6 is written in binary like 110 7 is written in binray like 111

    following with your approach you will go to the last bit and set it as 0 then all the remaining bits as 1, but in this case you will return 6 and the correct answer is 7. So, you must care the case when it is the last bit, if they only differ in the last bit you must return Right

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

      Actually not... As I said, at the end I count the number of 1s in r and the number of 1s in res and print the one with more 1s... In this case, I'd print 7 :D

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

contest had many bugs bugman! :)

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

All problems are very interesting. Thanks to oversolver.

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

(http://i.imgur.com/nvtu5ZI.png)

still waiting for my first hack attempt :D

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

When you are as bad a coder as me then technical difficulties are not such a big problem for you! :P My only submission was Div2 C at 2 hours 7 minutes past the start of the contest and it got tested without any delay.

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

    My only submission was Div1 A at 0 hours 6 minutes past the start of the contest and it got tested without any delay :D

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

Div1 D:

We can prove that each groups must be increasing or decreasing. So we can solve it in O(N) with using ordinary DP.

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

    Or the problem is just asking to traverse the array from left to right choose some numbers and add to solution and some other numbers and subtract it from solution such that at any time during the traverse number of numbers that you added to solution differs from number of numbers that you subtract from solution by at most 1 but at the end the two numbers should be equal , this can be solved by very simple dp my code 8576807

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

      Lol, how simple. Reminds me of 383D - Antimatter with a long explanation for the official solution and a short one for the one most people found.

      (It's not like DEGwer's version is much harder — you just need to think when it's better to split/merge a group and it follows almost immediately.)

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

    I like D , I tried to solve it ( but got TL ) with DP , ternary search and segment trees.

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

I have seen Div1 B in a Japanese high school programming contest.

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0270

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

Nice problem at all, thanks for the contest. Btw, someone can describe the solution of problem Div2C/Div1A? Please)

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

    greedy will work :). let b = number of bit in R (upper bound).

    now start from res = (1<<b)-1. (all the bit 1) now start removing power of 2 from right to left until you have res in the given range.

    If removing a power of 2 gives you a number less then lower bound L then do not remove it, try next one...

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

    go from li to ri increasing the number of ones in his binary representation :

    for example

    li = 0010001 -> 0010011 -> 0010111 -> ...... until it reach some number equal or greater than ri

    ri = 1010101

    when I say increase number of 1s , I mean add 1s in the 0-positions from right to left, every time you add an 1 digit the result number is the minimun number with 's' 1 digits ( s = current number of 1 digits in the result number ) greater than ri , you can prove it.

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

Good problems. Bad network.

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

How is Div2-D / Div1-B to be solved?

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

Thank you oversolver for this amazing round. I took the best place I ever had, and that gave me faith. My self esteem is in your debt.

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

Why do we need to run the loop 'm' times in Problem A of Div-2?..

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

    in case we have 65535 65536, Answer is "Yes". so , we must check until m or else we may get a wrong answer in this brute force method .

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

Thanks oversolver for great problems. I was sad when I read announcement but I was happy after system testing (because my solution A failed) :)

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

Thank you oversolver for such an awesome problemset! If the servers didn't have issues during the contest and ran smoothly I think it would've been an even better one. I hope we'll see more rounds from you in the future! :)

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

Quite a nice contest :) My first hack ever! Thank you oversolver.

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

nice contest and fast editorial

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

Why rating system is too slow? Or is it a unrated contest??

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

Just wondering, is this the first time for a contest being unrated? Anyway the div2 problems are as good as your last contest. Thanks, oversolver.

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

8573331

Output
qertwy
qtewry
qetyrw
Answer
qertwy
qtewry
qetyrw
Checker comment
wrong answer 1st lines differ - expected: 'qertwy', found: 'qertwy'

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

    hint: check the length of s

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

      If check visually, seems that checker printed both string of length 6, no more symbols, spaces or newlines.

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

      Already changed that yesterday, but either way I got TLE :P. Too much copying vectors :(

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

    I don't get it. Why is it WA?

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

      I didn't expect that it can be a reason of WA, but it's caused by zero byte.

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

My rating didn't change after the contest...

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

Country wise rankings have been updated for this contest. Although I know many people left the contest half way, including me, but still had to update the site.

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

next div 1 contest after two weeks...

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

when will the ratings be updated?

→ Reply