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

Автор Stepavly, 3 дня назад, По-русски

Привет, Codeforces!

UPD: Так как после тестирования раунд кажется чуть сложнее обычного, мы продлили раунд на 15 минут.

<almost-copy-pasted-part>

Привет! В 10.06.2021 17:35 (Московское время) начнётся Codeforces Round #725 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7 задач. Задачи подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше, могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы будем расстроены, если у многих попадают решения после окончания контеста.

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

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше. Независимо от того, являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Задачи на этот раунд были придуманы MikeMirzayanov, Supermagzzz и Stepavly.

Спасибо Fly_37, -is-this-fft-, A_Le_K, ALILILILILI-KHAN, ANZ1217, hocky, PhaiCoGiaiQuocGia, Sho, ASIXER, songsinger, OlegZubkov, AlexFetisov, darkkcyan, ivanzuki, kocko, Gassa за помощь в тестировании раунда.

Спасибо MikeMirzayanov за платформы и координацию нашей работы. Удачи!

</almost-copy-pasted-part>

UPD: Разбор

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

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

It's my first time as a blue coder in a (Div 3) contest. I was waiting for this for a long time. Best wishes to all the rated contestants.

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

    Same here, I feel like our individual hard work has finally paid off. Good Luck for purple. :D

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

      I'm try my best to reach the blue coder. But failed again and again. I didn't lose hope. I'm still trying. The main painful things, I solve problem after contest, But contest time I feel stressed. What should I do? any advise?

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

        Have patience And keep trying . You are not alone in this

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

        There's no need to be stressful. Focus more on problem solving than rating. That's what I'd say. When I thought of reaching expert I stayed cyan but when I focused on solving till D, positive delta was complimentary. I made silly mistakes in some contests and got AC right after the contest ended. I think that's a part of the learning curve too.

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

          I think, It will work. Although I've done silly mistake again in problem D and got AC right after contest ended, But I'm satisfied. I only focused in solving problem. Next time, I will keep it mind. Thanks.

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

        Don't lose hope. In your stage, I suggest practice more Light OJ, CF (C, D) problems. Try to practice more and more binary search, (bfs, dfs), number theory, and DP problems. Here is a native Bangla Youtube channel Bangladesh Advanced Computing Society — BACS that may help you.

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

          loved the length and quality of questions picked by this youtube channel. but can this be in Hindi or English ??

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

        I'm a newbie, gave my first contest yesterday but my opinion is virtual contests can help as they are not rated and you can calmly solve problems as you said you can't solve because you're stressed during the contest and by gaining confidence in virtual contest you might also be able to perform better in rated ones,im not saying give only virtual contests,but practice problems thru them, practicing this way can help you to perform better under time constraints.just a suggestion.........if that works

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

          Well.. But some silly mistake makes me annoying. Yesterday contest, I've done well but in problem D,I just a little error. Just few minutes after the contest I caught the silly error. This is really disappointing. However, that's also a learning part, One day I will overcome and will get success.

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

            yup ,also happened with me for B , i was checking if sum/n was an integer by storing in float and converting to int and comparing the two values but it was giving wrong answer ,idk why like 28/5 was saying it was an integer and 5.6 not an integer ,do you know y? , just few minutes after the contest i realized all i had to do was sum%n ==0 or not , such a stupid thing ,such things do happen ....... immediately after the contest i was able to submit B and got accepted,

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

      Hoping for positive delta this time.

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

    Wow! You have a nice participation graph — you are the first person I see that participated in 1970. How was it back then? :)

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

    same :)

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

Round 719, yes I have arrived in past.

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

Hello! Codeforces Round #719 (Div. 3) will start at Wednesday, May 5, 2021 at 20:05UTC+5.5.
<almost-copy-pasted-part>
I think it should be <fully-copy-pasted-part> instead

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

Hoping for a good increase of the rating In Sha Allah...

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

