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

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

Добрый день!

Уже завтра, в 07.02.2019 16:35 (Московское время) состоится Codeforces Global Round 1.

Это первый раунд из новой серии Codeforces Global Rounds. В раундах могут участвовать все, рейтинг тоже будет пересчитан для всех.

Призы в этом раунде:

  • 30 лучших участников получат футболки.
  • 20 футболок будут разыграны случайным образом среди участников с 31-го по 500-е место.

Призы в серии из 6 раундов в 2019 году:

  • За каждый раунд лучшим 100 участникам начисляются баллы согласно таблице.
  • Итоговый результат участника равны сумме баллов для четырех лучших выступлений этого участника.
  • Лучшие 20 участников по итоговым результатам получают толстовки и сертификаты с указанием места.

Задачи для этого раунда были разработаны целым коллективом авторов: _h_, simonlindholm, grphil, vintage_Vlad_Makeev, GreenGrape, budalnik, cdkrot и мной. Спасибо arsijo и cdkrot за помощь в координации раунда, а также majk, pashka, Jeel_Vaishnav, Ashishgup и Jatana за тестирование!

Удачи!

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

  1. tourist
  2. Um_nik
  3. TLE
  4. mnbvmar
  5. sunset
  6. EvenImage
  7. ksun48
  8. molamola.
  9. snuke
  10. fateice

Разбор.

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

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

Among reds and yellows, there is GreenGrape too. :D

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

I hope the difficulty gap between problems will be proper.

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

Just love the unstable contests. GreenGrape is here so we can hope for hell of an unstable contest!I mean contest with weak pretests O_o

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

how many problems will be there?

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

What is the number of problems? And round duration???

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

Me in this round.

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

It's not like I am going to get any GP score, but it seems a bit unreasonable to rank 4 out of 6 contests, especially with the fact that rounds are not announced weeks ahead of the schedule for participants to allocate time slot for the contest.

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

Nice contest after chinese new year :D Good luck all !

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

wishing ** Good luck** to everyone who is going to participate. - !NOOB :|

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

Why am i getting negative contribution without doing anything.

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

I'm not so sure if this is just me or the case for others too, but I feel like weekends would be more convenient for such rounds, people might be more busy during weekdays. Just an opinion I might be wrong :) Best of luck to those participating in this one!

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

There used to be a time when questions at the level of C were thought-provoking. Now the contests are like type first 3 fast and sometimes the transition in difficulty is so drastic that as you move from 1 level to another, the difficulty increases manifold. I believe A should be solved by 80%, B should be solved by 60%, C by 20% and D by like 7-8%. And C level questions need to level up.

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

Well shit. I can't participate again because the time is too early.

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

How many problems and duration ?

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

Новый вид раундов, класс. Надеюсь, будет круто :D

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

Getting One T-shirt can make your motivation level rise to the moons! Best of luck everyone.

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

Will it be in ACM-rules? Or in CF rules?

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

Happy Coding guys !

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

There was(thanks for the correction!) a 'и' in the English post. Now that I learned Russian a little, I do know it means "and" in Russian, but for those who don't know Russian, it's a bit confusing (especially when it's in the problem statement -- which I've encountered long ago, though it was clear from the context that it means "and" ;)

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

Should we expect an interactive problem?

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

seem difficult for practicer like me to compete t-shirt...

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

Feb 7, 2019: Day of emancipation div2 and div3....

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

Hi everyone!

I got my old PC fixed just in time to do the contest. Excited to do this contest and this is such a nostalgic feeling. Let us enjoy it together, everyone.

Also, 1 like for getting my main PC fixed. or my PC dies. Your upvotes are really needed. Who wants a poor PC that went through such a harsh life of having 50 chrome tabs open every moment to die? Your likes are needed people.

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

    Oh, at this rate you guys are gonna even kill my old computer and I won't be able to do the contest. Keep it up everyone, 100 downvotes and my battery will blow up.

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

    Protip: you can put a whole persistent OS on a USB drive, and boot from it anywhere (except where BIOS is locked). You don't need your own PC at all.

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

      Oh that's actually really cool. If I had something like that, I could be using an updated Chrome with an updated IOS which I could really use for a VPN. I could also use my main vimrc. But I still needed a repaired PC to use at my home. If I didn't have one, I would either give up the contest, or try to use a smartphone which is kinda ridiculous (has anybody done that?), or do the contest at a place with a PC which would work actually, but I don't know of a place like that off the top of my mind.
      tl dr; thank you for the protip.

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

Good luck everyone :D

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

Happy Rose day to all...

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

Will the round be sorted by penalties or will points be awarded?

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

10,000+ registration is now become common for codeforces ):

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

Are the problems sorted by ther difficulty ?

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

Wish you good pretests and high rating!

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

Traditional randomization scripts!

The second script is used to feed random places into the first script. Seed will be the score of the top1 contestant of today's contest, length is the number of people with ranks 31..500 (likely 470) and nwinners is 20.

