Barichek's blog

Codeforces Round #407
By Barichek, history, 8 years ago, translation, In English

Hello everyone!

Codeforces Round #407 for both divisions will happen on Mar/29/2017 19:05 MSK.

The problems were prepared by me (Ihor Barenblat), Stanislav giraffeh Tomash and Anton arsijo Tsypko. Great thanks to Ivan Fekete Fekete, Adalbert Adalbert Makarovych, Roman chakred_namor Derkach, Vladislav winger Isenbaev and Alex AlexFetisov Fetisov for testing the round, Nikolay KAN Kalinin for his help with the round preparation and Mike MikeMirzayanov Mirzayanov for the Codeforces and Polygon systems.

As usual, contestants will have 2 hours to solve 5 problems. Scoring will be announced closer before the round.

Hope that everyone will find interesting problems. Good luck!

Scoring distribution:

Div2: 500-1000-1500-2250-2500

Div1: 500-1250-1500-2000-2250

UPD. Editorial is published.

Congratulations to winners:

Div.1:

  1. -XraY-

  2. Um_nik

  3. jqdai0815

  4. YuukaKazami

  5. Syloviaely

Div.2:

  1. KacaMG00

  2. LAGBOYDaD3zZ

  3. __W__

  4. GoogleBot

  5. shas20

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

Comments Comments (221)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

Nowadays number of problem setters+tester of each contests are more than the number of problems :D That's cool. Thanks to all the problem setters for giving their important time in problem setting for us B-)

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

Hope to have interesting problems and good problem description.

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

wish high rating for all

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

    now you can see my pokerface

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

      I actually see it is a see-saw and your art gives me an impression that rating have to be balanced in a round, therefore "wish high rating for all" is an illusion.

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

:|

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

How many problems？

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

who is maria ivanova Barichek ?

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

I will be in top 1000 this contest!

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

Well I m new in programming contests ... Can you plz tell me that in in which Division should I register.....It will be great if you can give some tips to me .

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

    If you are new, you should register in Div.2

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

Rating prediction: div1 div2

Extensions:

Have fun & high rating:)

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

    Hey, Can you Github it? and share the link, please?

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

      It's already on github. Also you could read blog on cf about it.

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

        Hey, What's the matter with accuracy? Why not accurate when you know the results?

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

          The results of this predictor are very much accurate.

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

            Gotta try it from now, lets see how today's contest rolls up. all the best everyone.

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

Is a2oj down?

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

I believe I can fly.

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

Good luck in the competition! Here's a little song to hype y'all up!

Beautiful program
Please run for me.
I've tried you in BASIC,
FORTRAN and C.
Beautiful program,
You've errors galore.
And each time I run you,
You're swapped out of core.

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

    You are good in programming (as I see your color) but sorry to say, not in literature.

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

Problems in CSAcademy are getting better than DIV2 CF Rounds. Long Problems, uneven difficulty levels.

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

Is it at all possible that problem E is just named "New task" because it is a placeholder name :P?

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

Hack page not loading... Can someone please check?

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

Problem with the hack page :/

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

Today we are going to witness the fastest system tests ever .

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

Hi div2 :V

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

RIP RATINGS...

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

What is pretest 14 in div2 B ? Your text to link here... What is wrong in my solution?

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

    Try this:

    5 0 4 1

    1

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

      I think it isnot this case because my pro can cover this

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

      inf?

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

      ans is "inf" ?

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

        Ans is "0". Because Masha will stop writing immediately if |bi| > L.

        That's exactly why I got WA on the first submission.

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

      my sol is giving correct answer my solution

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

      Ans is infinity.

      Because 5 0 0 0 0 0 ... Now 0 is no=t in list...So ans is inf

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

      it think ans is 0 i thought it was inf before i changed it and passed that test and the statement was confusing.

      she will firstly write 5 that's bigger than l so she stop and write no number so answer is 0

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

    I want to know too

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

    i passed it by putting
    if(abs(b1) >l) cout << 0 <<endl;

    at the beginning

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

      thank you , it must be this case

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

      How come? if b1=0 and q=0 then the answer should be infinite!!

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

        the condition has nothing to do with q it just compares b1 and L and if b1 =0 the condition will be false because L is always bigger than 0

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

    if q==-1 && Math.abs(b1)>l then ans = 0; i think this is the case .

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

    I don't know actually, but this case troubled me a lot today :-/ somehow, passed it in 11th submission.

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