I am missing vovuh for Div-3 rounds.

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

    I guess vovuh has betrayed div3, Curious why he is staying loyal to educational rounds xd

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

      I wouldn't say I betrayed Div.3, if I got the meaning of this word in your sentence correctly. Just a combination of circumstances forced me to stop doing them. I'm also not doing Educational Rounds, though. Guys just take my problems from time to time (rarely), that's all.

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

hoping for short and concise questions and a good performance :)

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

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

Any motivational lines please?

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

I waited so long for this day! At last, unrated in div3 for the very first time *_* Cant't wait more for the contest.

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

finaaly i realy miss div 3 contest :(

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

Good luck to everyone!

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

Aiming for specialist.

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

What is the 10 min penalty for the wrong submission? will time reduced if submitted wrong solution??

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

    No, you will still have 2 hours to solve the problems. Penalty time is just a counter used as a tie-breaker for contestants with the same number of solved problems. The less penalty you have, the better.

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

Cannot wait to get started :) Hope for concise and clear problems.

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

UPD: Since the round seems a little more complicated than usual after testing, we extended the round length by 15 minutes.
Hard problems coming up

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

Suddenly my rating changed to 1601 from 1598. Will the round be still rated for me lol?

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

Nice to see so many participants hope the servers don't go down during the contest.

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

Does 15 minutes really matter for the Cyan guys!! :p :p

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

Wow!!!! This is the first unrated contest for me!!!

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

fingers crossed no technical issues for this contest

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

Since the round seems a little more complicated than usual after testing, we extended the round length by 15 minutes.

This is super sus.

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

27k+ participants. Looking forward to long queues ... :/

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

E is the worst problem I've seen.

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

Sequence of problems should be A->B->C->F->D->G->E

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

I started implementing E and then it was while parsing the input when I realized that it was a bad idea..

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

My first time solving the entire contest

"the round seems a little more complicated than usual" must be a joke

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

