gepardo's blog

Announcement of Codeforces Round #379 (Div. 2)
By gepardo, history, 8 years ago, translation, In English

Hello, Codeforces!

Tomorrow, in November 15, 2016 at 19:35 MSK a regular Codeforces round for participants in the second division will be held. As usual, participants from the first division can take part out of competition.

I (gepardo) am the author of the contest. It's my first round and I hope it won't be the last. Great thanks to Gleb Evstropov (GlebsHP) for help in preparing the contest, Andrey Kalendarov (Andreikkaa) for testing the round and Mike Mirzayanov (MikeMirzayanov) for the great platforms Codeforces and Polygon.

As usual, the participants will be given 6 problems and two hours to solve them. I recommend to read ALL the problems. I wish everyone many Accepted and, of course, enjoy solving the problems.

The problems will be about my younger brother Anton. I hope you'll like them :)

The round is rated.

UPD: Though, the round won't be completely usual and there will be 6 problems.

UPD2: The scoring is 500-750-1250-1500-2000-2750.

UPD3: Tutorial is available now.

UPD4: Contest is over, congrats to winners :)

Div. 2

  1. Octotentacle

  2. CisnijAsdPawel

  3. VemMonstro13

  4. fulvioabrahao

  5. Mehrdad_S

Div. 1

  1. sugim48

  2. uwi

  3. khadaev

  4. HellKitsune

  5. Um_nik

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

Comments Comments (178)
| Write comment?
»
8 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Finally a regular round!

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

    Let's hope for a great round with diverse problems!

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

Finally a usual 2 hour contest. All the best for your first contest as a problem setter gepardo

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

Usual time? How unusual!

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

Here we go again :D

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

It is becoming so usual to see comments about usuality

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

It is such a long time that has no contest!

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

is it rated?

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

"I wish everyone many accepted" — yes! we love this green word.

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

I wonder why so little div 1 contest lately. So sad :(

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

Hope next contests will be a bit earlier.

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

I have recently joined.Shall I be able to participate in #379(Div.2) ?

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

    Of course yes, just register to the contest. Wish you good luck :)

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

I wanna thank your younger brother who faces problems and made us get into competition , All the greetings and appreciation to him

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

    Thank you, it is me.

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

      I hope you are not competing in this round, that would be a huge advantage against all other participants, as you already know all your problems

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

        No, of course, I'm fair. I know all the problems and I will not compete in this round.

        Good luck everyone! I hope you will enjoy this round!

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

It's happening after a long time, also after a long time next one will happen! we'll miss it for long time!

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

I'm attending a CF round after a long time hope there are a lot of interesting problems :)

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

    I also hope that my problems will be interesting for you :)

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

"the round won't be completely usual", will there be a clown dancing in the middle of the contest or something :D

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

6 problems in 2 hours, will they be enough??? or shouldn't it be at least 2:15 :\

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

come on !!!! 12 more days until the upcoming div1 round

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

It seems that not having 5 problems is the new default

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

I guess problem C hacks use this: ci are not decreasing and di are not decreasing?

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

    I hacked someone because he didn't handle only using second spell.

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

E test 3 — what was this?

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

    Consider a white node connected to three black nodes and each of these black nodes is connected to another white node. The answer is 2.

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

    in first sample , add a white child to 11 , that should fail most wrong logics.

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

    Maybe something like this?

    16
1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16

    Answer is 4.

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

    It was just a random test.

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

Is this rated?

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