How to solve Div2B. Got stuck for 1 hr.

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

    check for exception cases — q = -1,0,1 and b1 = 0. for others apply naive method.

    I got hacked once because of not putting b1=0 case seperately.

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

      @mizuki instead of checking exception cases, we can count iterations here is my code (maybe it will fail in system test):

      intt ans = 0, it = 0;
    while (abs (b1) <= l) {
        intt t = 0;
        if (binary_search (arr + 1, arr + m + 1, b1))
            t = 1;
        b1 *= q;
        if (t == 0)
            ans++;
            it ++;
            if (it == 100000)
                break;
    }
    if (ans > 31) {
        cout << "inf" << endl;
        return 0;
    }
    cout << ans << endl;
      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did that ..can you check my submission?

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

      i used that but i had wrong answer on pretest 9 .. could some one tell me why ? i thought i did it correctly i did all the cases ?

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

        I tried for q=0,1,-1 and b1 = 0. As well as same way as of iterations count but got pretest 9 WA :(

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

    Just use binary search instead for checking if bi is 'bad'.

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

What could be Problem B test 14 ?

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

    I think it was abs(b1) > L.

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

      I considered that case too along with q==-1 but still got WA

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

How to solve C?

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

    The answer doesn't exceed 1000. But I don't know how to prove it.

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

      If there exists a[i] == n, answer is 1.

      Else if we don't have both a[i] < n and a[i] > n, answer is -1.

      Else we have some a[i] == n — x and a[j] == n + y. Then we can take y bottles of type i and x bottles of type j. x + y <= 1000.

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

This >.<

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

    me too :/

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

      Mine is wrong too :(

      Masha writes all progression terms one by one onto the board (including repetitive) while condition |bi| ≤ l is satisfied (|x| means absolute value of x).

      So if bi>L u don't have to check for 0 too when common ratio is 0.

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

    fail 4 times, which case did I missed?

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

Hacks, Hacks everywhere 8-) <3

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

Is Div1 D solvable by Java? I think the solution needs almost 300000 queries. An Educational Codeforces Round held some month ago has such problem (many queries needed) and no one can solve by Java since flush() is time-consuming.

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

    Codeforces and ACM want people to code in C++, thats why I changed from java to C++ :(

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

      If so, statement must not advice for Java or other languages' flush.

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

        Well I should be doing 1.8*10^5 if that matters. Isn't there another way to make flush?

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

    we can solve it in at most 100000 steps.

    fix... my estimation is wrong before...

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

Can somebody tell, if for div1B suggestion, that 2 used only once edges are neighbour edges, is right?

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

    Any two self loops can also be single edges.

    Also any normal edge(non self loop) with any self loop can also form a pair.

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

      is that only 2 cases? self-loops and neighbour edges?

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

        1- pair of self-loops

        2- self-loop and edge

        3- pair of edges that share an endpoint

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

          Can you please tell me a case where this would go wrong:
          sz[i] tells the number of nodes adjacent to node i (not including i even if there is a self loop)
          n is the number of edges which are not self loops..

                  for(int i = 0; i < nodes; i++)
	{
		for(int j = 0; j < adj[i].size(); j++)
		{
			ans += sz[adj[i][j]];
		}
	}
	ans /= 2;
	ans = ans - n;
	cout << ans;
          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            As I said, pairs of self-loop's should be counted

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

              Sorry I don't understand this very statement pairs of self-loop's...
              for example:
              2 3
              1 1
              2 2
              1 2

              My program gives 2, which I think is the right answer too.
              Sorry if all this sounds really stupid..

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

                Answer is 3. You can select any 2 of the 3 edges.
                Using the two self-loops once the path is 1->1->2->2->1

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

                  Thanks.. got it :)

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

                  So something like this? 

                  ll ans = 0;
	for(int i = 0; i < nodes; i++)
		for(int j = 0; j < adj[i].size(); j++)
			ans += sz[adj[i][j]];
	ans = ans - n;
	ans += (l * (l - 1));
	ans /= 2;
                  → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                in this test the answer is 3, because you should also count this pair: (first edge,second edge)

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

          I forgot second case anyway, so I got WA. But can you prove that only needed are these three cases ?

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

            Eulerian path/cycle exist if the graph is connected (edge-wise) and degree of all nodes are even except for 0 or 2 nodes are odd.

            so if all edges are doubled all degrees will be even, if a pair of edges don't share an endpoint then they will make 4 odd nodes

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

              Fantastic proof, thanks !

              I was so close to solve this :)

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

          I did the same. Wrong Answer on pretest 18.
          Edit: I messed up in checking whether all edges are connected or not.

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

    I did the same solution but I am getting WA on pretest 5 :/

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

    Not necessarily, for example two random self-loops work.

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

    Nope, check the graph 1->2, 2->3, 3->3, and you can use edges 1-2 and 3-3 only once by going 1-2-3-3-2-1.

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

