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

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

Всем привет!

В среду, 14 декабря в 17:35 MSK состоится Codeforces Round #384 для второго дивизиона. Традиционно, участники из первого дивизиона смогут принять участие вне конкурса.

Подготовкой раунда занимались Юра hloya_ygrt Шиляев и я, Кирилл kefaa Гулин.

Выражаем благодарность Николаю KAN Калинину за помощь в подготовке раунда и Михаилу MikeMirzayanov Мирзаянову за системы Codeforces и Polygon.

Вам будут предложены 5 задач и 2 часа на их решение.

Разбалловка будет объявлена ближе к началу раунда.

UPD. Разбалловка: 500 — 1000 — 1250 — 2000 — 2500

UPD2. Контест завершен! Всем спасибо за участие. Надеемся, вам понравилось :)

Разбор

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

Div2:

  1. TheBartender

  2. Ownz

  3. lesskreker

  4. xyt520

  5. SpinyAnteater

  6. y32M-71693993

  7. ezLadder

  8. tqyaaaaaaaang

  9. Fiks_warrior

  10. 00001

Div.1:

  1. Um_nik

  2. kmjp

  3. Temirulan

  4. zscoder

  5. rajat1603

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

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

Good look all participants!!

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

Why we can't see this announcement at the homepage. And why writer's name is missing at the upcoming contest list? Just asking :) BTW thanks for preparing the round. Hopefully everything will be alright (no long queue and fast rating update) :)
UPD: The announcement is now available at the homepage.

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

    For those who gives me negative vote, please let me know how can I improve my previous comment? Normally we can see the announcement at the homepage and every contest has its writer's name at the contest list. Thanks in advance :)

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

Думаю задачки будут интересные :D

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

Is it rated?

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

    yep.. it's rated.

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

    -48 votes?? I think we are being quite rude here. This person has participated only once! It might not be obvious for newcomers. This much hostility makes the community unhealthy for beginners.

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

i hope the problems statements will be short like this announcement and less hacking

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

    Why less hacking?

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

      because hacking system is not fair , you can be in the room where most of the room solve the problem wrong and you make a lot of hacks on the other side in another room all people solve the problem right is it fair ?

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

        Life is so unfair, my friend.

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

        In my opinion, it's because that CLEAR and CONCISE programming is discouraged. Also, not every programming language is understandable. Coding in really difficult languages (brainfuck) is also encouraged.

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

          Actually , no.

          See Contest rules , Can-do's and Can't-do's , Point no. 3

          " It is forbidden to obfuscate the solution code as well as create obstacles for its reading and understanding. That is, it is forbidden to use any special techniques aimed at making the code difficult to read and understand the principle of its work. "

          The idea is to subject your code to a jury of your peers , who have all shown confidence in their code (by locking it).

          The guiding reason behind it is that you are expected make the logic of the code so infallible that it simply cannot be hacked , and not deliberately obfuscate code , which is against both the spirit of the competition and the rules.

          It is the objective of the writer to write perfect , legible code. It is the objective of the hacker to expose flaws in that code.

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

        I think you want more hacking: wrong solutions in every room.

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

    So much for "less hacking"... there are 40 pages of hacks: http://mirror.codeforces.com/contest/743/status (EDIT: select "Verdict: Hacked" on the right side panel)

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

Please include some hints for the problems in the editorial like in the editorial for the previous round
they are really helpful

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

Well, long time no cf. I would love to take part into this round. Wish me scores increasing!Haha

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

Unusual time!! Yayy!! Codeforces is back...I missed you. Unusual is the new usual :D

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

Am I the only one here thinking that this round features the same writer of round 321 (which has all questions named after kefa)

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

I think they should have mention it in announcement (is it rated or not). Because most of the registrants are new and they don't know that each round is rated(If it is not mentioned explicitly ). Otherwise freshers will keep asking, whether its rated or not and they will keep getting negative votes. I am sure that i will also get negative votes for this comment for no reason.

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

    Usually a regular round is rated. So, in my point of view it's unnecessary to mention if the round is rated. But in case the round is not rated then it's necessary to mention it. And newcomers should read the FAQ before participating. Thanks :)

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

My sister once signed up for a codeforces account to try out competitive programming and stopped 1 year ago. Yesterday when she received an email about this round she asked me: "why do your codeforces contests always start at an unusual time"

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

Three rated rounds in one week, how unusual!

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

Three rounds in one week! That's the spirit!

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

2 hours, 5 Problems the traditional Codeforces Rounds are back!

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