How to solve C?

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

    using binary search!!

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

    Use binary search.Since potions of type 2 are already sorted and also greater the cost of potion 2 greater is the number of potions that are immediately completed. for each potion of type 1 find the maximum type 2 potion that can be bought using upper_bound(In C++ ofcourse) and find the amount of time it takes and find minimum among those.

    Time Complexity — mlogk

    m-number of potions of type 1 k-number of potions of type 2

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

      I used similar approach but failed on pretest 3... 22247888 any idea why its failing ?

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

        pretest 3 was about not considering using only first spell I think.

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

          in the commented portion i was tackling that as well but still It was failing on pretest 3. btw can we see pre tests once the contest is over ?

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

            yep, just scroll down to see tests.

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

        What if we just need to cast spell type 2?

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

    1.First solve for only using second type spell — O(k) 2.Iterate over m and during each iteration use binary search on k and find minimum value during each iteration. 3.Then take minimum of all value which find in step 2.

    Time complexity — O(mlogk)

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

      I add one artificial spell to both types. (x, 0) for the first type, and (0, 0) for the second one. Picking one of this spells is equivalent to taking none of respective types as they have no effect. Thus I was always picking exactly one first type and exactly one second type spell, sparing myself consideration of corner cases. It got accepted so I suppose it's valid.

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

    Two pointers. Sort first spells by mana and go from left to right, at each step decrease the pointer for the second spell while you don't have enough mana.

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

    I solved it with two pointer technique

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

    sort first type spell's by cost of each. then you can use Two Pointer algorithm for each a[i] (the i-th first type spell)

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

когда это редакционная?

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

Should have defined axis in D . The picture for sample 1 got me all confused :/

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

What is the simpsons prediction about this contest ?

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

Any approach for problem E? i used dp on trees but it failed on pretest 3. My solution

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

    compress adjacent node with same color , answer is radius of this tree.

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

      ohh nice one! but can you look into my dp solution? (its short and easy to understand). I cant figure out why its wrong.

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

        in the first sample add a white child to node 11 , answer is 2 , your code gives 3

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

      Why is the answer radius of the tree?

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

        pick the centre of the compressed tree , and keep painting it till the color reaches the leaves , it takes radius number of steps.

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

          How did you not think it was dp on a tree question?

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

        After painting one node (and compressing the tree again), the number of layers of the tree decreases at most by one, so we have to find a tree with the minimum number of layers (minimum depth). That means that the root must be the center of the tree

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

    The colors make a ring like structure visually. ans=no. of rings-1

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

Nice contest! Easy problems — so I can feel me smart xD

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

What was the hacking testcase for F? Probably something for which answer looks nice, but b[i] and c[i] are computed incorrectly.

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

I tried hacking this code on test case: 5000000 5000000 5000000 5000000