is F that easy more that 4K solved it sadly I have no time to see it :(

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

Very balanced round
B = C = D = E = F = G

Only A was sadly out of the pack

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

    Well, to be more precise

    Ranking by the amount of time I spent + penalty time

    D(44) > C(31) > G(28) > E(19) > F(8) > A(5) > B(4)

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

A moment of silence for those who were trying to solve D using Gcd to handle the No case

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

Is there a purely mathematical solution for G, I wasted an hour trying to fit the right formula but couldn't figure it out, then I realized there exists a thing called binary search.

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

    logic? or how you decide that x gifts can be made?

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

    If we take $$$N$$$ gift sets of type 1 ($$$a$$$ red, $$$b$$$ blue) and $$$M$$$ gift sets of type 2, then we want the maximum $$$N + M$$$ constrained by $$$Na + Mb \leq x$$$ and $$$Nb + Ma \leq y$$$, which are two lines. The optimal point is at the intersection of those two lines. So we get an $$$\mathcal O(1)$$$ solution.

    Submission

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

      Ah.. just recalled it from my linear programming course, thanks!

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

      Yeah, But I tried to solve them using simplex and get an WA, I think using Simplex here is OverRated.

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

        lol yea simplex was actually my first thought when reading the problem as well, but simplex can't find the optimal integer solution, just optimal solution in general.

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

      Oh, I've looked into your solution, that's much simpler then mine... I did coordinate transformation $$$N=K+G$$$ and $$$M=K-G$$$ so I could maximize $$$K$$$ without regards of $$$G$$$ (since $$$K=\frac{N+M}{2}$$$) and then needed to check for $$$K<G$$$ and $$$K<-G$$$. But judging from your submission I totally didn't need that transformation.

      I guess I did that, because I wasn't sure, that the ideal solution will be at the intersection. After performing the transformation it was obvious, that the solution will be either at the intersection or at $$$N=0$$$ or at $$$M=0$$$. But I still continued my calculations from there with the transformation which made it more laborious.

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

    Same with me.

    Except that I quickly decided that I'm too stupid for math and started to write binary search from the start

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

    I thought that somehow Chicken McNugget Theorem could have helped but couldn't figure out till the end as to how to use it in this problem and now I see everyone used binary search T_T .

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

    I solved G with a logic/math solution similar to neal's first ac submission (he resubmitted with binary search uh oh) which is $$$\mathcal{O}(1)$$$. I'm not confident that it is correct (bcz I suck at proofs) but it seems to intuitively make sense. My general approach was as follows:

    Assign $$$\min(x, y)$$$ to $$$x$$$ and $$$\max(x, y)$$$ to $$$y$$$. Then, attempt to balance $$$x$$$ and $$$y$$$ by subtracting $$$\min(a, b)$$$ from $$$x$$$ and $$$\max(a, b)$$$ from $$$y$$$ until either $$$x$$$ and $$$y$$$ are balanced or $$$x$$$ has been exhausted. Then, evenly subtract the rest from $$$x$$$ and $$$y$$$ by alternating $$$a$$$ and $$$b$$$ (starting with $$$\min(a, b)$$$ for $$$x$$$ and $$$\max(a, b)$$$ for $$$y$$$). My solution code is below.

    pls hack this or smth

    Does anyone else have this solution?

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

    Well Well Well. How the turn tables

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

I think Problem-F should be placed before Problem-D or may be also before Problem-C.

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

WTF was the positioning of F. I read it when there was 1 minuite left!

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

problem D is bad itself(case consideration), and moreover, I had to change longlong->int and map->unordered_map to pass tl, G with ternary search with stupid trick can be easily passed, some other problems I can't remember, they weren't interesting, not very good round for me:(

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

    What is wrong with D? Probably, you just have bad implementation. My solution is short and clear, no corner cases. You see it is part of the programming skill to write in such a way that there are no corner cases and huge code.

    G is also my problem. I think it is good) Ternary search, probably, is wrong in this problem.

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

      it's just my opinion, I wasn't able to come up with a good solution, so I spent my nerves on consideration), also I think that G can be solved in that way is not really good, but most likely it will be hacked, I suppose. Anyway, most of the previous div3 rounds were more interesting for me, so...

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

      Agreed!!

      I wrote a poor code in D, but still fail to understand why my TLE submission got AC after changing a lots of heavy lines of if-else statement into single if-else statement.

      Does that affect the code somehow :-(

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

    What's wrong with case analysis? The fastest solution for D runs in 30 ms, how can you say the TL is was strict?

    But it would be nicer if the TL was 4-5 seconds or if ${T} was decreased to 1000 from 10000. This would allow solutions in slower languages to pass comfortably, without compromising the core idea.

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

      case analysis is boring:/, tl is just not enough strict for wrong solutions or on the contrary too strict if solutions using straight factorization are considered correct

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

    It can be tempting to say a round isn't very good because you found it difficult, or what you tried didn't work. A good round has a range of problems of different difficulties, not 7 easy problems that anyone can get. I think this round was good, because it had interesting, and in some cases unusual, problems, which were varied in difficulty.

    I struggled on G too because I tried ternary search. I got it wrong, and then had a different idea which worked. That's part of the fun.

    D I also got wrong initially because I missed a crucial pruning insight. Again, that's part of the fun.

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

      firstly it's just my(very important:)) opinion, secondly, I said nothing about difficulty, but I think you're right about the correlation between difficulty and fun. But in my opinion, that's not a such case

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

well that was embarrassing

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

Any hints for D?

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

    There are only two cases to consider to get both numbers a and b to the same number c: if operations are too much or little...

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

D ruined the contest for me.

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

Solving F but not solving D army !!

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

Here's my video of the contest (including solutions) on YouTube: https://www.youtube.com/watch?v=FXcIKhU_3IU

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

is it just me or the time-limits on D and memory -limits on E were strange for some reasons ?

»
2 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  1. what is the trick for problem C.
  2. Help me in problem D where i am doing wrong. https://codeforces.com/contest/1538/submission/119067539
»
2 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

TLEForces

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

What is the idea for the solution of F?

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

Is C literally that easy? How to do it?

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

    binary search for the good range of all numbers >= a[i] excluding a[i] for each i

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

    yes, just sort the array and for every ith element count how many elements are there from (i+1) to n which holds (elements>=(max(0,l-arr[i]) && elements<=(r-arr[i])(using binary search). This will give us the range we just need to add this range in our answer.

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

Problem E should be put in the position of the problem G.

And for new competitors, you don't need to solve these questions in default sequence, if you have solved problem i, the next problem you are going to solve is unsolved problem j that have maximum accepted users, j don't need to be i+1.

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

I solved C using point compression and segment tree, was there an easier solution?

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

    just sort it and use lower_bound and upper_bound for l — vec[i] and r — vec[i] for each index to the right

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

    Binary Search

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

      please explain

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

        let's say have 1 5 3 4 2 and l = 5, r = 8 sort -> (1 2 3 4 5) next iterate and for each element (from left to right) at index i, find 2 things:

        1) first greater or equal element index to l — vec[i](just c++ lower_bound function): index1

        2) first greater element index + 1 to r — vec[i](just upper_bound) both in [index + 1, end): index2

        for each element answer is index2 — index1. sum up all answers and get the final

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

    You can also use a 2 pointer approach.

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

      How? I tried but got stuck

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

        You can check my solution, but the idea is that you can sort the array and process it in order of increasing a[i]. Now you need to solve how many pairs are such that a[i] + a[j] <= X. If you start from the smallest a[i], all the numbers <= X — a[i] will be valid pairs. As you move to the next i, a[i] will increase, and the numbers <= X — a[i] will only decrease so you can use a pointer.

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

My greedy solution for G passed pretests, does it survive system testing?

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

How to prime factorize (count the number of prime factors) the two numbers in D in 2 seconds ?

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

    I precomputed the primes till $$$\sqrt{10^9}$$$ and then iterated over it code

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

    Store all prime numbers upto $$$4e4 (sqrt(1e9))$$$ there are about $$$3000$$$ of them, then check only these numbers atlast check if there is a prime factor greater than $$$4e4$$$ (there can be atmost 1).

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

    First, we need primes <= sqrt(1e9), we have approximately 4000 primes You can do it by sieve. Then you can use those primes to factorize. Like this: for prime in primes, while(num % prime==0) { num/=p; power++;} do it until prime < sqrt(num). In the end if num > 1 then it is also a prime. Max count of prime can be approximately 13 for a number < 1e9. For each prime power count can be at max 28. So it will pass.

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

I think that the test cases of D are slightly weak. Mine should have given TLE imo.

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

How to solve E ?

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

Can someone explain the approach to D?
I tried calculating the number of prime factors in the similar parts (GCD) and the dissimilar parts of the numbers but there seemed to be just too many edge cases to manage.
Should have at least opened F instead.

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

I registerd yesterday and I did not get any ranking points, why?

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

    Registered yesterday as an Alt you mean. Well, I'd guess it's because you're not a Trusted Participant, but you must have read that from the announcement. But I guess you missed it.

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

In problem D when using int it is getting accepted but showing TLE for long long! why??

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

    Because long long eats up memory stack, you are not supposed to use long long everywhere, use it only when you suspect an overflow.

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

Pretty easy but my hands aren't fast enough to AC all :(

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

imagine all above Mike's comments written by radewoosh...

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

You can solve C using Dynamic segment tree!

Link

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

This is ridiculous, how the time limit for D is so strict for c++ but not for other language?

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

10^9forces

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

What is the expected time complexity of D?

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

Can anyone please explain me why in my function getPf changing getPf(int x) to getPf(ll x) gives TLE for question D

TLE code: 119084091

AC code: 119084144

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

Can anyone suggest me problems like F. Interesting Function.

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

119063957 119067741 119066275 check all solutions of these people they are the same ... They did this in all contests....

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

Is there any discrepancy in the test case for Problem C, This guy naitikvarshney has hacked more than 100 AC solution. MikeMirzayanov please look into the matter.

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

    Your code got hacked due to Arrays.sort() function which in worst case have O(n^2) time complexity.

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

      Damn, Thanks for letting me know. Will use the Collections next time. Happy Coding.

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

      How does hacking work? (newbie here) Am I able to correct the solution and still get the credit?

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

      I was hacked by this since I used java's Arrays.sort() method, but when I reversed the input array before sorting, I got accepted. This is because the test case used in the hack was deliberately chosen for this java's specific implementation of dual pivot quick sort to run in its worst case, when nearly any other array could be sorted much faster. My submission where I reversed the array could easily be hacked as well by simply reversing the input, which is why I think something may need to be done about this. Either way, the Collections.sort() method will always run in O(NlogN), and will always be accepted.

      Solution without reversed array that got TLE: https://codeforces.com/contest/1538/submission/119093728

      Accepted solution with reversed array: https://codeforces.com/contest/1538/submission/119099990

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

        I tested that it sufficed to Fischer-Yates shuffle the array prior to using Arrays.sort(). But is it faster in this case to simply use an ArrayList instead of an array and do Collections.sort()?

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

119083149

Anybody, please help!

I am not able to figure out why I am getting TLE in question D https://codeforces.com/contest/1538/submission/119083149

I really appreciate any help you can provide.

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

I kind of applied the same logic in D as mentioned in the editorial, but not able to pass the tests. Can anyone tell me what am I missing link

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

119082014 for D i have calculated prime factors for both the numbers in O(sqrt n) then also giving tle.

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

I replaced int with long long and it got accepted.In long long it was getting TLE.It's very sad.

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

Nice contest. I wish the authors of the tasks success in the future!

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

I personally believe the level of this contest was not exactly same as other Div 3 contests. Its difficulty level was somewhere between regular Div 3 and Div 2. Again, it's a personal opinion.

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

Hello all I wasn't able to solve a single problem today!! idk i have practiced over 70 questions now but still can't think of the approach properly!! any suggestions

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

How come all the java submissions are being hacked (tl)by naitikvarshney, while the same solutions in C++ and python are working perfectly fine ?

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

Can someone tell what is wrong in this code of Bugaboo C — Submission I am not able to see testcase on which it went wrong.

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

According to these rules 1.take part in at least two rated rounds (and solve at least one problem in each of them), 2.do not have a point of 1900 or higher in the rating. I should be eligible for rated round but it doesnot happen dont know why?

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

Problem D with some explanation and code. Link

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

Come on Man! My Man CF mod !. Release the ratings already man. A long time since a contest went this good. Been 6 hours man. :D

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

For problem D, I'm using a long long data type, which makes me TLE, but when I change it to INT, I get AC

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

Can anyone tell which corner case I am missing in the solution to problem D? I am getting WA on token 1021 of test case 2. Here's my link 119065848. Thanks.

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

Can someone please help me to know why this solution of C is giving TLE at test case 4. The time complexity I suppose is Nlog(N) here. 119107327

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

For the best time I was able to solve 4 questions :)

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