Awesome problem set! problems was tricky though xD

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

Pretty nice contest. My most favorite problem is Div2-D. Though, I don't like Div2-B.

Btw, how to solve Div2-E? Is it some kind of DP?

UDP: I don't know if the words "geometric" and "depression" in Div2-B title are intended puns or not.

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

    Solve the multivariate linear indeterminate equation? I guess...

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

    The crux here is to notice that all we need is the sum of (signed) distances of the cokes that we include to our desired amount is zero.

    Then do we something like Knapsack's DP, except we notice that an optimal solution could be arranged so that we never stray beyond [0, 1000], supposing that we start at the desired amount and then add/subtract the distances from there.

    To make it run faster, we implement it using BFS (store the reachable ones in an array that indicated how many steps needed)

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

"14" it became my worst number because of problem B

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

Announcement:

Problem B. Weird journey

Note that it is not necessary for good path to go through all cities, we care only about roads.

are announcements supposed to give hints or only to clarify the statement?

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

    Guess they didn't want people hacking

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

      It is in pretest 18 I think.

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

    Actually, the statement is still incorrect:

    Little boy Igor wants to become a traveller. At first, he decided to visit all the cities of his motherland — Uzhlyandia.

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

      Ok then announcement was needed, but I still think it gave hint to some people :D

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

And what about div2 B pretest 10?

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

How to solve Div2 A ?

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

In Div1 C, I really tried hard to hack O(N^3) solutions. But the CF evaluation server was too fast.. They all worked within 900 ms.

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

    What was the expected solution?

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

      My solution is O(N^2) with BFS.

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

        Wow how did you solve ?

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

          We are to pick some of (a[i]-n) such that the sum of them is zero. We don't need to go to a state greater than 1000 or less than -1000, because for all i, |a[i]-n| <= 1000 and we should make zero. Therefore, BFS with 2001 nodes ([-1000, 1000]) will be enough.

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

            Which test case did you use to hack? As I feel intuitively that if you have a many types of a[i] the answer can be found quite fast and if you have a small number of different a[i] each iteration will have a small number of operations.

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

              Almost all solutions that I tried to hack first check if there is n. If not, they divide numbers into two groups, and calculate available sums for each group with time complexity O(N^3). No matter what numbers come, they iterate full O(N^3) loop. So I handcopied them to custom invocation and just tried K = 1000000.

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

what the data of DIV 2 B test 8?

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

please read this : http://codeforces.net/blog/entry/51309

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

Problem B — Masha and geometric depression It looks like not only geometric who has depression

My Status Right now

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

[DELETED]

*Thanks for the round

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

    You can't solve it,so you decide that it isn't your fault?

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

      Thanks for the awesome round. I am ok with this round. Sorry for earlier comments.

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

        Wrong ideas? I don't understand. If you don't know how to solve it, you can look at programme that have passed

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

int main() { cout<<100000<<" "<<1<<endl; for(long long i=1;i<=100000;i++) { cout<<10000<<" "; } cout<<endl; }

Used this code to Hack a Div.2 A...why do i get invalid?

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

    last element should not be followed be a space.

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

    I made a hacking attempt with similar script expecting TLE. But the solution passed in 436ms. I guess that was because the operations were small (x++)

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

I want to see, how many DIV2C solutions will fail due to integer overflow. I managed to hack 4 people in my room alone, who used int ans=0;. My hack test

6
1000000000 0 0 1000000000 1000000000 0

Correct answer: 3000000000

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

Can I already post "start systests" meme?

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

How to solve C ? I used two accumulative arrays where in the first array l=1 and in the second array l=2 (r=n in both arrays), then i looked for max range sum of both arrays. this is supposed to be O(n) but still gives TLE on pretest 10. help?

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

For Div 2 B,
Whats the correct answer for :
5 0 4 1
5

Main confusion:
Does abs(b)<=l check happen even if b is a bad number?

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

Note that it is not necessary for good path to go through all cities, we care only about roads.