but got unsuccessful hacking attempt :( . I was expecting int overflow as the ans for this test case is

1280000000

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

Whats the fastest way to check for the optimal solution in C?

I checked for Spell 1 only and Spell 2 only by normal for-loop and used two-pointer method for Spell 1 + Spell 2 checking.

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

    Use binary search.Since potions of type 2 are already sorted and also greater the cost of potion 2 greater is the number of potions that are immediately completed. for each potion of type 1 find the maximum type 2 potion that can be bought using upper_bound(In C++ ofcourse) and find the amount of time it takes and find minimum among those. Time Complexity — mlogk m-number of potions of type 1 k-number of potions of type 2

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

      Oh damn, I'm an idiot. I thought that the upper_bound function was O(N).

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

At the last minute, I submitted D and got WA, and I found there was an obvious bug and fixed it immediately, there was 15 seconds left and I resubmitted as soon as I could, but I couldn't click the submit button T T

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

Can someone give me testcase for C for which my solution[submission:22243090] fail

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

I wrote a correct solution(I think it's a correct solution) for the problem E but when I was submitting it I choose the GNU C++ compiler instead of GNU C++11. Is it possible for the site administration to rejudge my submission with the right compiler?

link to my submission: http://mirror.codeforces.com/contest/734/submission/22248724

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

Suggestion:

Either 6 problems in 2.5 hours or 5 problems in 2 Hours.
Thank you!

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

For the beginning of the contest, I could not submit codes to problem A and C. The site kept me waiting without echoing anything, which really really annoys me (I have lost 100-200 points and spent some ten or twenty minutes trying to fix it). After each time I submitted a solution, I had to wait 1 or 2 minutes to see the result, and in most cases, it told me the connection was lost(maybe timeout?) and I must resubmit. Finally, I used a VPN proxy and it somehow worked. I think at the submit page there should be some js code to handle timeout, because (at least for me) a successful submission usually won't take a long time.

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

In problem E: Does the paint function simply work like the paint bucket in mspaint.exe (floodfill all adjacent nodes of the same color)? If yes, then the description is needlessly complicated. Interpreting it like this I used a disjoint set union, and tried to count the number of white and black sets and printed the minimum of them. Seems like I'm wrong...22248877

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

I'm really scared from C's tests everyone is failing in it.

:(

UPD: got it AC

:)

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

My B failed! :(
Can anyone tell me what is wrong in this? 

ll k2,k3,k5,k6; cin>>k2>>k3>>k5>>k6;
ll mini=(k2,min(k5,k6));
ll sum=0; sum+=256LL*mini;
k2-=mini; k5-=mini; k6-=mini;
mini=min(k3,k2);
sum+=32LL*mini;
cout<<sum<<endl;

Edit:Jesus christ, I wrote (k2,min(k5,k6)) instead of min(k2,min(k5,k6)) ...... How does (k2,min(k5,k6)) get evaluated anyway?

TrueSadness.jpg :(

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

Solutions for C of many people failed any idea where it failed.

Upd: Mine too failed any idea on the mistake in my code

http://mirror.codeforces.com/contest/734/submission/22243843

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

    My solution failed i believe because i set maximum value for answer to be 10**16 (I thought n = 10**5)

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

    I got WA on test 13 because I forgot to take minimum of possible potion values and the original value of x, :/ Feels bad man. :/

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

    i think you forgot if pos <= 0 or something like that

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

      Thanks i got the mistake if upper bound return 0 pos becomes -1 .

      Facepalm :)

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

What's up with A? I understand it's Div. 2 A and you can give there pretty much anything solvable by anybody in less than 5 minutes (I have been an author myself), but I think it's too much: I feel like I have seen this problem ten times before, it's pretty much one loop and one if (no brain involved), and looks more like a programming language exercise.

Still thanks for a contest! :) I enjoyed E (and have no clue for F).

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

    As you've seen C was a little bit hard, so I needed something very easy for A.

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

    I believe they meant to test the platform for a lot of quick submissions ;)

    I must say, well done, everything worked very smooth this round, good job!

    (I submitted A in second minute of the contest thinking how quick I am... and there were already 500 accepted submissions)

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

Auto comment: topic has been updated by gepardo (previous revision, new revision, compare).

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

Auto comment: topic has been updated by gepardo (previous revision, new revision, compare).

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

It was good

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

May be pretests will be more stronger!7! At least in realisations such as D

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

Where? ! :O

And also how Tutorial was available before the contest is over ! :P

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

In Problem D, It was stated that it's a x-y plane. However, it didn't seem like a Cartesian Coordinates System at all. :\

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

    It is a cartesian plane.

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

      X represented the row instead of the column, -ve rows(i.e -ve X) were on the top !

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

        That doesn't change the result. A rotated plane is still a plane.

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

I am a new participant. After the contest my rating was not updated and my contest list doesn't show my participation in this round. Is there any problem with my profile or anything else?

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

Has anyone solved problem E,using dp on compressed tree ?

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

I had submitted a solution to the C problem during the contest and it was giving wrong answer on 5th pretest and I submitted the exact same solution after the contest and it is giving TLE on 6th pretest. I don't know why this is happening.

Submission during contest: http://mirror.codeforces.com/contest/734/submission/22240240

Submission after contest: http://mirror.codeforces.com/contest/734/submission/22250847

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

    Only 

        #define xxx xx

    is added !!!

    Authority should take a look at this ! The both solution is same ! But for some reason during contest time there occurred a overflow ! for that output was -7166261092318506304 !! -_-

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

For problem C, can anybody please explain me why for input

10 3 3
10 33
1 7 6
17 25 68
2 9 10
78 89 125

output is 17 ?

Shouldn't the output be 10? Since Anton can use the 1st spell of the first type that costs 17 manapoints. Thus, the preparation time of each potion changes to 1 seconds. So the preparation time is 10*1 = 10.

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

Auto comment: topic has been updated by gepardo (previous revision, new revision, compare).

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

In problem C, I have used range minimum query segment tree + binary search to find the minimum possible time. I am getting WA on test 13. Testcase is pretty much large, cant figure it out manually, Somebody help please :) http://mirror.codeforces.com/contest/734/submission/22241998

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

    I had WA on the same test, make sure you're considering the case when you don't use any spells of the first type.

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