I wasted more than 100 minutes on problem D and still couldn't solve the problem in the contest (WAs throughout), only to find out later that I had taken return type for a function (counting prime factors) as "bool" instead of "int" ! I have never felt so useless before lol

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

Do runtime errors count in wrong submissions?

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

A bit confused, after how long will the ratings be updated? (also if someone can share blog post on codeforces which talks bit more on this)

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

    System testing hasn't started yet. First that'll happen and after it's finished the ratings are updated within the next hour or so.

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

      Hi, I'm not quite familiar with codeforces system. Could you please tell me when will the system testing begin?

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

        There isn't any specific time for system testing, it happens soon after the round is finished in Div.2 , and after the hacking phase is finished in Div.3 and edu contests

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

Hey! This is my first time giving a contest so I have a few doubts. My rating has not changed from 0 till now. I did successfully submit 2 ques near the end of contest. So will they not be counted cause I took too much time??

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

Hi ! MikeMirzayanov when will you update the rating?

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

Comparitively easier problem set than previous div3 contest.Apart from problem E,most of them seemed like Div4 type problems.

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

I can't understand why this round was made unrated Can anyone explain me the reason. Thanks in advance.

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

I'm wondering about division system? Is it based on rating? If yes then how is div1 div2 and div3 divided?

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

    Kind of based on the rating of participants rated

    Div3 1600-
    Div2 1900- if there is a concurrent div1 round, 2100- otherwise.
    Div1 1900+

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