So just a side note, not like the statement says the opposite? Really, why didn't you fix that? "At first, he decided to visit all the cities of his motherland — Uzhlyandia." or any other sentence does not even suggest that he may not want to visit all cities, does it?

Also, don't you guys think that "Boy thinks a path is good if the path goes over m - 2 roads twice, and over the other 2 exactly once." isn't well-defined for M=1? I made them tell me that the answer is 0 for M=1 on my third try.

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

    Well u kinda cant walk -1 edge, so.. Kappa. Agreed, statements are awful

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

      Yup, also "the other 2" suggests there are at least two edges. Not only did it take me three tries to convince them to explain the situation with M=1, but they didn't even make an announcement after that...

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

    The English in that statement was also very sloppy at times.

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

I am in doubt, was their any DIV2 round today?

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

    Yes, this contest was for both DIV1 and DIV2

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

can some one help me find out what is the difference between these two codes:

    int n,k;cin>>n>>k;
    ll ans=0;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        ans+=ceil(double(x)/k);
    }
    cout<<ceil(ans/2.0);

and this:

    ll n,k,ans=0,v;
    cin>>n>>k;
    for (int i=0;i<n;i++)
    {
        cin>>v;
        ans+=(v/k);
        if (v%k!=0)
        {
            ans++;
        }
    }
    ans+=(ans%2);
    cout<<ans/2;
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What I've noticed, is that the second code adds the remainder to the answer before dividing it. (wrong)

    The first one is adding the remainder after dividing, which is the right way.

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

    ceil will return for example 51 in case that the computer calculates 100.0 / 2.0 as 50.00000000000000000001... floating point arithmetics are calculated with some machine specified fixed precision...

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

      thanks for the reply so you mean that the second one is correct?

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

      Division by 2 does not have such flaw since 2 has exact representation. It will break only if the numerator is already not exact, which for integers means it must be more than 253.

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

        but in case of division by k this has a problem.(based on what others are saying)

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

        I remember I tested it on two integers less than 100 and it failed. I don't exactly remember the numbers.

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

          That is possible only if one of the numbers was already calculated with an error (for example, if you used the pow function).

          Here is an old but good TopCoder tutorial by misof to learn about integers and reals representation.

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

TFW you finish debugging 30 seconds after the round ends

feels bad man

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

Can someone tell differences between these codes for Div 2 A?

First one passed pretests and second didn't.

Code 1

cin>>n>>k;
FOR(i,1,n) cin>>arr[i];
long long int sum=0;
for(int =1;i<=n;++i)
	sum+=ceil(arr[i]*1.0/(double)k);
cout<<(long long int)ceil(sum*1.0/2.0)<<endl;

Code 2.

cin>>n>>k;
FOR(i,1,n) cin>>arr[i];
long long int sum=0;
for(int =1;i<=n;++i)
	sum+=ceil(arr[i]*1.0/k);
cout<<ceil(sum*1.0/2.0)<<endl;
→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think there are some issue in Problem Div2 B. For this reason system test is delayed.

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

Systest is still pending, because even the setters get WA 14 on Div2B :)

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

Div2.B... 13 is not unlucky number. now, 14 is unlucky number.

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

Div2 Problem B Case #14: 123 0 21 4 543453 -123 6 1424

Accepted. But A failed :-/

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

System test are over but div2 B test doesn't seem correct. 14 test case's ans should be inf but it shows 0

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

Div2 B : 1221 pretests passed -> 771 AC ..
May God be with us !!

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