Tomorrow I've 2 exams! but I can't read now, because excited about CF :D

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

Am I the only one who can't do anything in the few moments just before every contest ?

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

Notice anything unusual about this screenshot?

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

Долбаная задача A. Как ее решить?

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

Прикольно. В 321м раунде Владик(Vladik) дал задачи про Кефу(kefaa), а теперь Кефа дал задачи про Владика :)

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

Great contest!!!

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

Maximum fun from problem C )

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

Approach for problem E?

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

    if you fix the minimum frequency , then you can calculate the answer in N*2^8 using dp with state(position , mask) , so now just do a binary search to find max posible frequency. Total complexity N*logN*2^8

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

    At first we can list all of the length t, which means that each digit can appear t or t + 1 times. Then we need to figure out the longest subsequence, so we can use dynamic programming to do this. Let dp[mask][i] mean the leftmost position for us to consider the next digit when we now have filled the digits set mask, and we have i digits whose length is t + 1. We can choose a digit not in mask and greedy choose the next position, which can be processed in O(n2) time at the begin of the program. Thus the whole algorithm is O(8n2 + 8n * 28).

    UPD: We can also binary search t to speed up the algorithm into . And if n = 106, we can use binary search in vector to greedy get the next position, in this case the whole algorithm is .

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

    i tried making D[k][i][j] — first position where ends finding j elements of type k from position i after that, for each permutation of the subset ( 0 -> 8 ) i try to find best solution, hard to explain, i finished the solution right when the time ends, the solution is correct but not sure if it fits in time

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

    i think i found a solution in O( N^2*8 + 8!*8*log(n) + 8!*2^8 ) precalculating D[k][i][j] — from position i to D[k][i][j] are j elements equal to k. With that precalculated bs the answer making all permutations and checking every combination if its valid in O( alphabet = 8 ). After we find the respective number, we can check which elements will appear lenght+1 times in the final answer in O( 8! * 2^8 ). I implemented this solution with linear searching instead of bs and it works pretty fine: 68ms http://mirror.codeforces.com/contest/743/submission/22980164

    Sorry for bad english

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

Hack fiesta with 1 on problem C :)

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

How to solve A?

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

    Let the binary string be s (1-indexed). Then if s[a]==s[b], then answer is 0, else it is 1.

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

    0 if the companies in A and B are different or 1 otherwise.

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

    Well just print 0 if value at a and b are the same. Otherwise is 1. Because if value at a and value at b are different, you have to get to the next airport if the next one is same as b you travel right away to b so cost 1, on the other hand it will cost 0.

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

That feeling when you find a mistake in your A solution just after you lock it. :'(

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

Worst contest of my life ;_; . Got killed by A ;_;

Good problems (y)

3 more minutes and I could've at least submitted D ;_;

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

read problem D wrong twice.. thought one would take before another and write ~100 lines for tree dp...

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

D should have a test case with all negative pleasantness.

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

Hack Festival!@#(@($*!@(#!@

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

For Problem C:

if (n==1) answer = -1;

else

numbers are (n) , (n+1) and (n*(n+1))

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

А почему в задаче E такие маленькие ограничения? Мое решение работает за , его можно упростить и получить решение за

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

Can anyone tell me how to do D?

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

    This is my logic, but didn't get to submit

    First, sum all values in a subtree, and store in a sum array.

    Then, do a DP on each vertex and find the max value you can get from this subtree, using values from sum array.

    Then traverse the tree again and take 3 global variables with you : v1=-inf, v2=-inf, v3=-inf. V1 holds the max value of two subtrees( we'll use dp table from before ). answer is v1, if all v1,v2,v3 are > -inf.

    v2 and v3 are the two values we took to make v1.

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

      Why did you even get downvoted? This is a pretty solid explanation.

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

    For every node you can store the sum of pleasantness of its subtree with DFS. Let's call this value P[node]

    Suppose two nodes u and v, these nodes can be paired if u is not an ancestor of v and vice-versa.

    You can traverse the tree and, for every node u find another node v which is neither an ancestor nor a children of it, with maximum P[v] and update the final answer.

    I think there are several ways to find that node quickly, I used Range Maximum Query with Segment Tree.

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

    The last part of I_love_Captain_America solution can be solved using segment tree too. During traversing we can mark each node by it's start and end time. Now all the node of a sub-tree will fall into a range [start time,end time]. If we take this node for Chloe we need to choose another non-intersecting sub-tree for Vladik. We can take the sub-tree from range [1,start time — 1] and range [end time+1,n] except the nodes fall in the path from root to current node. To exclude the nodes from root to current node we can update it's value with a large negative number at the beginning and rollback to it's actual value at the end. You can look at my submission for better understanding.

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

Интересно, почему в задаче A зафиксировали ограничение по времени 2 секунды, когда, на самом деле, такая задача, а точнее решение к такой задаче работает меньше 1 секунды — или что, авторы подразумевали другое решение, которое работало бы за чуть менее 2 секунды — или это просто случайная ошибка?

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

How to go for Div-2 B

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

Currently I have been in the condition where you know that your code (for A) is gonna fail on System Test and you were knowing after locking the problem but still you have hacked solutions which was having the same mistake as yours and you just got more points in hacks than you are gonna loose in System test fail.

P.S. : Sometimes It is better to find a testcase which fails your code and find others in a room who has done same mistake as yours. 11 hacks for me for loose of 472 points! :)

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