when will the ratings be updated!!!!!

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

I got a RUNTIME_ERROR on my submission 22244664 for problem D. If I run my solution locally, it runs fine. Does anyone have a clue?

--EDIT: Also on submission 22251648, which is the same code but cleaned up.

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

How long do they update the rating ?

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

We need more regular Rounds like this and in general more rounds..

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

A funny thing about the contest:

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

Waiting for the rating change..

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

i have an Exam tomorrow send me a message when you update the rate ,i am sleeping XD

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

this was a great "prime in number" round :D

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

Deleted

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

First time 'BLUE'! It's great to see my name in blue color! :D

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

gepardo Problem C: Can you check why test case 21 has only 3 lines, its hard to take input as in questions it specifies input in different lines.

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

    Codeforces doesn't show the tests fully, so you can see only 3 lines. But in fact there're 6 lines in the test.

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

This was my first competition and I really enjoyed solving the problems. Good job Alex! :)

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

That is a pity!I have read problem.E for more than one hour,but fail to understand the description until now,please illustrate your meaning clearly in the future.

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

Stuck on finding bug in submission 22242517 for 734C - Anton and Making Potions. Got error on 13 test case. Any suggestions, please?

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

    Consider the case where you meed to take only potion of the second type.

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

      May I ask you to provide some more details, please?

      I am iterating over all items of second type and searching for appropriate items of the first type using binary search in the for loop.

      For me it still looks like in 13 test case there is an item of second type with c == n and d <= s.

      for (long long i = 0; i < k; ++i) {
        if (snd[i].first > s) { break; }
        long long max_b = s - snd[i].first;
        long long r = n - snd[i].second;
        if (r <= 0) { min_time = 0; break; }
        long long a = min_fst(max_b, fst);
        if (a < 0) { a = x; } 
        min_time = std::min(min_time, r * a);
}
      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just figured out that min_fst function was incorrect. Should check if iterator points to the end after lower_bound if (it == fst.end()) { --it; }

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

I'm not sure whether I am right. I'm getting WA on test 1 in E. I checked the answer on my computer and it's 2. However, the result of the onlinejudge is 5, which makes me confused. I made the judge print the edges of the data1, it's 3 8 3 8 3 8 3 8 3 8 ???, and that made the wrong result. Also, I get RE on data1 if I chose C++11. I assume that the data of test1 is wrong? if not, why is the problem coursed? Thx

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

    Hi, I had a similar problem before. I see that you are using both scanf and ios::sync_with_stdio(0). Use either scanf or cin when u use ios::sync_with_stdio(0), but not both. That's the reason for the problem you are experiencing :) EDIT: Also, your code has wrong logic so correct that too :).

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

      Thank you! I solved this problem= = With regard to the wrong logic, I will think it over later = =

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

In problem E
Who can help me explain this example, why the answer is 3?
10
0 1 0 1 0 1 0 0 1 0
1 2
2 3
3 4
4 5
5 6
6 7
4 8
8 9
9 10

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

Solved all problems with Haskell. I really like your problems! :D :D :D

→ Reply