Блог пользователя Barichek

Автор Barichek, история, 8 лет назад, По-русски

Всем привет!

29 марта в 19:05 MSK состоится рейтинговый Codeforces Round #407.

Задачи готовили я — Игорь Баренблат, Станислав giraffeh Томаш и Антон arsijo Цыпко. Большое спасибо Ивану Fekete Фекете, Адальберту Adalbert Макаровичу, Роману chakred_namor Деркачу, Владиславу winger Исенбаеву и Александру AlexFetisov Фетисову за тестирование, Николаю KAN Калинину за помощь в подготовке раунда, а также Михаилу MikeMirzayanov Мирзаянову за системы Codeforces и Polygon.

Как всегда участникам будет предложено по пять задач и два часа на их решение. Разбалловка будет объявлена ближе к началу раунда.

Надеемся каждый найдет для себя интересную задачу. Всем успешного раунда и повышения в рейтинге!

Разбалловка:

Div2: 500-1000-1500-2250-2500

Div1: 500-1250-1500-2000-2250

UPD. Разбор опубликован.

Поздравляем победителей:

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

  • Проголосовать: нравится
  • +414
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

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-)

»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Hope to have interesting problems and good problem description.

»
8 лет назад, # |
Rev. 50   Проголосовать: нравится -94 Проголосовать: не нравится

wish high rating for all

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    now you can see my pokerface

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится

      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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

:|

»
8 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

How many problems?

»
8 лет назад, # |
  Проголосовать: нравится +83 Проголосовать: не нравится

who is maria ivanova Barichek ?

»
8 лет назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

I will be in top 1000 this contest!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 .

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +77 Проголосовать: не нравится

Rating prediction: div1 div2

Extensions:

Have fun & high rating:)

»
8 лет назад, # |
  Проголосовать: нравится -39 Проголосовать: не нравится

Is a2oj down?

»
8 лет назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

I believe I can fly.

»
8 лет назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +53 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В задаче D есть ограничение на кол-во прямых?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Полагаю, это число следует из ограничений на тест-взлом (n, m  ≤  104)

»
8 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem with the hack page :/

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Hi div2 :V

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

RIP RATINGS...

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

what's test #14 in B Div2?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve Div2B. Got stuck for 1 hr.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      @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;
      
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I did that ..can you check my submission?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 ?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What could be Problem B test 14 ?

»
8 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

How to solve C?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

»
8 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

This >.<

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hacks, Hacks everywhere 8-) <3

»
8 лет назад, # |
Rev. 5   Проголосовать: нравится +30 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +27 Проголосовать: не нравится

        1- pair of self-loops

        2- self-loop and edge

        3- pair of edges that share an endpoint

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          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;
          
          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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..

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

                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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Thanks.. got it :)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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;
                  
              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Awesome problem set! problems was tricky though xD

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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)

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Div2 B take a lot of time debugging.

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

And what about div2 B pretest 10?

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

How to solve Div2 A ?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +39 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What was the expected solution?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Wow how did you solve ?

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +52 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what the data of DIV 2 B test 8?

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
»
8 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

My Status Right now

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I tried to hack a solution with this code

for problem A in Div.2

include

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

It says invalid input.Why is it so?

»
8 лет назад, # |
Rev. 7   Проголосовать: нравится -14 Проголосовать: не нравится

[DELETED]

*Thanks for the round

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 7   Проголосовать: нравится -11 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    last element should not be followed be a space.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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++)

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

DIV2 B if |b1|>l masha will stop,but you do not say it!

so if |b1|>l && q=0 masha can write 0 ,i think the answer is "inf"! But your question is "0", you did not give me a clear meaning! sorry my english is poor.

»
8 лет назад, # |
  Проголосовать: нравится +144 Проголосовать: не нравится

Can I already post "start systests" meme?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
8 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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...

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Спасибо за задачи :) до встречи на всеукре)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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;
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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...

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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.

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

http://codeforces.me/contest/789/submission/25922219 Отличные претесты :)

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

TFW you finish debugging 30 seconds after the round ends

feels bad man

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

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;
»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

С упала только потому, что неправильно обработал случай с n = 0(подумал, что в таком случае нам вообще не надо покупать колу и выводил 0). Чо ж вы в семплы его не включили или не написали в условии жирным, что изначально у нас НОЛЬ ЛИТРОВ КОЛЫ И ГАЗА СООТВЕТСТВЕННО. Формально косяк мой, но это же не совсем крайний случай и многие его учли(и я тоже), просто я неверно его обработал.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

Accepted. But A failed :-/

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Barichek (предыдущая версия, новая версия, сравнить).

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

editorial link is broken edit: fixed

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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...

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Happiness is getting into Deep Blue.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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'.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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. :/

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.me/contest/789/hacks/312464

Thanks in advance.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Kindly ignore above question.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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).

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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?

»
8 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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 :(

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      Lol no, this is compiler optimization :D

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +30 Проголосовать: не нравится

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.