Test Case 11 for Problem D? Any ideas?

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

Problem A was just made for hacking..any solution where you do not see
if(s[a-1]!=s[b-1]) cout<<1; else cout<<0;
was hackable.

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

How to approach question D ?

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

^_^

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

What should be the approach to solve Div2 C (assume that you know nothing about Egyptian fractions). I formed equations, tried solving them, but was not able to solve :(

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

    Example case 2 is your friend , personally i think this problem is too mathematic.

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

      Couldn't agree more. I wrote so much equations but nothing matched. Then i did stress testing to find some pattern but i failed there aswell, and whole time i was thinking that case 1 and 2 are just baits..Lost so much time on it..

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

    2/n = 1/n + 1/n

    So, n is x.

    1/n = (n+1)/(n*(n+1)) = 1/n+1 + 1/n*(n+1)

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

    I didn't know about Egyptian fractions! I wanted to find some pattern and suddenly it came to my mind! And the 2nd test case helps a lot to solve this problem.

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

    I did not had any idea about Egyptian fractions so tried the following method. I ran 3 loops for x,y,z, with upper limit 200...after checking for small values of n, I found that the solution will always be n n+1 n*(n+1). I put these values in the expression. And found it to be true.

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

    It is logical that for any number 2/x, it can be divided into 1/x + 1/x

    So first number is x.

    Now we have to split 1/x into two parts (1/y and 1/z) such that sum = 1/x.

    Observation: x/x+1 * 1/x = 1/(x+1) -> we pick such a division to get 1 in numerator

    Therefore we can divide the remaining 1/x into 1/x+1 + 1/(x)*(x+1).

    For example, 1/3 can be divided into 3/4 and 1/4 parts, 3/4th of 1/3 = 1/4, and 1/4th of 1/3 = 1/12. So answer for 2/3 = 1/3 + 1/4 + 1/12

    And you realize all this and fail on n=1...I Hate my life.

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

    I didn't know about egyptian fractions. My approach was heavily influenced by example 2, which was n=7, sol: 7,8,56. Using this example, I proved that n, n+1, and n(n+1) always works.

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

    You can run a brute force to generate all solutions for a particular n and notice that a solution of form n, n + 1, n(n + 1) always appears. You can now prove that it works for all n by simple algebra and go for it.

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

    First, I thought that 2/n looks a bit weird and it is worth to remove 1/n from 2/n (put x = n). The remaining equation looks much simpler: 1/n = 1/y + 1/z. If you look at the examples or try to guess yourself, you will notice that 1/2 = 1/3 + 1/6; 1/3 = 1/4 + 1/12 etc. Then you can realize that 1/n = 1/(n+1) + 1/(n(n+1)). So, y = n+1, z = n(n+1).

    Otherwise, you can just rewrite simplified equation like follows: 1/n — 1/y = 1/z (y-n)/yn = 1/z All you need to get a solution is to set z = yn and y-n = 1 — which gives you the same as above.

    And, of course, notice that y and z should differ — so n = 1 is a special case. Actually, maximum value of 1/x + 1/y + 1/z we can get with pairwise different x, y, z is 1/1 + 1/2 + 1/3 = 11/6 which is less than 2/1 — so for n = 1 answer is -1.

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

    Initially I also formed equations and starting thinking of LCM of x,y,z . But then it was too much of trouble so I gave up that approach and started thinking from scratch. Following is what I next thought: Think of 2/n as 1/n+1/n . Then by observation , 1/n can be written as 1/(n*(n+1)) + 1/(n+1) so write any one of the two (1/n)s as 1/n*(n+1) + 1/(n+1). Thats pretty much what i did. Took me 45 minutes to see this . But then in the end my solution got hacked in the last minute (and i could not correct it in that less time)because there was one edge case here(n=1 ; ans would be -1 for this case). Hope this explanation helps.

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

    I didn't even think that it could be solved with a formula :( I used brute force. The idea is:

    1. If 1/x + 1/y + 1/z = 2/n, then some of {1/x, 1/y, 1/z} got to be bigger than 1/3 * 2/n, which means that some of {x, y, z} is less than 3n/2 (which is of order 10^4). Without loss of generality, let it be x, so we guessing it by looping from 1 to 3n/2.
    2. Next, same reasoning can be applied to 1/y + 1/z = 2/n — 1/x; at least one of {1/y, 1/z} got to be bigger than 1/2 * (2/n — 1/x), therefore one of {y, z} is less than 2 / (2/n — 1/x). Again, this is something of order 10^4 so we can afford doing second loop over y.
    3. Now, you just calculate 2/n — 1/x — 1/y and check a) whether it can be represented as 1/z (so basically nominator divides deniminator) and b) that x != y != z. This check takes constant time, so the whole solution works in O(n^2).