А почему для меня раунд оказался не рейтинговым? У меня же рейтинг меньше 1600

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

why E had so less submissions? I felt it easier than many other problems.

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

Why hasn't the Rating been updated

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

I got a message that my submission for problem B in round 725 coincides with other solutions. I had not shared my solution to anybody nor used any public IDE.I only submitted my code at codeforces and it can be a coincidence and the variables that I used are totally different from other people and many of the people wrote their codes after me .

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

hey can anyone tell me why did i got a plag on F buz i code it on my own..

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

    MikeMirzayanov, Stepavly Supermagzzz please look into this i didn't copy tht man and if i had to i should have copied each and ever answer or atleast A question too i didn't copied what else can i say, please restore my rating

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

fahimfardous8 and Toxic_046 both account is mine. I tried to solve Codeforces #725 contest problem in both account.When I solved problems A,B then submttefd in both of my accounts.I apologise for that.I can give proof that both of the account is mine.

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

    It's still wrong even if both accounts are yours, you are essentially bypassing all the WA penalties. How do you expect CF to know which account belongs to which human on earth. If 2 accounts use the same solution, they should be penalised.

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

fahimfardous8 and Toxic_046 both account is mine. I tried to solve Codeforces #725 contest problem in both account.When I solved problems A,B then submittef in both my account

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