get_ranklist.py
randgen.cpp
»
7 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

I think wery0 liked this round wery much. Thanks, problemsetters (especially Mr GreenGrape) for good tasks and fast editorial. Also, I want to say thanks to MikeMirzayanov for great(grape) platforms: Codeforces and Polygon!!!!

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

How to solve E

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

Many people used pow function in A which will overflow but those ran fine. Can someone provide a test case on which these overflow solutions will be wrong if any?

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

A was more interesting than usual. :)

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

How to solve D?

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

    Did not solve it, but if im not mistaken you can decrease each value to ={1,2,3}. And then apply DP.

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

    Just note that you don't need to remove the same consecutive triplet more than 2 times, because otherwise you could have just gotten the same result by removing each number separately.

    This in turn allows for a DP solution. Just go through the numbers in sorted order and keep track of how many consecutive triplets the previous number and the previous previous number have been a part of.

    EDIT: Some clarifications. The dp state is how many you have left of the previous number and how many you have left of the previous previous number. And because you only want to remove the same consecutive triplet at most twice you can assume that you have at most 2 of the previous previous number.

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

Very nice problem C!

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

how to solve B?

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

    Note that if we are allowed n pieces of tape (when k = n), we can end up using a minimum total length of n cm. (We would use 1 cm for each broken segment).

    Consider the case where k = n-1. Then we need one piece of tape to cover (at least) 2 broken segments. We want to minimize the total length, so we want this piece of tape to cover the two adjacent segments that are closest.

    In general, if we have k pieces of tape, then we will have to merge (n-k) adjacent segments.

    Let's define the adjacent difference of segments i and (i+1) as (b[i+1] — b[i] — 1).

    So for b[i] = 3 and b[i+1] = 4, the adjacent difference would be 0 and we can tape over both with 1 piece of tape of length 2.

    We can generalize this by sorting all adjacent differences then taking the sum of the (n-k) smallest ones and adding n to that sum to get our final answer.

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

Best problem C I've ever seen~

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

Can someone explain why binary searching for the answer (minimum length) with a greedy function wrong in case of B problem? I kept on getting WA on pretest 7. A hint would suffice.

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

B was harder than C for me. LOL

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

how to solve B?no idea :(

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

Well...I think the pretest of problem A is too weak because I passed the pretest while writing x&1 wrong as x^1...

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

E is one of the best problem E ever on Codeforces, until I realized that one can fail system test because they forget to check if c[1] ≠ t[1] or c[n] ≠ t[n].

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

Does this count as cheating? I saw a submission for C where the user created a map of all the possible input a's to the answer. Probably these answers were brute forced earlier and logged?

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

What is test case 35 in D? Many people including me are failing on that

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

Problem E was on AtCoder: link.

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

even the submission that i didnt have time to submit is WA .. now I can rest in peace

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

I love this contest, where the difficulty is in ideas not just complex code.

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

When can we konw the final result ?

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

Just for curiosity, why are there no hacking session for this contes_- _t? The contests I participated since were rated for Div2 so... just curious.

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

So I was using ideone for this contest since I'm not home and I didn't want to install codeblocks on this pc and I got a message that bruce_knight copied my code for B. The message said I could be getting banned for this ? What are my options ?

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

Even tourist couldn't solve H ?
There must be something wrong with tourist or that question...

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

I think there are some problems that have appeared in another place. For example: E: BZOJ5071  I'm sorry that the language for this problem is Chinese, but this problem is similar to Problem E (My English is not good)

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

Can someone explain the logic behind E?

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

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

In api expected rating change shows +34 but in rating changes it shows -4

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

I had almost solved problem G but there was not enough time.... It's an interesting problem to me though.

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

Can F be done with centroid decomposition ?

For each leaf ,go up to root via centroids storing in each centroid ,distance of leaf from it and its index. For each centroid we keep this list sorted on the basis of indices. While answering a query, we go up to root from vertex v via centroids, at each centroid, we need to query min dist of leaf from this centroid whose index lies in L to R(simple RMQ).Take this minimum across all centroids in my path to root .

Is this approach correct ? will it fit the TL ?

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

I think the rating changes for today's contest were not correct. As the "CF Predictor" extension showed something else and the rating changes were different.

Kindly look into the matter.

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

Problem C was a great question. The only case you had to take care of was when a was of the form 2^x-1. The trick involved was gcd(a&b, a^b) = gcd(b, a-b) = gcd(a, b). So we need to find the greatest proper divisor of a. Kudos to the writers!

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

Can D be solved using a recursive approach without running into "Memory limit exceeded"?

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

Hey,guys.I have a problem on 1110D — Jongmah. I passed the test 1 locally on my machine,however get WA on the net. Here is running ID #49593747 Help me please!!!QAQ

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

When will the editorial be published?

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

Thanks to this contest, I have become a candidate master. I'm so happy.

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

KAN, Why 2 links to the same editorial are added to contest page?