»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

When contestants in TOP 20 submitted A and C after E, and almost everybody has additional points for hacks you know that it was a good contest :)

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

I didn't get hacked on A or fail system tests, but can someone tell me what was the hack on A?

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

    Something like this:

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

      Can you explain what people did wrong to get this wrong?

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

        If s[a] != s[b] they were looking for i, j:

        s[i] != s[a], abs(i - a) -> min,
        s[j] != s[b], abs(j - b) -> min,
        ans = min(abs(i - a), abs(j - b)).
        

        So for test

        6 1 6
        111000
        
        i = 4, j = 3,
        ans = min(3,3) = 3 != 1
        
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Read this
    Some of the test cases I used are
    12 6 12
    101010111000
    9 4 9
    101000111

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

Did this ever happen to anyone else? My submission for problem C was treated as 3 distinct submissions and I got penalty for 2 re-submissions. Generally, Codeforces doesn't allow same code to be submitted multiple times but this ignored that rule too.

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

Wasted a lot of precious time figuring out C! If not, could've hacked more solutions of A! :(

Nevertheless, a good contest allover! :)

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

waiting for rating ...

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

This was the best round except my performance. No waiting queues. Fast system testing. Problems were too good. _/_

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

In Div2 D I couldn't understand if all the gifts have negative values then why not the answer is 0 as they want to maximize the pleasantness and hence both will not pick so answer should be 0 rather impossible.

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

Why this submission AC....Data set very WEAK....

743B - Chloe and the sequence

22968117

This Submission hack for test case: 9 8541

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

http://mirror.codeforces.com/contest/743/submission/22961619

This code generates correct answer for pretest 8 on my machine but not on codeforces server. Can somebody give a detailed analysis on why it happened? Thanks :)

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

    I'm not sure why it showed up differently on your machine, however your ans variable is an integer instead of a long.

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

    I've figured it out! When you make the bitset out of k, in your computer the initialization treats k as long long. However, in codeforces server, k is parsed into an int, and then the bitset is generated. Sorry, but your wrong answer is a consequence of lack of standardization among compilers :/. (You should try to print string s in custom test of codeforces to see how no bit of k is being registered in the server.)

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