I got a message for my solution to F question to be matching with some other participant's codes. I have written my code on my own. I did refer to Stack overflow for Functions within functions in c++. Link: https://stackoverflow.com/questions/4324763/can-we-have-functions-inside-functions-in-c. Please check. I have not indulged in any malpractice that violates codeforces rules. It must be a mere coincidence since the code was extremely short and easy and had a very naive approach.

I assure that I will not use any code snippets from Stackoverflow in future contests.

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

I have been accused of plagiarism against my own solutions. Please look into this.

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

I'm not able to find my name on the official standings for this contest(trusted users list) but when I click on my friends standings it shows me rank greater than what is on the official list, Will I not get rating for this contest?

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

    Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:

    take part in at least two rated rounds (and solve at least one problem in each of them), do not have a point of 1900 or higher in the rating. Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

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

PLAG ALERT : Someone(anti_shab and zZz2) copied my code I don't know from where but they copied it. Please everyone take care of this from next time. I am not sure whether my ratings will be updated or not. If anyone has any solution to this please do tell me.[user:anti_shab][user:zZz2] please don't eat someone's hard work

[user:MikeMirzayanov][user:Stepavly][user:Supermagzzz] please hav a look at it

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

    Quick question why do people use ideone during contests? can't you install a compiler and code editor on your machine(don't mean to offend anyone but I would really like to know why on earth are people using ideone or similar websites during contests)

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

I just received a mail from system stating: Attention!

Your solution 118979297 for the problem 1538B significantly coincides with solutions Rituraj.rs/118979297, shivam14_20/119035373. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked. I had submitted first solution within 8 minutes and was continuously solving others. I dont even know the person mentioned. I have been using the same template for other submissions also and I usually follow common names for loops and arrays. I believe that my usage of common names for loops and arrays has lead to this. Please help me. I never share my code with anyone during the contest.

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