Div2 B, WA on main test 43 opps :( :(

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

even though i am not the only one who dissapointed with problem B, but i do appreciate your effort for giving your time to us for making this contest, i'll wait for your next contest of course with a better problem to be solved, graciass

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

problem B

why output of this case is 0 123 0 21 4 543453 -123 6 1424

it must be "inf" because b1 = 123 will not be printed because it's invalid b2 = 0 will be printed because it's valid b3 = 0 will be printed because it's valid . . . infinity

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

    l is smaller than 123? The process stops at b1. Beware of the difference between "skip" and "stop"

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

    123 > 21 ... 0

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

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

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

editorial link is broken edit: fixed

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

I don't why but there is some issue with the challenging system near the end of the contenst. It seems that my hack page keeps refreshing and it failed to load the hack interface so I cannot hack other's solution...

Surprisingly after I change from chrome to firefox it suddenly works...Don't know why there is a difference between firefox and chrome...

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

Happiness is getting into Deep Blue.

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

System test data for Div-2 problem A are weak. They should test some hack cases too.

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

Here is interesting submission of Div2 E/Div1 C. It seems to be O(5004) with some heuristics. I try to find solution using one, two or three types if there is such. If no, then comes what should be O(5004) DP. But it passes systests.

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

Can anyone take a look at THIS submission please? This code gives correct output of the test case 15 on my compiler but wrong ans on codeforces' compiler. Help would be much appreciated. Input case : 3 2 115 16 24 48 12 96 3 720031148 -367712651 -838596957 558177735 -963046495 -313322487 -465018432 -618984128 -607173835 144854086 178041956 .Output should be '1' but on cf it gives me '3'.

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

    Anyone please?? Atleast you can run the code on your compiler with that input and let me know if you get the wrong ans or correct ans. :/

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

      Man !! you don't make your code easy to read.. do you...

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

For part A : I initially submitted 25910962 with variables declared globally and I got wrong answer in test 5. But after that I declared the variables inside the int main() and the solution 25923127 was accepted. Can someone explain it to me how this makes a difference?

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

    Compare ll w[10000]; to ll w[n];. First one fails, because n<=10^5 , but you declare the size as 10^4

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

For B div 2, shouldn't the following test case output in "0" instead of "inf"?

-1000 0 100 1
-1000

because b1 = B, and |b1| > L, she shouldn't write anything on the blackboard.

But I might've missed something. The hack attempt is here: http://codeforces.net/contest/789/hacks/312464

Thanks in advance.

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

    Ah, it is my blunder. I misread "expected output" as my own output.

    Kindly ignore above question.

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

In Div2 Prob B test case 14 — 123 0 21 4 543453 -123 6 1424 The output should be inf because First 123 would not be written on the board as it is greater then 21 but 0 should be written as its not present in the m numbers ,So it should have been written every time. But why is the answer 0..? Answer should have been inf

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

    Masha writes all progression terms one by one onto the board (including repetitive) WHILE condition |bi| ≤ l is satisfied. So if |bi| > l she will stop.

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

    No. The question clearly states that the number won't be written if it's absolute value is greater than 'L' and the loop would break. In this case, 123>21. So even that would never be written.

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

    The problem description state that she will write as long as the condition of |bi| <= L holds.

    On the test case 14, b1 = 123 is already greater than 21, hence the girl will stop there.

    There is a difference between skipping a number (because the number exists in bad number set) and stop writing (because the current number already exceed the given bound).

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

Thanks for the great contest!

Very clear description and interesting solutions. Unfortunately, I spent half of the time of the contest trying to figure out why my solution for problem C did not work? In the end, a friend told me that the function f(l, r) = sum_{i=l}^{r — 1} |a[i] — a[i+1]| * (-1)^i-l while I thought it is f(l, r) = sum_{i=l}^{r — 1} |a[i] — a[i+1]| * (-1)^i-1. Anybody else had the same problem?

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

I used the following generator code to hack a solution 25904282 for Problem Div2A: 

printf("100000 1\n");
for(i=0;i<100000-1;i++)
{
    printf("%d ",10000);
}
printf("%d",10000);
printf("\n");

Unfortunately, the attempt became unsuccessful as the solution produced the output in 998 ms.

Later during the system test, the same solution gave a TLE on the exact same test case — Test Case #27 :(

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

    It's bad idea to hack solutions where only basic addition and subtraction operations are performed in loops.

    See this solution. It is performing 10^14 operations still system test passed.

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

      It is performing 10^14 operations still system test passed.

      Lol no, this is compiler optimization :D

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

I have an interesting solution for div1 D and maybe it need only O(n) queries.

First we choose a number number G less than , probably (M is the coordinate range and n is the number of lines). And we can random several times to find a point a = (x, y) such that .

Then, for vertical lines, we query all the point (x + kG, y) which is in the coordinate range. And we can find several lines. But if there are many lines which are very close, we may only find out some of them.

So, the next step, we need to find out the remaining lines. If the dis between two adjacent lines is larger than 2G, then there are no lines between them. Otherwise, we can search between these two lines. Each time we query the midpoint of the search range, if we get a new line, then we try to search both sides and otherwise, exit.

We can find out the horizontal lines analogously.

This is my code 25939395.

During the contest, I made some stupid mistakes and failed to pass it. Sad story.

→ Reply