I saw a wrong solution for A, then I quickly generate test and hack it. Unfortunately, he resubmit it just before me hack and I get a fail hack :(.

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

    I think if you try to hack a code and this code is resubmitted it will said "that code has been hacked or resubmitted"

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

      I don't know why :(. I easily paste the input, click the hack button and I didn't see any alert.

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

        if you see that he resubmitted a code it doesn't mean that your hack is tested on the new code simply your hack is wrong :"D it is not a problem .... and it is illogical that you hack a code and your hack tested on another code :"D.

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

    I was the one you tried hacking. You are not correct, thienlongtpct

    From log we see, that I submitted after your hack:

    01:11:27  A  Unsuccessful hacking attempt by thienlongtpct
    01:11:38  A  Accepted [main tests]
    

    My initial code: 22962124 simply passed your hack http://mirror.codeforces.com/contest/743/hacks/273143/test with a correct result :)

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

      Oh, maybe when I see unsuccessful hacking, I reload a page and see you have resubmit the problem. Congratulation for your new color.

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

I was wondering why a hack of 10000 (or 1e4) on problem C gave me an unsuccessful hack while the exact same code TLE'ed for an input of 8863. Here is the code: http://mirror.codeforces.com/contest/743/submission/22965351 Any inputs are much valued.

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

    I think it not depend on how bigger the number N is, it depen on the time we find the answer.

    if (a % b == 0 && x != a/b && y != a/b && a/b > 0 && a/b <= 1000 * 1000 * 1000) {
        printf ("%d %d %d", x, y, a/b);
        exit (0);
    }
    

    Maybe with n = 10000, it may find the answer quickly and and then end the program (exit (0)) when the stament is true. However, with n = 8865 it cosume more time to find the answer.

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

    When I try it on CUSTOM INVOCATION
    - for 10000

    - for 8863

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

daayum, so close, yet so far. i hope, next ranked my rank can improve at least one point. ![](http://pass.mivo.com/numpang/ramadoka.codeforces.png)

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

contest is over guys now enjoy!!!!

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

Соревнование по внимательному чтению условий — это плохо. С C все норм. С A видимо нет, потому что сотни людей неправильно поняли условие. D — это вообще жесть. "Задача ни о чем, поэтому напишем условие максимально непонятно, чтобы искусственно повысить сложность". Ну или у вас реально проблемы с формулировкой условий. BCD — 3 безыдейных простых задачи. A хотя бы забавная. Ограничения в E я понять не могу. Такое чувство, что специально хотели пропускать O(k·kn). Даже близко не понимаю, зачем. Была бы хорошая задача, если бы ограничения были (k ≤ 16, n ≤ 105).

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

    Вот мне кажется ты не прав. Хороший раунд получился:

    • А. Я перечитал задачу. Там всё достаточно подробно и четко. Кажется, что там присутствует идея с тем, что ответ это 0 или 1. Если не сообразить, то многие могут набажничать (ведь эта задача для тысяч участников разного уровня подготовки). Посмотрел несколько упавших попыток — не похоже на непонимание условия.

    • B. Для более чем половины участников задача была в достаточной степени содержательной. Конечно, какой-то особенной новизны в задаче нет. На официальную олимпиаду такое брать нельзя, на Д2 раунд вполне можно. Такое случается для первых задач Д2, ничего особенного в этом нет. В этот раз я следил за раундом из университета и наблюдал как мои студенты пишут раунд. Участнику, который впервые столкнулся с похожей конструкцией задача была интересна и безусловна полезна. Вот чего не хватает — хорошего разбора по ней с введением в строки Грея и описанием некоторых свойств и альтернативными способами построения.

    • C. Математическая задача, которую решили далеко не все. Ну вот что значит безыдейная? Технических сложностей её написать, очевидно, не было. Значит не придумывали.

    • D. Отличная задача на анализ деревьев, поиск в глубину и тому подобное. В условии явно написано "корневое дерево". Не думаю, что были особые сложности с пониманием её условия. Идея в решении, конечно, присутствует. Почти всем из Д2 она была интересна.

    • E. Я не считаю, что если в задаче возможно более эффективное решение, то его обязательно надо требовать от участника. C задачей справились 59 участников из 4381. Большая часть из решивших сделала это в последние полчаса контеста. Такой исход мне нравится значительно больше, чем решения от 0-3 участников и то, которые на самом деле из Д1.

    Кстати, вопросов по задачам во время раунда было рекордно мало. Это сильный признак хороших условий.

    Мне кажется, ты имеешь какие-то странные ожидания от задач второго дивизиона. Следует понимать, что ты Legendary grandmaster over 3000. Конечно, большое количество задач для тебя безыдейны, но не являются таковыми для многих участников Д2. Эти контесты в первую очередь ориентированы именно на них и не ставят перед собой цель хорошенько озадачить тебя.

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

      A: Лично у меня проблем с пониманием не возникло. Но я сделал по ней около 5 взломов; все решения в комнате делились на одинаковые правильные и одинаковые неправильные. Когда один человек так ошибается, я считаю, что он неправильно прочитал условие. Когда одинаково ошибается треть комнаты (и среди них золото IOI), я начинаю подозревать, что в условии есть что-то, что натолкнуло на такое понимание. Для конкретики: все решения, которые я взломал, считали, что можно делать не более одной пересадки.

      D: Корневое дерево — это единственное, что написано в условии явно. Дальше идет что-то невнятное про веревочки. Я сильно сомневаюсь, что только мне пришлось прочитать условие два раза, чтобы понять, что нужно выбрать два невложенных поддерева. Дальше задача как задача, но парсить условие неприятно.

      E: В таких случаях в разборе надо писать "вот клевое решение, но мы специально понизили ограничения, чтобы заходили более простые решения, например такие:". Сейчас же в разборе написано более сложное и медленное решение. Это наводит на мысль, что низкие ограничения — это не осознанный выбор.

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

        Извиняюсь за действительно существующую неточность в задаче Д.

        По задаче А, в условии задачи четко указано (целый абзац уделен)

        Владик может совершить любое количество промежуточных перелетов

        Но действительно, многие сильные участники, к примеру netman, слали решение с одной пересадкой, потому что оно показалось им правильным.

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

Hi Guys!

I need some help, I'm not an expert in java but I'm not sure what is happening about this code, for several prime numbers is working but for instance for the prime number 6491 I'm getting something strange when I run the code. This is my actual code

As this number is prime then the List div is going to have just two elemens 6491 and 6491 but when I compare them java is saying its comparisson is false when should be true, could some one tell me please if I'm missing something or I did something wrong?, thank you in advance

 List<Long> divs(long n){
    long half = n / 2 + (n % 2 == 0 ? 1 : 0);
    List<Long> div = new ArrayList<Long>();
    for(long i = 2; i < half; i++){
      if(n % i == 0){
        div.add(i);
        div.add(n / i);
        break;
      }
    }
    return div;
  }
  
  public void solve(final long n){
    if(n == 1){
      System.out.println(-1);
      return;
    }
    List<Long> div = divs(n*n);
//    System.out.println(div.get(0)+" "+ div.get(1)+" "+(div.get(0) == div.get(1)));
    if(div.get(0) == div.get(1)){
      System.out.println(n + " " + (n + 1) + " " + (n * (n+1)));
    }
    else{
      System.out.println(n + " " + (n+div.get(0)) + " " + (n+div.get(1)));
    }
    return;
  }
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    I think you have to write your code on ideone in order to be readable

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

      Thank you and sorry about it, it was my first comment ever, I research about my comment and seems like my mistake was to write div.get(0) == div.get(1) instead of something like div.get(0).compareTo(div.get(1)) == 0

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

Can anyone please tell me what's special about test case 15 in problem D? I am getting WA. Here is my submission.

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

    You only check for subtrees of the first tree that have more tan 1 child. It is possible that the answer is lower in the tree. Take the following test case: ~~~~~ 7 -1 -1 -1 1 1 -1 -1 1 2 1 3 2 4 2 5 3 6 3 7 ~~~~~ Your program will state that the answer is 1 (from the subtree rooted at 2)+(-1) (from the subtree rooted at 3), when actually, the answer is 1 (from the subtree rooted at 4)+1(from the one rooted at 5)

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

Problem C My code is incorrect, however I pass the final test... Code refer to this paper

You can hack my by follow data whose factors != 1 mod 24

73 97 193 241 313 337 409 433 457 577 601 673 769 937

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

Can someone explain how to solve D ? I don't understand the editorial and it's a bit hard to analize codes.

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

    First, by dfs you can get sum[u] and dp[u].
    - sum[u] means the sum of a[u] and a[ vi ],vi is the son of u
    - dp[u] means the max value of sum[u].....dp[ vi ],vi is the son of u
    and start another dfs
    when dfs(u),
    - if u have more than 1 son you choose twos sons v1 and v2,satisfy dp[v1] and dp[v2] is the max and second max value in the son of u.and record the max value of v1 + v2.
    here is my code 22968058

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

can anyone explain the idea of problem B with proof?

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

    its a constructive algorithm so it prooves itself. you can calculate the length of the array in o(n) with formula lng[i] = lng[i-1]*2+1; array is constructed as last array + new element + array; so thr new element is in the middle. with that observation you can say that if the element k you search is in the middle you can say its the unique element of the given length. if its in the left side, you search in array n-1 the same k. if its in the right side, you know that both halves look the same so you find the corespondent of the k-th element in the left side, which is k-lng[n-1]-1 and search that element in the n-1 string

    hope it helps, sorry for bad english

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

Can anyone help me with this ? I can't find out my error .

code: here

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

    Input

    15 18432

    Participant's output

    <

    Jury's answer

    12

    char(12 + '0') will be represented as char(12 + 48) = char(60) = '<', not "12" as you want. Actually, your solution will not fit in the time limit as far as the length of the resulting string will be too large.

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

743B — Chloe and the sequence : value of k cannot be greater than 2^50 — 1 but in** test case 34** it is 2^50. My submission was evaluated as wrong please take desired action.