i recently got an email saying that one of my solutions submitted coincides with some other users solution. i did not refer to any online resource or "ideone.com" as mentioned in the email which I have no clue what it is. this is purely a coincidence that could be justified by the easy difficulty level of the problem itself. I know for a fact that I have done that problem on my own and want any kind of warning/rr reduction removed ASAP. solution number:119007587 problem number:1538B

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

I had written code on Hackerrank IDE. I just received a mail from system stating: Attention! Your solution 118979297 for the problem 1538B significantly coincides with solutions Rituraj.rs/118979297, shivam14_20/119035373. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked. I had submitted first solution within 8 minutes and was continuously solving others. I dont even know the person mentioned. I have been using the same template for other submissions also and I usually follow common names for loops and arrays. I believe that my usage of common names for loops and arrays has lead to this. Please help me. I never share my code with anyone during the contest. MikeMirzayanov Please look into this

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

I just received a plagiarism warning on problem 1538B. I had written the entire solution by myself and I do not understand why I was flagged by your algorithm. on comparing codes with the mention submissions in the email it can clearly be seen that my code greatly differs from the rest two other submissions while their code is exactly same. I hereby want this warning//rr reduction to be removed ASAP. the conclusive evidence is itself the comparison between my submission and the rest submission mentioned in the email. I would further request to please fix your algorithm before sending out emails about plagiarism. solution number: 119007587 to compare solutions with other submissions mentioned: 119049812,119065057

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

My rating is less than 1600 yet this contest shows unrated for me :/ I have even given more than 2 contests before

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

Problem D: Another Problem About Dividing Numbers

Tutorial Link: https://www.youtube.com/watch?v=00FBTOay-3E

It'll help & understandable for those who knows bangla language specially.

Thanx to all.

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

Problem F: Interesting Function

Tutorial Link: https://www.youtube.com/watch?v=sEZbLMYVS48

It'll help & understandable for those who knows bangla specially.

Thanx to all.

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

Всем привет! Мне пришло письмо с сообщением о том, что решение участника vippro https://codeforces.com/contest/1538/submission/118981243 совпадает с моим https://codeforces.com/contest/1538/submission/118983434. Да, я сам был поражён, когда открыл код. Ранее мне приходило такое предупреждение, когда я писал на сервисе ideone.com и случайно оставлял открытыми мои исходные коды, которые потом парсили что-то вроде ботов. На этом же соревновании я писал в visual studio code и вообще не использовал онлайн сервисов. Я понимаю, что участник vippro предоставил решение раньше, но я даже не знаю, как я бы нашёл его код (только если бы у меня не было бота по типу, как того, который у меня украли). Я просто прошу заметить, что я сдал все задачи на этом контесте. Явно, если я сдал задачу E, я бы не стал искать решение задачи B. Я надеюсь на понимание администрации, что такие совпадения имеют место быть, особенно когда задача тривиальна. Если сравнить моё решение с оригинальным авторским — https://codeforces.com/blog/entry/91637, то явно тоже практически один-в-один, только я никогда функции solve не пишу. MikeMirzayanov Supermagzzz Stepavly

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

????????????where's my rating??????bro???????????

NO rating ??????????

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

It was my first contest on codeforces, I solved 2 problems but my rating is not updated

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

MikeMirzayanov можно узнать по какой причине могут забирать баллы, если задачи были решены с первой попытки? Это второе соревнование, когда при верном решении с первого раза отнимаются баллы, хотелось бы знать почему)

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

Thank you to the authors for such a great contest! This contest helped me a lot to become specialist for the first time!! :D

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

i have used ideaone for testing my code while i am solving contest #725 (div. 3). since my profile was open to all, my code got shared with others. so please consider my reason and consider my solutions. i will be sure not to repeat this again and requesting to award me the specific ratings which i have earned from this contest.

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

Can anyone help me with this question on 725_div3 Problem C Giving TLE on custom binary search when used instead of Upper an lower bounds. Here is the link to my solution https://codeforces.com/contest/1538/submission/119267566